There are $100$ glasses, with $101,102,...,200$ cents.Two players play next game. In every move they can take some cents from one glass, but after move should be different number of cents in every glass. Who will win with right strategy?
Problem
Source: St Petersburg Olympiad 2013, Grade 9, P4
Tags: combinatorics
13.10.2017 18:34
Here I assume the glasses can be empty and that the player who makes the last move wins. We'll call a pair of glasses with $2k$ and $2k+1$ coins good. It is not hard to see that the first player wins with the following strategy: - In the first turn, remove $100$ cents from the glass containing $200$. Now the glasses can be arranged into $50$ good pairs: $(100,101),(102,103),\ldots,(198,199)$. - In subsequent turns, the first player just maintains that there are always $50$ good pairs. For example, if the second player moves $123\to 50$, the first player moves $122\to 51$, essentially changing the good pair $(122,123)$ to $(50,51)$. Clearly the first player can always play, and as the game always end, the first player must win.
17.10.2017 19:23
I think your solution is wrong. The second player can play with this strategy too
17.10.2017 20:34
Eagleka94 wrote: I think your solution is wrong. The second player can play with this strategy too No, this method doesn't work for the second player. - First, the initial position of $101,102,\ldots,200$ cannot be paired into $50$ good pairs. Note that a good pair is $(2k,2k+1)$ and not $(2k-1,2k)$. - If you were to define a good pair as a pair of the form $(2k-1,2k)$ then the first player can reduce a glass to $0$ cents and the second player cannot create a glass with $-1$ cents.