Difference between revisions of "2024 AIME I Problems/Problem 3"
Numerophile (talk | contribs) (→Solution 3) |
|||
Line 91: | Line 91: | ||
Putting all cases together, the answer is <math>404 + 405 = \boxed{\textbf{(809) }}</math>. | Putting all cases together, the answer is <math>404 + 405 = \boxed{\textbf{(809) }}</math>. | ||
+ | |||
+ | ==Solution 4 (Grundy Values)== | ||
+ | |||
+ | Since the game Alice and Bob play is impartial (the only difference between player 1 and player 2 is that player 1 goes first (note that games like chess are not impartial because each player can only move their own pieces)), we can use the Sprague-Grundy Theorem to solve this problem. We will use induction to calculate the Grundy Values for this game. | ||
+ | |||
+ | We claim that heaps of size congruent to <math>0,2 \bmod{5}</math> will be in outcome class <math>\mathcal{P}</math> (win for player 2 = Bob), and heaps of size equivalent to <math>1,3,4 \bmod{5}</math> will be in outcome class <math>\mathcal{N}</math> (win for player 1 = Alice). Note that the mex (minimal excludant) of a set of nonnegative integers is the least nonnegative integer not in the set. e.g. mex<math>(1, 2, 3) = 0</math> and mex<math>(0, 1, 2, 4) = 3</math>. | ||
+ | |||
+ | |||
+ | <math>\text{heap}(0) = \{\} = *\text{mex}(\emptyset) = 0</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(1) = \{0\} = *\text{mex}(0) = *</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(2) = \{*\} = *\text{mex}(1) = 0</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(3) = \{0\} = *\text{mex}(0) = *</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(4) = \{0, *\} = *\text{mex}(0, 1) = *2</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(5) = \{*, *2\} = *\text{mex}(1, 2) = 0</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(6) = \{0, 0\} = *\text{mex}(0, 0) = *</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(7) = \{*, *\} = *\text{mex}(1, 1) = 0</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(8) = \{*2, 0\} = *\text{mex}(0, 2) = *</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(9) = \{0, *\} = *\text{mex}(0, 1) = *2</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(10) = \{*, *2\} = *\text{mex}(1, 2) = 0</math> | ||
+ | |||
+ | |||
+ | We have proven the base case. We will now prove the inductive hypothesis: If <math>n \equiv 0 \bmod{5}</math>, <math>\text{heap}(n) = 0</math>, <math>\text{heap}(n+1) = *</math>, <math>\text{heap}(n+2) = 0</math>, <math>\text{heap}(n+3) = *</math>, and <math>\text{heap}(n+4) = *2</math>, then <math>\text{heap}(n+5) = 0</math>, <math>\text{heap}(n+6) = *</math>, <math>\text{heap}(n+7) = 0</math>, <math>\text{heap}(n+8) = *</math>, and <math>\text{heap}(n+9) = *2</math>. | ||
+ | |||
+ | |||
+ | <math>\text{heap}(n+5) = \{\text{heap}(n+1), \text{heap}(n+4)\} = \{*, *2\} = *\text{mex}(1, 2) = 0</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(n+6) = \{\text{heap}(n+2), \text{heap}(n+5)\} = \{0, 0\} = *\text{mex}(0, 0) = *</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(n+7) = \{\text{heap}(n+3), \text{heap}(n+6)\} = \{*, *\} = *\text{mex}(1, 1) = 0</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(n+8) = \{\text{heap}(n+4), \text{heap}(n+7)\} = \{*2, 0\} = *\text{mex}(2, 1) = *</math> | ||
+ | |||
+ | |||
+ | <math>\text{heap}(n+9) = \{\text{heap}(n+5), \text{heap}(n+8)\} = \{0, *\} = *\text{mex}(0, 1) = *2</math> | ||
+ | |||
+ | |||
+ | We have proven the inductive hypothesis. QED | ||
+ | There are <math>2020*\frac{2}{5}=808</math> positive integers congruent to <math>0,2 \bmod{5}</math> between 1 and 2020, and 1 integer between 2021 and 2024. 808 + 1 = \boxed{809}. | ||
+ | |||
+ | ~numerophile | ||
==Video Solution== | ==Video Solution== |
Revision as of 15:37, 3 February 2024
Contents
[hide]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, where a marks when Alice wins and an marks when Bob wins.
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. In other words, there will be losing positions out of every consecutive values of n. As ranges from to , of these values are losing positions where Bob will win. As ranges from to , is the only value where Bob will win. Thus, the answer is
~alexanderruan
Solution 3
Denote by and Alice's or Bob's th moves, respectively.
Case 1: .
Bob can always take the strategy that . This guarantees him to win.
In this case, the number of is .
Case 2: .
In this case, consider Alice's following strategy: and for . Thus, under Alice's this strategy, Bob has no way to win.
Case 3: .
In this case, consider Alice's following strategy: and for . Thus, under Alice's this strategy, Bob has no way to win.
Case 4: .
Bob can always take the strategy that . Therefore, after the th turn, there are two tokens leftover. Therefore, Alice must take 1 in the next turn that leaves the last token on the table. Therefore, Bob can take the last token to win the game. This guarantees him to win.
In this case, the number of is .
Case 5: .
Consider Alice's following strategy: and for . By doing so, there will finally be 2 tokens on the table and Bob moves first. Because Bob has the only choice of taking 1 token, Alice can take the last token and win the game.
Therefore, in this case, under Alice's this strategy, Bob has no way to win.
Putting all cases together, the answer is .
Solution 4 (Grundy Values)
Since the game Alice and Bob play is impartial (the only difference between player 1 and player 2 is that player 1 goes first (note that games like chess are not impartial because each player can only move their own pieces)), we can use the Sprague-Grundy Theorem to solve this problem. We will use induction to calculate the Grundy Values for this game.
We claim that heaps of size congruent to will be in outcome class (win for player 2 = Bob), and heaps of size equivalent to will be in outcome class (win for player 1 = Alice). Note that the mex (minimal excludant) of a set of nonnegative integers is the least nonnegative integer not in the set. e.g. mex and mex.
We have proven the base case. We will now prove the inductive hypothesis: If , , , , , and , then , , , , and .
We have proven the inductive hypothesis. QED
There are positive integers congruent to between 1 and 2020, and 1 integer between 2021 and 2024. 808 + 1 = \boxed{809}.
~numerophile
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
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.