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"

m (latexed numbers/variables)
Line 13: Line 13:
  
 
~lprado
 
~lprado
 +
 +
==Solution 2==
 +
We will use winning and losing positions.
 +
 +
<math>1</math> coin: W
 +
 +
<math>2</math> coins: L
 +
 +
<math>3</math> coins: W
 +
 +
<math>4</math> coins: W
 +
 +
<math>5</math> coins: L
 +
 +
<math>6</math> coin: W
 +
 +
<math>7</math> coins: L
 +
 +
<math>8</math> coins: W
 +
 +
<math>9</math> coins: W
 +
 +
<math>10</math> coins: L
 +
 +
<math>11</math> coin: W
 +
 +
<math>12</math> coins: L
 +
 +
<math>13</math> coins: W
 +
 +
<math>14</math> coins: W
 +
 +
<math>15</math> coins: L
 +
 +
We can see that winning positions occur when <math>n\equiv2, 3, 4 \mod{5}</math> and losing positions occur otherwise. As <math>n</math> ranges from <math>1</math> to <math>2020</math>, <math>\frac{2}{5}</math> of these values are losing positions where Bob will win. As <math>n</math> goes from <math>2021</math> to <math>2024</math>, <math>2022</math> is the only value where Bob wins. Therefore, the answer is <math>2020\times\frac{2}{5}+1=\boxed{809}</math>
 +
  
 
==See also==
 
==See also==

Revision as of 20:24, 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

Solution 2

We will use winning and losing positions.

$1$ coin: W

$2$ coins: L

$3$ coins: W

$4$ coins: W

$5$ coins: L

$6$ coin: W

$7$ coins: L

$8$ coins: W

$9$ coins: W

$10$ coins: L

$11$ coin: W

$12$ coins: L

$13$ coins: W

$14$ coins: W

$15$ coins: L

We can see that winning positions occur when $n\equiv2, 3, 4 \mod{5}$ and losing positions occur otherwise. As $n$ ranges from $1$ to $2020$, $\frac{2}{5}$ of these values are losing positions where Bob will win. As $n$ goes from $2021$ to $2024$, $2022$ is the only value where Bob wins. Therefore, the answer is $2020\times\frac{2}{5}+1=\boxed{809}$


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. AMC logo.png

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