(english version below)
O problema deste post foi-me colocado na primeira edição das Jornadas de Matemática da Faculdade de Ciências da Universidade do Porto, numa sessão de jogos matemáticos! O problema é particularmente engraçado porque assenta num jogo que se pode jogar entre duas pessoas.
Problema: suponha-se que sobre uma mesa estão dois montes de feijões, um com 19 feijões e outro com 20 feijões. A Ana e o João vão jogar um jogo com esses montes de feijões: cada jogada consiste em retirar $2N$ feijões de um monte e pôr $N $ feijões no outro monte. Assim, na primeira jogada podemos, por exemplo, tirar 10 feijões do monte com 19, deixando-o com 9, e pôr 5 feijões no monte com 20, deixando-o com 25. A Ana vai ser a primeira a jogar e perde quem não puder fazer nenhuma jogada válida. Será que algum dos jogadores consegue garantir a sua vitória?
Este jogo tem regras muito simples e é bastante engraçado, vale a pena jogá-lo com alguém só para entender realmente como funciona a dinâmica do jogo. Incluímos aqui uma janela para que se possa jogar o jogo contra um jogador virtual que não segue nenhuma estratégia em particular, exceto quando, perto do fim, ele reconhece uma jogada vencedora. Para jogar há que carregar no triângulo por cima do código e escrever as nossas jogadas na parte da direita. "Fazer uma jogada" corresponde a escrever os novos tamanhos das pilhas depois da alteração que escolhermos fazer; por exemplo, se fizermos a jogada descrita no enunciado, escreveríamos "9, 25". Por defeito o computador joga pelo João; para alterar isto basta escrever um $1$ em vez de $0$ à frente de "GOES_FIRST".
Solução: vamos mostrar que o João tem uma estratégia vencedora. Em vez de apresentar apenas a prova de que o João consegue sempre ganhar, vou tentar recriar todo o meu raciocínio que levou a esta conclusão.
Representemos o número de feijões nos montes por um par $(x,y) $. A primeira coisa óbvia a notar é que as jogadas que se podem fazer em $(x,y) $ também se podem fazer em $(y,x) $, portanto tudo o que concluirmos sobre a posição $(x,y) $ aplica-se à posição $(y,x) $ e vice-versa. Agora começamos por notar que, se for a nossa vez de jogar e estivermos em alguma das posições $(0,0), (1,0), (0,1), (1,1)$, perdemos... O que quer dizer que o nosso objetivo é estar numa posição qualquer $(x,y)$ e jogar de modo a passarmos ao nosso adversário uma das quatro posições anteriores. De onde é que podem surgir essas jogadas?
Notamos que é impossível chegar à posição $(0,0)$, já que em cada jogada tiramos feijões de um monte e pomos feijões no outro, portanto há sempre um monte que tem mais do que $0$ feijões; como é que podemos chegar a $(1,0)$? É fácil de ver que só a posição $(0,2)$ pode dar origem à posição $(1,0)$, da maneira (óbvia) que vemos na figura:
De modo semelhante podemos concluir que, para chegar à posição $(1,1)$, temos de ter vindo da posição $(3,0)$ (ou da posição $(0,3)$ claro). Neste momento já sabemos qual é o resultado de um jogo, jogado por dois jogadores perfeitos, que comece numa das posições $(0,0), (1,0), (0,1), (1,1), (2,0), (0,2), (3,0), (0,3)$. Vamos continuar este tipo de raciocínio e sistematizar as nossas conclusões numa tabela. Dizemos que uma posição é perdedora P se, num jogo começado nessa posição, o primeiro jogador perde, e dizemos que uma posição é vencedora V se, num jogo começado nessa posição, o primeiro jogador vence. Por exemplo, a posição $(1, 0)$ é P. O que sabemos até agora é o seguinte:
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline 0 & P & P & V & V & & \\
\hline 1 & P & P & & & & \\
\hline 2 & V & & & & & \\
\hline 3 & V & & & & & \\
\hline 4 & & & & & & \\
\hline 5 & & & & & & \\
\hline
\end{array}
$$
Continuamos a preencher a tabela, concluindo com alguma facilidade que as posições $(2,1)$ e $(2,2)$ são perdedoras; de seguida, podemos concluir que as posições $(3,1), (4,0), (4,1), (5,0), (6,0)$ e $(4,2)$ são vencedoras, porque todas elas podem chegar a $(2,1)$ ou $(2,2)$. Note-se que para uma posição ser vencedora basta que uma jogada sobre essa posição leve a uma posição perdedora. Por exemplo, na posição $(4,0)$ podemos passar para $(2,1)$ ou para $(2,0)$. Se passarmos para $(2,1)$ ganhamos, porque $(2,1)$ é uma posição P, mas se passarmos para $(2,0)$ acabámos de dar a vitória ao nosso adversário.
Por outro lado, para uma posição ser perdedora é necessário que todas as jogadas sobre essa posição dêem a vitória ao adversário, i.e. o jogador A só está numa posição P se, independentemente do que fizer, o jogador B fique numa posição V.
Preenchendo a tabela com as nossas novas conclusões obtemos
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline 0 & P & P & V & V & V & V \\
\hline 1 & P & P & P & V & V & \\
\hline 2 & V & P & P & & V & \\
\hline 3 & V & V & & & & \\
\hline 4 & V & V & V & & & \\
\hline 5 & V & & & & & \\
\hline
\end{array}
$$
Neste ponto podemos começar a notar que um certo padrão parece emergir, que evidencio na tabela seguinte:
Neste momento podemos ser levados a fazer uma conjetura: as posições perdedoras são as posições da forma $(x, x+1), (x,x) $ e $(x+1,x) $.
Antes de testarmos essa hipótese, vamos ainda preencher as posições $(3,2), (3,3), (2,3)$. Se estas também forem posições P, então a nossa conjetura ganha relevância e vale a pena testá-la.
Notamos que, estando na posição $(3,2)$, apenas conseguimos ir para as posições $(1,3)$ e $(4,0)$, que são as duas posições $V$, logo $(3,2)$ (e por conseguinte $(2,3)$) é uma posição P. De modo análogo concluímos que $(3,3)$ é uma posição P:
Poderíamos continuar a preencher a tabela, mas neste ponto já vale a pena tentar provar a nossa conjetura; não porque temos a certeza absoluta de que ela é verdade, mas porque se não for, somos capazes de compreender melhor que outro tipo de posições também são posições P.
Conjetura: Uma posição $(x,y)$ é uma posição P se e só se $y \in \{x-1, x, x+1\}$. Isto é, toda a posição P é da forma $(x,x-1),(x,x)$ ou $(x,x+1)$ e toda a posição dessa forma é uma posição P.
Começamos por provar que todas as posições da forma anterior são perdedoras, por indução no tamanho da primeira pilha. O caso base é para as posições $(1,0), (1,1)$ e $(1,2)$, que é trivialmente verdade pela tabela que já construímos. Supomos agora que as posições $(k,k-1), (k,k)$ e $(k,k+1)$ são todas perdedoras, para $k < x, x>1$, e mostramos que isso implica que as três posições $(x,x-1), (x,x), (x,x+1)$ são perdedoras também; para tal, verificaremos que, independentemente da jogada feita a partir dessas posições, o adversário consegue sempre jogar de maneira tal que voltamos a estar numa das posições na zona a vermelho. Relembramos ainda que o caso $(x, x-1)$ é dado de graça pela hipótese de indução, uma vez que $(x, x-1) \approx (x-1, x) = (k, k+1), k=x-1$ é uma posição perdedora pela hipótese de indução.
Note-se que, se da posição $(x, y)$ pudémos fazer a jogada $(x - 2N, y + N)$, então assumindo que $y + N \geq 2N$ podemos fazer a jogada $(x - 2N, y+N) \to ((x-2N) + N, (y+N) - 2N) = (x - N, y - N)$, i.e. mantemos a diferença entre os tamanhos das pilhas ($(x-N)-(y-N) = x-y$) mas diminuimos o tamanho total das pilhas. Basta agora notar que tanto no caso $(x,x)$ como no caso $(x,x+1)$ podemos fazer sempre a segunda jogada descrita anteriormente. Explanamos o raciocínio para a posição $(x, x+1)$: o primeiro jogador leva-nos para a posição $(x - 2N, x + N + 1)$ ou para a posição $(x + N, x - 2N + 1)$.
Estando no caso $(x - 2N, x + N + 1)$, é óbvio que podemos retirar $2N$ da segunda pilha: se pudemos retirar $2N$ feijões de uma pilha com $x$ feijões, então podemos retirar $2N$ feijões de uma pilha com $x + N + 1$, e ficamos na posição $(x - N, x + 1 - N)$ que, pela hipótese de indução, é perdedora. Se estivermos no caso $(x + N, x - 2N + 1)$ temos necessariamente que $2N \leq x + 1 \implies N \leq \frac{x+1}{2}$ uma vez que $x-2N+1\geq 0$. Ora $x + N \leq 2N \iff x \leq N \iff \frac{x}{2} \leq \frac{N}{2} \implies \frac{x+1}{2} \leq \frac{N+1}{2} = \frac{N}{2} + \frac{1}{2} \leq \frac{N}{2} + \frac{N}{2} = N$ e portanto podemos fazer a jogada $(x - 2N, x + N + 1) \to (x - N, x + 1 - N)$ que, pela hipótese de indução, é uma posição perdedora.
Concluímos assim que todas as posições da forma $(x, x-1), (x,x), (x, x+1)$ são posições perdedoras. Para mostrarmos que todas as posições perdedoras são desta forma, basta mostrar que qualquer outra posição é uma posição vencedora; de facto, se estamos na posição $(x, y)$ com $x > y+1$ então há um $N \geq 1$ tal que $(x - 2N, y + N)$ é de uma das formas anteriores (em particular tomando $N = \lfloor \frac{x-y}{3}\rfloor$).
De facto, se $x > y + 1$ então $x - y = 3N \vee x - y = 3N-1 \vee x - y = 3N + 1$ para algum $N \geq 1$. Fazendo uma jogada com esse mesmo $N$ na maior pilha dá o pretendido.
Conluímos assim a prova da nossa conjetura, e aplicando ao jogo do enunciado, notamos que a posição inicial é uma posição perdedora, i.e. o João tem uma estratégia vencedora se seguir a estratégia evidenciada pelo nosso raciocínio.
Na consola abaixo podem experimentar jogar contra o computador que, sempre que possível, vai adotar a estratégia vencedora. Para jogar basta carregar no triângulo por cima do código, para que este seja executado. Fazer uma jogada corresponde a dizer quais são os tamanhos com que as pilhas ficam depois de retirarmos os $2N$ feijões de uma das pilhas e posto $N$ na outra.
English version:
I find this post's problem really fun to think about because it is a problem about a game that can actually be played between two players.
Problem statement: suppose you have two stacks of beans, one with 19 and another with 20, on top of a table. John and Mary are to play a game with those beans: each turn, one of them picks $2N$ beans from one of the stacks and puts $N$ of those beans on top of the other stack, where $N$ must be at least 1. For example, in the first turn Mary could pick 10 beans from the stack with 19 (leaving it with 9) and then would put 5 of those in the stack with 20 (leaving it with 25 beans). Mary plays first and the first player that cannot make a move, loses. Can any of the players guarantee a victory?
This game is really simple and it is worth playing it against someone just to get a better feel for the rules. Below you can find a Python console with a script so you can play an interactive session of the game against the computer, which will follow no strategy in particular. To play, just hit the "play" button above the code and write your plays on the console; in your turn all you have to do is write the sizes the stacks will be after you make your move. For example, if your first play is the same as in the problem statement, you would just type "9, 25". By default the computer goes second, but you can change that by replacing the 0 in front of "GOES_FIRST" by a 1.
Solution: we will show that John has a winning strategy. Instead of just proving it, I will try to recreate the train of thought it took me to get there.
Let us represent the sizes of the stacks by a pair $(x, y)$. The first thing to note is that the plays you can make while at $(x, y)$ are the same plays you can make while at $(y, x)$, which means everything we conclude about position $(x, y)$ can also be concluded about position $(y, x)$. Now we follow the first hint and note that if our turn starts and we are at either of $(0,0), (1,0), (0,1)$ or $(1,1)$, we lose, because we cannot remove any beans from either stack. This means that we want to play in such a way that, at a given point, we are at position $(x, y)$ and make a move such that the game state becomes any of those 4 positions, making our opponent lose. From what positions can we make that decisive play?
We can see that it is impossible to reach position $(0, 0)$ given that each move consists of removing some beans from one stack and then adding some beans to the other stack; let us focus on $(1, 0)$. How can one get there? It is fairly easy to see that we can only reach $(1, 0)$ from $(0, 2)$ by making the (obvious) play in the figure:
In a similar fashion we can conclude that to reach the position $(1, 1)$ we must have been at $(3, 0)$ (or $(0, 3)$ of course). At this point, we can already determine the outcome of a game played by two perfect opponents if the game starts at any of the following positions: $(0,0), (1,0), (0,1), (1,1), (2,0), (0,2), (3,0), (0,3)$. We shall keep exploring positions this way and fill a table with our conclusions. We say we have a losing position L if the first player loses a game starting at that position and similarly we say we have a winning position W if the first player wins a game starting at that position. As an example, $(1,0)$ is a losing position. So far, this is what we know:
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline 0 & L & L & W & W & & \\
\hline 1 & L & L & & & & \\
\hline 2 & W & & & & & \\
\hline 3 & W & & & & & \\
\hline 4 & & & & & & \\
\hline 5 & & & & & & \\
\hline
\end{array}
$$
We will keep filling the table up, noticing with relative ease that positions $(2,1)$ and $(2,2)$ are losing positions; after that we conclude that positions $(3,1), (4,0), (4,1), (5,0), (6,0)$ and $(4,2)$ are winning positions, because from all of those we can get to either $(2,1)$ or $(2,2)$. Note that for a position to be a winning position it is enough that there exists one specific move that sends it to a losing position. For example, from $(4,0)$ we can go to $(2,1)$ or $(2,0)$. If we go to $(2,1)$ we win, because $(2,1)$ is an L position, but if we go to $(2, 0)$ we just offered a victory to our opponent. On the other hand, for a position to be a losing position it is necessary that all positions that derive from it give the victory to our opponent, i.e. player $A$ is in a losing position if, regardless of its move, player $B$ receives a winning position.
If we fill the table with our new findings we get:
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline 0 & L & L & W & W & W & W \\
\hline 1 & L & L & L & W & W & \\
\hline 2 & W & L & L & & W & \\
\hline 3 & W & W & & & & \\
\hline 4 & W & W & W & & & \\
\hline 5 & W & & & & & \\
\hline
\end{array}
$$
At this point we could start to notice a pattern that I try to make more explicit in the following figure:
Hopefully the red lines are hinting at a possible conjecture: the losing positions are positions of the form $(x, x+1), (x,x)$ and $(x+1, x)$.
Before we try to prove our conjecture we will check positions $(3,2), (3,3), (2,3)$. If those positions are also L positions, then our conjecture gains strength and it will make sense to test it.
If we are at $(3,2)$ we can only go to $(4,0)$ or $(1,3)$ which are both W positions, hence $(3,2)$ (and therefore $(2,3)$ as well) is a losing position. We can also verify that $(3,3)$ is an L position:
We could keep on going and fill the whole table, but at this point I thought it would be worth it to try and prove the conjecture. If it turns out that the conjecture is false, then maybe we might get some more insight into what other positions are also losing positions.
Conjecture: a position $(x, y)$ is an L position if and only if $y \in \{x-1, x, x+1\}$. That is, every L position is of the form $(x, x-1), (x,x)$ or $(x, x+1)$ and every position of that form is an L position.
We start by proving that every position of the form stated is a losing position by induction on the size of the first pile. The base case is for the positions $(1,0),(1,1), (1,2)$ which is true by our table. For the inductive step, we assume that for any $k < x$ (with $x > 1$) all three positions $(k, k-1), (k,k), (k, k+1)$ are losing positions and proceed to show that it implies the positions $(x,x-1), (x,x)$ and $(x, x+1)$ are also losing positions; for that, we will show that regardless of the move made, the opponent can always reply in such a way that we go back to the red zone. We recall that the case $(x, x-1)$ comes for free by the induction hypothesis, given that $(x, x-1) \approx (x-1, x) = (k, k+1), k = x-1$ is an L position.
It should also be noted that if we could go from position $(x, y)$ to $(x - 2N, y + N)$, then if we also assume that $y + N \geq 2N$ then the opponent can reply with $(x - 2N, y+N) \to ((x-2N) + N, (y+N) - 2N) = (x - N, y - N)$, i.e. the final outcome of the two moves is that the difference between the stacks is the same ($(x-N)-(y-N) = x-y$) but both piles got smaller. We are now left with showing that from both the case $(x,x)$ and $(x, x+1)$ we can play like we described above. We will show how to prove it for the position $(x, x+1)$: the first player can take us to $(x - 2N, x + N + 1)$ or $(x + N, x - 2N + 1)$.
If we are at $(x - 2N, x + N + 1)$ it is obvious that we can take $2N$ beans from the second pile: after all, if we could take $2N$ beans from a stack with $x$ beans we can take $2N$ beans from a stack with $x + N + 1$ beans, leaving us at $(x - N, x + 1 - N)$ which, by the induction hypothesis, is a losing position. If we are at $(x + N, x - 2N + 1)$ we necessarily have $2N \leq x + 1 \implies N \leq \frac{x+1}{2}$ because $x-2N+1\geq 0$. Now, $x + N \leq 2N \iff x \leq N \iff \frac{x}{2} \leq \frac{N}{2} \implies \frac{x+1}{2} \leq \frac{N+1}{2} = \frac{N}{2} + \frac{1}{2} \leq \frac{N}{2} + \frac{N}{2} = N$ and so we can make the move $(x - 2N, x + N + 1) \to (x - N, x + 1 - N)$ which, by the induction hypothesis, is a losing position.
We conclude that all positions of the form $(x, x-1), (x,x), (x,x+1)$ are losing positions. To show all losing positions are of that form it suffices to show that every other position is a winning position. As a matter of fact, if we are at $(x, y)$ with $x > y+1$ then there is an $N \geq 1$ such that $(x - 2N, y + N)$ is of the previous form (in particular taking $N = \lfloor \frac{x-y}{3}\rfloor$).
Assuming $x > y + 1$ then $x - y = 3N \vee x - y = 3N-1 \vee x - y = 3N + 1$ for some $N \geq 1$. Making a play with said $N$ works as intended.
We conclude the proof of our conjecture and we see that the position in the problem statement is a losing position, i.e. John has a winning strategy if he follows the strategy outlined in our proof.
In the console below you can try playing against a computer that will follow the winning strategy. To play, press the triangle "play" button to execute it. Making a play corresponds to writing the sizes of the stacks after moving the beans according to the rules
Let me know what you think!
-RGS
O problema deste post foi-me colocado na primeira edição das Jornadas de Matemática da Faculdade de Ciências da Universidade do Porto, numa sessão de jogos matemáticos! O problema é particularmente engraçado porque assenta num jogo que se pode jogar entre duas pessoas.
Problema: suponha-se que sobre uma mesa estão dois montes de feijões, um com 19 feijões e outro com 20 feijões. A Ana e o João vão jogar um jogo com esses montes de feijões: cada jogada consiste em retirar $2N$ feijões de um monte e pôr $N $ feijões no outro monte. Assim, na primeira jogada podemos, por exemplo, tirar 10 feijões do monte com 19, deixando-o com 9, e pôr 5 feijões no monte com 20, deixando-o com 25. A Ana vai ser a primeira a jogar e perde quem não puder fazer nenhuma jogada válida. Será que algum dos jogadores consegue garantir a sua vitória?
Este jogo tem regras muito simples e é bastante engraçado, vale a pena jogá-lo com alguém só para entender realmente como funciona a dinâmica do jogo. Incluímos aqui uma janela para que se possa jogar o jogo contra um jogador virtual que não segue nenhuma estratégia em particular, exceto quando, perto do fim, ele reconhece uma jogada vencedora. Para jogar há que carregar no triângulo por cima do código e escrever as nossas jogadas na parte da direita. "Fazer uma jogada" corresponde a escrever os novos tamanhos das pilhas depois da alteração que escolhermos fazer; por exemplo, se fizermos a jogada descrita no enunciado, escreveríamos "9, 25". Por defeito o computador joga pelo João; para alterar isto basta escrever um $1$ em vez de $0$ à frente de "GOES_FIRST".
Solução: vamos mostrar que o João tem uma estratégia vencedora. Em vez de apresentar apenas a prova de que o João consegue sempre ganhar, vou tentar recriar todo o meu raciocínio que levou a esta conclusão.
Representemos o número de feijões nos montes por um par $(x,y) $. A primeira coisa óbvia a notar é que as jogadas que se podem fazer em $(x,y) $ também se podem fazer em $(y,x) $, portanto tudo o que concluirmos sobre a posição $(x,y) $ aplica-se à posição $(y,x) $ e vice-versa. Agora começamos por notar que, se for a nossa vez de jogar e estivermos em alguma das posições $(0,0), (1,0), (0,1), (1,1)$, perdemos... O que quer dizer que o nosso objetivo é estar numa posição qualquer $(x,y)$ e jogar de modo a passarmos ao nosso adversário uma das quatro posições anteriores. De onde é que podem surgir essas jogadas?
Notamos que é impossível chegar à posição $(0,0)$, já que em cada jogada tiramos feijões de um monte e pomos feijões no outro, portanto há sempre um monte que tem mais do que $0$ feijões; como é que podemos chegar a $(1,0)$? É fácil de ver que só a posição $(0,2)$ pode dar origem à posição $(1,0)$, da maneira (óbvia) que vemos na figura:
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline 0 & P & P & V & V & & \\
\hline 1 & P & P & & & & \\
\hline 2 & V & & & & & \\
\hline 3 & V & & & & & \\
\hline 4 & & & & & & \\
\hline 5 & & & & & & \\
\hline
\end{array}
$$
Continuamos a preencher a tabela, concluindo com alguma facilidade que as posições $(2,1)$ e $(2,2)$ são perdedoras; de seguida, podemos concluir que as posições $(3,1), (4,0), (4,1), (5,0), (6,0)$ e $(4,2)$ são vencedoras, porque todas elas podem chegar a $(2,1)$ ou $(2,2)$. Note-se que para uma posição ser vencedora basta que uma jogada sobre essa posição leve a uma posição perdedora. Por exemplo, na posição $(4,0)$ podemos passar para $(2,1)$ ou para $(2,0)$. Se passarmos para $(2,1)$ ganhamos, porque $(2,1)$ é uma posição P, mas se passarmos para $(2,0)$ acabámos de dar a vitória ao nosso adversário.
Por outro lado, para uma posição ser perdedora é necessário que todas as jogadas sobre essa posição dêem a vitória ao adversário, i.e. o jogador A só está numa posição P se, independentemente do que fizer, o jogador B fique numa posição V.
Preenchendo a tabela com as nossas novas conclusões obtemos
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline 0 & P & P & V & V & V & V \\
\hline 1 & P & P & P & V & V & \\
\hline 2 & V & P & P & & V & \\
\hline 3 & V & V & & & & \\
\hline 4 & V & V & V & & & \\
\hline 5 & V & & & & & \\
\hline
\end{array}
$$
Neste ponto podemos começar a notar que um certo padrão parece emergir, que evidencio na tabela seguinte:
Antes de testarmos essa hipótese, vamos ainda preencher as posições $(3,2), (3,3), (2,3)$. Se estas também forem posições P, então a nossa conjetura ganha relevância e vale a pena testá-la.
Notamos que, estando na posição $(3,2)$, apenas conseguimos ir para as posições $(1,3)$ e $(4,0)$, que são as duas posições $V$, logo $(3,2)$ (e por conseguinte $(2,3)$) é uma posição P. De modo análogo concluímos que $(3,3)$ é uma posição P:
Poderíamos continuar a preencher a tabela, mas neste ponto já vale a pena tentar provar a nossa conjetura; não porque temos a certeza absoluta de que ela é verdade, mas porque se não for, somos capazes de compreender melhor que outro tipo de posições também são posições P.
Conjetura: Uma posição $(x,y)$ é uma posição P se e só se $y \in \{x-1, x, x+1\}$. Isto é, toda a posição P é da forma $(x,x-1),(x,x)$ ou $(x,x+1)$ e toda a posição dessa forma é uma posição P.
Começamos por provar que todas as posições da forma anterior são perdedoras, por indução no tamanho da primeira pilha. O caso base é para as posições $(1,0), (1,1)$ e $(1,2)$, que é trivialmente verdade pela tabela que já construímos. Supomos agora que as posições $(k,k-1), (k,k)$ e $(k,k+1)$ são todas perdedoras, para $k < x, x>1$, e mostramos que isso implica que as três posições $(x,x-1), (x,x), (x,x+1)$ são perdedoras também; para tal, verificaremos que, independentemente da jogada feita a partir dessas posições, o adversário consegue sempre jogar de maneira tal que voltamos a estar numa das posições na zona a vermelho. Relembramos ainda que o caso $(x, x-1)$ é dado de graça pela hipótese de indução, uma vez que $(x, x-1) \approx (x-1, x) = (k, k+1), k=x-1$ é uma posição perdedora pela hipótese de indução.
Note-se que, se da posição $(x, y)$ pudémos fazer a jogada $(x - 2N, y + N)$, então assumindo que $y + N \geq 2N$ podemos fazer a jogada $(x - 2N, y+N) \to ((x-2N) + N, (y+N) - 2N) = (x - N, y - N)$, i.e. mantemos a diferença entre os tamanhos das pilhas ($(x-N)-(y-N) = x-y$) mas diminuimos o tamanho total das pilhas. Basta agora notar que tanto no caso $(x,x)$ como no caso $(x,x+1)$ podemos fazer sempre a segunda jogada descrita anteriormente. Explanamos o raciocínio para a posição $(x, x+1)$: o primeiro jogador leva-nos para a posição $(x - 2N, x + N + 1)$ ou para a posição $(x + N, x - 2N + 1)$.
Estando no caso $(x - 2N, x + N + 1)$, é óbvio que podemos retirar $2N$ da segunda pilha: se pudemos retirar $2N$ feijões de uma pilha com $x$ feijões, então podemos retirar $2N$ feijões de uma pilha com $x + N + 1$, e ficamos na posição $(x - N, x + 1 - N)$ que, pela hipótese de indução, é perdedora. Se estivermos no caso $(x + N, x - 2N + 1)$ temos necessariamente que $2N \leq x + 1 \implies N \leq \frac{x+1}{2}$ uma vez que $x-2N+1\geq 0$. Ora $x + N \leq 2N \iff x \leq N \iff \frac{x}{2} \leq \frac{N}{2} \implies \frac{x+1}{2} \leq \frac{N+1}{2} = \frac{N}{2} + \frac{1}{2} \leq \frac{N}{2} + \frac{N}{2} = N$ e portanto podemos fazer a jogada $(x - 2N, x + N + 1) \to (x - N, x + 1 - N)$ que, pela hipótese de indução, é uma posição perdedora.
Concluímos assim que todas as posições da forma $(x, x-1), (x,x), (x, x+1)$ são posições perdedoras. Para mostrarmos que todas as posições perdedoras são desta forma, basta mostrar que qualquer outra posição é uma posição vencedora; de facto, se estamos na posição $(x, y)$ com $x > y+1$ então há um $N \geq 1$ tal que $(x - 2N, y + N)$ é de uma das formas anteriores (em particular tomando $N = \lfloor \frac{x-y}{3}\rfloor$).
De facto, se $x > y + 1$ então $x - y = 3N \vee x - y = 3N-1 \vee x - y = 3N + 1$ para algum $N \geq 1$. Fazendo uma jogada com esse mesmo $N$ na maior pilha dá o pretendido.
Conluímos assim a prova da nossa conjetura, e aplicando ao jogo do enunciado, notamos que a posição inicial é uma posição perdedora, i.e. o João tem uma estratégia vencedora se seguir a estratégia evidenciada pelo nosso raciocínio.
Na consola abaixo podem experimentar jogar contra o computador que, sempre que possível, vai adotar a estratégia vencedora. Para jogar basta carregar no triângulo por cima do código, para que este seja executado. Fazer uma jogada corresponde a dizer quais são os tamanhos com que as pilhas ficam depois de retirarmos os $2N$ feijões de uma das pilhas e posto $N$ na outra.
English version:
I find this post's problem really fun to think about because it is a problem about a game that can actually be played between two players.
Problem statement: suppose you have two stacks of beans, one with 19 and another with 20, on top of a table. John and Mary are to play a game with those beans: each turn, one of them picks $2N$ beans from one of the stacks and puts $N$ of those beans on top of the other stack, where $N$ must be at least 1. For example, in the first turn Mary could pick 10 beans from the stack with 19 (leaving it with 9) and then would put 5 of those in the stack with 20 (leaving it with 25 beans). Mary plays first and the first player that cannot make a move, loses. Can any of the players guarantee a victory?
This game is really simple and it is worth playing it against someone just to get a better feel for the rules. Below you can find a Python console with a script so you can play an interactive session of the game against the computer, which will follow no strategy in particular. To play, just hit the "play" button above the code and write your plays on the console; in your turn all you have to do is write the sizes the stacks will be after you make your move. For example, if your first play is the same as in the problem statement, you would just type "9, 25". By default the computer goes second, but you can change that by replacing the 0 in front of "GOES_FIRST" by a 1.
Solution: we will show that John has a winning strategy. Instead of just proving it, I will try to recreate the train of thought it took me to get there.
Let us represent the sizes of the stacks by a pair $(x, y)$. The first thing to note is that the plays you can make while at $(x, y)$ are the same plays you can make while at $(y, x)$, which means everything we conclude about position $(x, y)$ can also be concluded about position $(y, x)$. Now we follow the first hint and note that if our turn starts and we are at either of $(0,0), (1,0), (0,1)$ or $(1,1)$, we lose, because we cannot remove any beans from either stack. This means that we want to play in such a way that, at a given point, we are at position $(x, y)$ and make a move such that the game state becomes any of those 4 positions, making our opponent lose. From what positions can we make that decisive play?
We can see that it is impossible to reach position $(0, 0)$ given that each move consists of removing some beans from one stack and then adding some beans to the other stack; let us focus on $(1, 0)$. How can one get there? It is fairly easy to see that we can only reach $(1, 0)$ from $(0, 2)$ by making the (obvious) play in the figure:
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline 0 & L & L & W & W & & \\
\hline 1 & L & L & & & & \\
\hline 2 & W & & & & & \\
\hline 3 & W & & & & & \\
\hline 4 & & & & & & \\
\hline 5 & & & & & & \\
\hline
\end{array}
$$
We will keep filling the table up, noticing with relative ease that positions $(2,1)$ and $(2,2)$ are losing positions; after that we conclude that positions $(3,1), (4,0), (4,1), (5,0), (6,0)$ and $(4,2)$ are winning positions, because from all of those we can get to either $(2,1)$ or $(2,2)$. Note that for a position to be a winning position it is enough that there exists one specific move that sends it to a losing position. For example, from $(4,0)$ we can go to $(2,1)$ or $(2,0)$. If we go to $(2,1)$ we win, because $(2,1)$ is an L position, but if we go to $(2, 0)$ we just offered a victory to our opponent. On the other hand, for a position to be a losing position it is necessary that all positions that derive from it give the victory to our opponent, i.e. player $A$ is in a losing position if, regardless of its move, player $B$ receives a winning position.
If we fill the table with our new findings we get:
$$\begin{array}{|c|c|c|c|c|c|c|}
\hline & 0 & 1 & 2 & 3 & 4 & 5 \\
\hline 0 & L & L & W & W & W & W \\
\hline 1 & L & L & L & W & W & \\
\hline 2 & W & L & L & & W & \\
\hline 3 & W & W & & & & \\
\hline 4 & W & W & W & & & \\
\hline 5 & W & & & & & \\
\hline
\end{array}
$$
At this point we could start to notice a pattern that I try to make more explicit in the following figure:
Before we try to prove our conjecture we will check positions $(3,2), (3,3), (2,3)$. If those positions are also L positions, then our conjecture gains strength and it will make sense to test it.
If we are at $(3,2)$ we can only go to $(4,0)$ or $(1,3)$ which are both W positions, hence $(3,2)$ (and therefore $(2,3)$ as well) is a losing position. We can also verify that $(3,3)$ is an L position:
We could keep on going and fill the whole table, but at this point I thought it would be worth it to try and prove the conjecture. If it turns out that the conjecture is false, then maybe we might get some more insight into what other positions are also losing positions.
Conjecture: a position $(x, y)$ is an L position if and only if $y \in \{x-1, x, x+1\}$. That is, every L position is of the form $(x, x-1), (x,x)$ or $(x, x+1)$ and every position of that form is an L position.
We start by proving that every position of the form stated is a losing position by induction on the size of the first pile. The base case is for the positions $(1,0),(1,1), (1,2)$ which is true by our table. For the inductive step, we assume that for any $k < x$ (with $x > 1$) all three positions $(k, k-1), (k,k), (k, k+1)$ are losing positions and proceed to show that it implies the positions $(x,x-1), (x,x)$ and $(x, x+1)$ are also losing positions; for that, we will show that regardless of the move made, the opponent can always reply in such a way that we go back to the red zone. We recall that the case $(x, x-1)$ comes for free by the induction hypothesis, given that $(x, x-1) \approx (x-1, x) = (k, k+1), k = x-1$ is an L position.
It should also be noted that if we could go from position $(x, y)$ to $(x - 2N, y + N)$, then if we also assume that $y + N \geq 2N$ then the opponent can reply with $(x - 2N, y+N) \to ((x-2N) + N, (y+N) - 2N) = (x - N, y - N)$, i.e. the final outcome of the two moves is that the difference between the stacks is the same ($(x-N)-(y-N) = x-y$) but both piles got smaller. We are now left with showing that from both the case $(x,x)$ and $(x, x+1)$ we can play like we described above. We will show how to prove it for the position $(x, x+1)$: the first player can take us to $(x - 2N, x + N + 1)$ or $(x + N, x - 2N + 1)$.
If we are at $(x - 2N, x + N + 1)$ it is obvious that we can take $2N$ beans from the second pile: after all, if we could take $2N$ beans from a stack with $x$ beans we can take $2N$ beans from a stack with $x + N + 1$ beans, leaving us at $(x - N, x + 1 - N)$ which, by the induction hypothesis, is a losing position. If we are at $(x + N, x - 2N + 1)$ we necessarily have $2N \leq x + 1 \implies N \leq \frac{x+1}{2}$ because $x-2N+1\geq 0$. Now, $x + N \leq 2N \iff x \leq N \iff \frac{x}{2} \leq \frac{N}{2} \implies \frac{x+1}{2} \leq \frac{N+1}{2} = \frac{N}{2} + \frac{1}{2} \leq \frac{N}{2} + \frac{N}{2} = N$ and so we can make the move $(x - 2N, x + N + 1) \to (x - N, x + 1 - N)$ which, by the induction hypothesis, is a losing position.
We conclude that all positions of the form $(x, x-1), (x,x), (x,x+1)$ are losing positions. To show all losing positions are of that form it suffices to show that every other position is a winning position. As a matter of fact, if we are at $(x, y)$ with $x > y+1$ then there is an $N \geq 1$ such that $(x - 2N, y + N)$ is of the previous form (in particular taking $N = \lfloor \frac{x-y}{3}\rfloor$).
Assuming $x > y + 1$ then $x - y = 3N \vee x - y = 3N-1 \vee x - y = 3N + 1$ for some $N \geq 1$. Making a play with said $N$ works as intended.
We conclude the proof of our conjecture and we see that the position in the problem statement is a losing position, i.e. John has a winning strategy if he follows the strategy outlined in our proof.
In the console below you can try playing against a computer that will follow the winning strategy. To play, press the triangle "play" button to execute it. Making a play corresponds to writing the sizes of the stacks after moving the beans according to the rules
Let me know what you think!
-RGS
Problem #06 - stacks of beans
Reviewed by Unknown
on
February 10, 2018
Rating:
Reviewed by Unknown
on
February 10, 2018
Rating:
No comments: