2024 AIME I Problems/Problem 3

Problem

Alice and Bob play the following game. A stack of n tokens lies before them. The players take turns with Alice going first. On each turn, the player removes either 1 token or 4 tokens from the stack. Whoever removes the last token wins. Find the number of positive integers n less than or equal to 2024 for which there exists a strategy for Bob that guarantees that Bob will win the game regardless of Alice's play.

Solution 1

Let's first try some experimentation. Alice obviously wins if there is one coin. She will just take it and win. If there are 2 remaining, then Alice will take one and then Bob will take one, so Bob wins. If there are $3$ , Alice will take $1$ , Bob will take one, and Alice will take the final one. If there are $4$ , Alice will just remove all $4$ at once. If there are $5$ , no matter what Alice does, Bob can take the final coins in one try. Notice that Alice wins if there are $1$ , $3$ , or $4$ coins left. Bob wins if there are $2$ or $5$ coins left.

After some thought, you may realize that there is a strategy for Bob. If there is n is a multiple of $5$ , then Bob will win. The reason for this is the following: Let's say there are a multiple of $5$ coins remaining in the stack. If Alice takes $1$ , Bob will take $4$ , and there will still be a multiple of $5$ . If Alice takes $4$ , Bob will take $1$ , and there will still be a multiple of $5$ . This process will continue until you get $0$ coins left. For example, let's say there are $205$ coins. No matter what Alice does, Bob can simply just do the complement. After each of them make a turn, there will always be a multiple of $5$ left. This will continue until there are $5$ coins left, and Bob will end up winning.

After some more experimentation, you'll realize that any number that is congruent to $2$ mod $5$ will also work. This is because Bob can do the same strategy, and when there are $2$ coins left, Alice is forced to take $1$ and Bob takes the final coin. For example, let's say there are $72$ coins. If Alice takes $1$ , Bob will take $4$ . If Alice takes $4$ , Bob will take $1$ . So after they each make a turn, the number will always be equal to $2$ mod $5$ . Eventually, there will be only $2$ coins remaining, and we've established that Alice will simply take $1$ and Bob will take the final coin.

So we have to find the number of numbers less than or equal to $2024$ that are either congruent to $0$ mod $5$ or $2$ mod $5$ . There are $404$ numbers in the first category: $5, 10, 15, \dots, 2020$ . For the second category, there are $405$ numbers. $2, 7, 12, 17, \dots, 2022$ . So the answer is $404 + 405 = \boxed{809}$

~lprado

Page

Toolbox

Search

2024 AIME I Problems/Problem 3

Problem

Solution 1