MathDB
2023 Fall Theme p3B

Source:

December 23, 2023
2023FAlLthemeCombo

Problem Statement

Evin and Jerry are playing a game with a pile of marbles. On each players' turn, they can remove 22, 33, 77, or 88 marbles. If they can’t make a move, because there's 00 or 11 marble left, they lose the game. Given that Evin goes first and both players play optimally, for how many values of nn from 11 to 14341434 does Evin lose the game?
Proposed by Evin Liang
Solution. 573\boxed{573} Observe that no matter how many marbles a one of them removes, the next player can always remove marbles such that the total number of marbles removed is 1010. Thus, when the number of marbles is a multiple of 1010, the first player loses the game. We analyse this game based on the number of marbles modulo 1010:
If the number of marbles is 00 modulo 1010, the first player loses the game
If the number of marbles is 22, 33, 77, or 88 modulo 1010, the first player wins the game by moving to 00 modulo 10
If the number of marbles is 55 modulo 1010, the first player loses the game because every move leads to 22, 33, 77, or 88 modulo 1010
In summary, the first player loses if it is 00 mod 5, and wins if it is 22 or 33 mod 55. Now we solve the remaining cases by induction. The first player loses when it is 11 modulo 55 and wins when it is 44 modulo 55. The base case is when there is 11 marble, where the first player loses because there is no move. When it is 44 modulo 55, then the first player can always remove 33 marbles and win by the inductive hypothesis. When it is 11 modulo 55, every move results in 33 or 44 modulo 55, which allows the other player to win by the inductive hypothesis. Thus, Evin loses the game if n is 00 or 11 modulo 55. There are 573\boxed{573} such values of nn from 11 to 14341434.
Back to ProblemsView on AoPS