Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 AIME I Problems/Problem 3"
Line 4: Line 4:
  
 
==Solution 1==
 
==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. 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.
+
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 <math>3</math>, Alice will take <math>1</math>, Bob will take one, and Alice will take the final one. If there are <math>4</math>, Alice will just remove all <math>4</math> at once. If there are <math>5</math>, no matter what Alice does, Bob can take the final coins in one try. Notice that Alice wins if there are <math>1</math>, <math>3</math>, or <math>4</math> coins left. Bob wins if there are <math>2</math> or <math>5</math> coins left.
  
−
After some thought, you may realize that there is a strategy for Bob. If he can just ensure that there are 5 coins remaining, he wins. Any multiple of 5 will also work. 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.
+
After some thought, you may realize that there is a strategy for Bob. If there is n is a multiple of <math>5</math>, then Bob will win. The reason for this is the following: Let's say there are a multiple of <math>5</math> coins remaining in the stack. If Alice takes <math>1</math>, Bob will take <math>4</math>, and there will still be a multiple of <math>5</math>. If Alice takes <math>4</math>, Bob will take <math>1</math>, and there will still be a multiple of <math>5</math>. This process will continue until you get <math>0</math> coins left. For example, let's say there are <math>205</math> 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 <math>5</math> left. This will continue until there are <math>5</math> 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.
+
After some more experimentation, you'll realize that any number that is congruent to <math>2</math> mod <math>5</math> will also work. This is because Bob can do the same strategy, and when there are <math>2</math> coins left, Alice is forced to take <math>1</math> and Bob takes the final coin. For example, let's say there are <math>72</math> coins. If Alice takes <math>1</math>, Bob will take <math>4</math>. If Alice takes <math>4</math>, Bob will take <math>1</math>. So after they each make a turn, the number will always be equal to <math>2</math> mod <math>5</math>. Eventually, there will be only <math>2</math> coins remaining, and we've established that Alice will simply take <math>1</math> 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, ..., 2020. For the second category, there are 405 numbers. 2, 7, 12, 17, ..., 2022. So the answer is 404 + 405 = <math>\boxed{809}</math>
+
So we have to find the number of numbers less than or equal to <math>2024</math> that are either congruent to <math>0</math> mod <math>5</math> or <math>2</math> mod <math>5</math>. There are <math>404</math> numbers in the first category: <math>5, 10, 15, \dots, 2020</math>. For the second category, there are <math>405</math> numbers. <math>2, 7, 12, 17, \dots, 2022</math>. So the answer is <math>404 + 405 = \boxed{809}</math>
  
 
~lprado
 
~lprado

Revision as of 15:52, 2 February 2024

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AIME_I_Problems/Problem_3&oldid=214165"