There are 2009 boxes numbered from 1 to 2009, some of which contain stones. Two players, $ A$ and $ B$, play alternately, starting with $ A$. A move consists in selecting a non-empty box $ i$, taking one or more stones from that box and putting them in box $ i + 1$. If $ i = 2009$, the selected stones are eliminated. The player who removes the last stone wins a) If there are 2009 stones in the box 2 and the others are empty, find a winning strategy for either player. b) If there is exactly one stone in each box, find a winning strategy for either player.
Problem
Source: Problem 3, Centroamerican Olympiad 2009
Tags: combinatorics proposed, combinatorics
09.10.2009 17:42
An odd box is, for example, the box 17, the box 35,... For the $ a$ part, the player $ B$ win because he allways can play such that all the stones, after he play, will be in even boxes, and then the player $ A$ cannot win, and so like the game is finite, the player $ B$ must win. For the $ b$ part, I use the same strategy, it is that the player who can play such that, after the other player plays, the number of boxes odd and nonempty will be odd, and then is at least one, so he cannot lost. I will prove that the player $ A$ win. Let $ k$ be the number of odd boxes wich ar nonempty in any moment. In the begining of the game there are 1005 boxes that are nonempty and odd. The first play of the player $ A$ is select one stone of the box 2009. Now $ k$ is even. Then the player B can play of two ways: 1- If he select $ x$ stones from the box $ 2y$, then in the next play the player $ A$ select $ x$ stones from the box $ 2y + 1$ (it is easy to see that it allways is possible). 2- If he select $ 1$ stone from the box $ 2y + 1$, then in the next play the player $ A$ select $ 1$ stone from the box $ 2z + 1$. We see that like in the begining there is one stone in each box, after $ B$ plays, the number $ k$ is allways odd if $ B$ played 2 (so $ z$ allways exist). After $ A$ plays the number $ k$ is even and in each odd box the number of stones is 0 or 1. So the player $ A$ allways can play, and then he must win.
09.10.2009 19:33
gilcu3 wrote: Let $ k$ be the number of odd boxes wich ar nonempty in any moment. In the begining of the game there are 1005 boxes that are nonempty and odd. The first play of the player $ A$ is select one stone of the box 2009. Now $ k$ is even. Then the player B can play of two ways: 1- If he select $ x$ stones from the box $ 2y$, then in the next play the player $ A$ select $ x$ stones from the box $ 2y + 1$ (it is easy to see that it allways is possible). if the first play of B is 1., then k is even after the play of A
09.10.2009 19:41
Yes, I proved that after each play of $ A$, the number $ k$ is even.
08.08.2021 09:52
Let a stone in box $i$ have value $i$ and let the sum of all the values of the stones be denoted as $E$ (assume that there is some box of value 2010 for which no stone can be removed). Notice that after each move, $E$ increases by $1$ and thus changes parity. a) Notice that $E$ is initially even. Thus when $A$ operates, $E$ goes from even to odd and $B$ goes from odd to even. Clearly, $A$ cannot perform the operation of putting the last stone in box 2010 since such a move would be odd to even. b) Notice that the initial $E$ is now odd, thus when $A$ operates, $E$ goes from odd to even and $E$ goes from even to odd. Making $A$ win this time.