Problem:
Alice and Bob play the following game. A stack of tokens lies before them. The players take turns with Alice going first. On each turn, the player removes either token or tokens from the stack. Whoever removes the last token wins. Find the number of positive integers less than or equal to for which there exists a strategy for Bob that guarantees that Bob will win the game regardless of Alice's play.
Solution:
Assume that both Alice and Bob play optimally. Then Alice will win if . If , then Alice must remove token, leaving a winning position for Bob. If , then Alice must remove token, leaving a losing position for Bob, so Alice will win. If , then Alice can take all the tokens and win. If , then whether Alice takes token or tokens, she leaves a winning position for Bob. Thus for , if , then the player presented with that position can win, but if , then the player presented with that position will lose if the other player plays optimally.
By induction, Alice has a winning strategy exactly when positive integer is congruent to . Indeed, suppose this is true for all positive integers less than some . If , then a player presented with that position can remove token and present the opponent with a losing position, with the number of tokens congruent to , respectively. If , then a player presented with that position can remove tokens and present the opponent with a losing position, with the number of tokens congruent to . On the other hand, if , then removing or tokens will present the opponent with a number of tokens congruent to , from which the opponent can win. Thus Alice can guarantee winning the game if , and Bob can guarantee winning if .
The number of positive integers less than or equal to congruent to or is
The problems on this page are the property of the MAA's American Mathematics Competitions