There are three piles of tokens on the table: the first contains , the second and the third one tokens, and . Two players and take turns moving the tokens around. Player goes first. For each move, the active player first chooses two piles and then moves at least one token from the pile with fewer tokens into the pile containing more tokens. If the numbers of tokens in the two chosen piles are equal, then the player moves at least one token from any of them onto the other. A player wins if there is only one pile remaining after their move. Who has the winning strategy for different values of and ?
Solution
If , then player has the winning strategy, otherwise player has the winning strategy.
First, assume that . Then the two piles with the smallest number of tokens contain the same amount. In this case, player can ensure that the situation remains like that every time he makes his move, whereas every time makes his move the pile with the least number of tokens contains less tokens than the remaining piles. Indeed, player always has to move at least one token from one of the smallest two piles onto one of the other piles. Player can then choose the biggest two piles which necessarily contain more tokens than the smallest pile, and distribute the tokens between the two so that the smallest two piles after his turn contain the same number of tokens. The game will end when the smallest two piles are emptied, which can only happen after completes his turn. Hence, can always win.
Now, assume that . In this case should move tokens from the pile with tokens onto the pile with tokens. After his move the smallest two piles will contain tokens each. The situation is now the same as above, except this time is the first player to continue. Hence, has the winning strategy in this case.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.