2024 AIME I Problems/Problem 3
Contents
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 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 , Alice will take
, Bob will take one, and Alice will take the final one. If there are
, Alice will just remove all
at once. If there are
, no matter what Alice does, Bob can take the final coins in one try. Notice that Alice wins if there are
,
, or
coins left. Bob wins if there are
or
coins left.
After some thought, you may realize that there is a strategy for Bob. If there is n is a multiple of , then Bob will win. The reason for this is the following: Let's say there are a multiple of
coins remaining in the stack. If Alice takes
, Bob will take
, and there will still be a multiple of
. If Alice takes
, Bob will take
, and there will still be a multiple of
. This process will continue until you get
coins left. For example, let's say there are
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
left. This will continue until there are
coins left, and Bob will end up winning.
After some more experimentation, you'll realize that any number that is congruent to mod
will also work. This is because Bob can do the same strategy, and when there are
coins left, Alice is forced to take
and Bob takes the final coin. For example, let's say there are
coins. If Alice takes
, Bob will take
. If Alice takes
, Bob will take
. So after they each make a turn, the number will always be equal to
mod
. Eventually, there will be only
coins remaining, and we've established that Alice will simply take
and Bob will take the final coin.
So we have to find the number of numbers less than or equal to that are either congruent to
mod
or
mod
. There are
numbers in the first category:
. For the second category, there are
numbers.
. So the answer is
~lprado
Solution 2
We will use winning and losing positions.
coin:
coins:
coins:
coins:
coins:
coin:
coins:
coins:
coins:
coins:
coin:
coins:
coins:
coins:
coins:
We can see that losing positions occur when is congruent to
and winning positions occur otherwise. As
ranges from
to
,
of these values are losing positions where Bob will win. As
ranges from
to
,
is the only value where Bob wins. Therefore, the answer is
~alexanderruan
See also
2024 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.