Difference between revisions of "2018 AIME I Problems/Problem 10"

m (Solution)
m (Problem: Added a period to last sentence.)
(32 intermediate revisions by 14 users not shown)
Line 1: Line 1:
The wheel shown below consists of two circles and five spokes, with a label at each point where a spoke meets a circle. A bug walks along the wheel, starting at point <math>A</math>. At every step of the process, the bug walks from one labeled point to an adjacent labeled point. Along the inner circle the bug only walks in a circular clockwise direction, and along the outer circle the bug only walks in a clockwise direction. For example, the bug could travel along the path <math>AJABCHCHIJA</math>, which has <math>10</math> steps. Let <math>n</math> be the number of paths with <math>15</math> steps that begin and end at point <math>A</math>. Find the remainder when <math>n</math> is divided by <math>1000</math>
+
 
==Solution==
+
==Problem==
 +
The wheel shown below consists of two circles and five spokes, with a label at each point where a spoke meets a circle. A bug walks along the wheel, starting at point <math>A</math>. At every step of the process, the bug walks from one labeled point to an adjacent labeled point. Along the inner circle the bug only walks in a counterclockwise direction, and along the outer circle the bug only walks in a clockwise direction. For example, the bug could travel along the path <math>AJABCHCHIJA</math>, which has <math>10</math> steps. Let <math>n</math> be the number of paths with <math>15</math> steps that begin and end at point <math>A</math>. Find the remainder when <math>n</math> is divided by <math>1000.</math>
 +
<center><asy>
 +
unitsize(32);
 +
draw(unitcircle);
 +
draw(scale(2) * unitcircle);
 +
for(int d = 90; d < 360 + 90; d += 72){
 +
draw(2 * dir(d) -- dir(d));
 +
}
 +
 
 +
real s = 4;
 +
dot(1 * dir( 90), linewidth(s));
 +
dot(1 * dir(162), linewidth(s));
 +
dot(1 * dir(234), linewidth(s));
 +
dot(1 * dir(306), linewidth(s));
 +
dot(1 * dir(378), linewidth(s));
 +
dot(2 * dir(378), linewidth(s));
 +
dot(2 * dir(306), linewidth(s));
 +
dot(2 * dir(234), linewidth(s));
 +
dot(2 * dir(162), linewidth(s));
 +
dot(2 * dir( 90), linewidth(s));
 +
 
 +
defaultpen(fontsize(10pt));
 +
real r = 0.05;
 +
label("$A$", (1-r) * dir( 90), -dir( 90));
 +
label("$B$", (1-r) * dir(162), -dir(162));
 +
label("$C$", (1-r) * dir(234), -dir(234));
 +
label("$D$", (1-r) * dir(306), -dir(306));
 +
label("$E$", (1-r) * dir(378), -dir(378));
 +
label("$F$", (2+r) * dir(378), dir(378));
 +
label("$G$", (2+r) * dir(306), dir(306));
 +
label("$H$", (2+r) * dir(234), dir(234));
 +
label("$I$", (2+r) * dir(162), dir(162));
 +
label("$J$", (2+r) * dir( 90), dir( 90));
 +
</asy></center>
 +
 
 +
==Solution 1==
 
We divide this up into casework.  The "directions" the bug can go are <math>\text{Clockwise}</math>, <math>\text{Counter-Clockwise}</math>, and <math>\text{Switching}</math>.  Let an <math>I</math> signal going clockwise (because it has to be in the ''inner'' circle), an <math>O</math> signal going counter-clockwise, and an <math>S</math> switching between inner and outer circles.  An example string of length fifteen that gets the bug back to <math>A</math> would be <math>ISSIIISOOSISSII</math>.
 
We divide this up into casework.  The "directions" the bug can go are <math>\text{Clockwise}</math>, <math>\text{Counter-Clockwise}</math>, and <math>\text{Switching}</math>.  Let an <math>I</math> signal going clockwise (because it has to be in the ''inner'' circle), an <math>O</math> signal going counter-clockwise, and an <math>S</math> switching between inner and outer circles.  An example string of length fifteen that gets the bug back to <math>A</math> would be <math>ISSIIISOOSISSII</math>.
 
For the bug to end up back at <math>A</math>, the difference between the number of <math>I</math>'s and <math>O</math>'s must be a multiple of <math>5</math>.
 
For the bug to end up back at <math>A</math>, the difference between the number of <math>I</math>'s and <math>O</math>'s must be a multiple of <math>5</math>.
Case 1: There are 15 more <math>I</math>'s then <math>O</math>'s.
+
;Case 1 -- There are 15 more <math>I</math>'s than <math>O</math>'s.
    There is clearly <math>1</math> way for this to happen.
+
:There is clearly <math>1</math> way for this to happen.
Case 2: There are <math>5</math> more <math>I</math>'s then <math>O</math>'s.
+
 
    We split this case up into several sub-cases based on the number of <math>S</math>'s.
+
;Case 2 -- There are <math>5</math> more <math>I</math>'s than <math>O</math>'s.
    Sub-case 1: There are <math>10</math> <math>S</math>'s and <math>5</math> <math>I</math>'s.
+
:We split this case up into several sub-cases based on the number of <math>S</math>'s.
          Notice that the number of ways to order the <math>I</math>'s and <math>O</math>'s are independent assortments because the <math>I</math>'s must be in the "even" spaces
+
:;Sub-case 1 -- There are <math>10</math> <math>S</math>'s and <math>5</math> <math>I</math>'s.
          between <math>S</math>'s (i.e. before the 1st <math>S</math>, between the 2nd and 3rd <math>S</math>'s, etc.), while the <math>O</math>'s must be in the "odd" spaces.
+
::Notice that the number of ways to order the <math>I</math>'s and <math>O</math>'s are independent assortments because the <math>I</math>'s must be in the "even" spaces between <math>S</math>'s (i.e. before the 1st <math>S</math>, between the 2nd and 3rd <math>S</math>'s, etc.), while the <math>O</math>'s must be in the "odd" spaces.
         
+
 
          There are <math>6</math> places to put the <math>I</math>'s (after the 0th, 2nd, 4th, 6th, 8th, and 10th <math>S</math>'s), and <math>5</math> places to put the (0) <math>O</math>'s.  We use stars
+
::There are <math>6</math> places to put the <math>I</math>'s (after the 0th, 2nd, 4th, 6th, 8th, and 10th <math>S</math>'s), and <math>4</math> places to put the (0) <math>O</math>'s.  We use stars and bars to get an answer of <math>\binom{10}{5}\binom{4}{0}</math>
          and bars to get an answer of <math>\binom{10}{5}\binom{4}{0}</math>
+
:;Sub-case 2 --  There are <math>8</math> <math>S</math>'s, <math>6</math> <math>I</math>'s, and <math>1</math> <math>O</math>.
      Sub-case 2:    There are <math>8</math> <math>S</math>'s, <math>6</math> <math>I</math>'s, and <math>1</math> <math>O</math>.
+
::Similarly and by using stars and bars, we get an amount of <math>\binom{10}{4}\binom{4}{1}</math>
          Similarly and by using stars and bars, we get an amount of <math>\binom{10}{4}\binom{4}{1}</math>
+
:All the other  sub-cases are similar, with a total of <math>\binom{10}{5}\binom{4}{0}+\binom{10}{4}\binom{4}{1}+\cdots+\binom{10}{1}\binom{4}{4}=\binom{14}{5}=2002</math> by [https://artofproblemsolving.com/wiki/index.php?title=Combinatorial_identity#Vandermonde.27s_Identity Vandermonde's Identity].
   
+
 
    All the other  sub-cases are similar, with a total of <math>\binom{10}{5}\binom{4}{0}+\binom{10}{4}\binom{4}{1}+\cdots+\binom{10}{1}\binom{4}{4}=\binom{14}{5}=2002</math> by Vandermonde's Identity.
+
;Case 3 -- There are <math>5</math> more <math>O</math>'s than <math>I</math>'s.
Case 3: There are <math>5</math> more <math>O</math>'s than <math>I</math>'s.
+
:This case is similar to the other case.
    This case is similar to the other case.
+
:Here is an example of a sub-case for this case.
    Here is an example of a sub-case for this case.
+
:;Sub-case:  There are <math>10</math> <math>S</math>'s and <math>5</math> <math>O</math>'s.
    Sub-case:  There are <math>10</math> <math>S</math>'s and <math>5</math> <math>O</math>'s.
+
::There are <math>\binom{9}{4}\binom{5}{0}</math> ways to do this.
          There are <math>\binom{9}{4}\binom{5}{0}</math> ways to do this.
+
:We can see now that the pattern is going to be <math>\binom{9}{4}\binom{5}{0}+\binom{9}{3}\binom{5}{1}+\cdots+\binom{9}{0}\binom{5}{4}=\binom{14}{4}=1001</math>.
    We can see now that the pattern is going to be <math>\binom{9}{4}\binom{5}{0}+\binom{9}{3}\binom{5}{1}+\cdots+\binom{9}{0}\binom{5}{4}=\binom{14}{4}=1001</math>.
+
 
 +
 
 +
So, the total number of ways is <math>1+2002+1001=3004</math> which gives <math>\boxed{004}</math> as the answer.
 +
 
 +
== Solution 2 (Official MAA)==
 +
Note that the set of sequences of moves the bug makes is in bijective correspondence with the set of strings of <math>X</math>s and <math>Y</math>s of length <math>15</math>, where <math>X</math> denotes a move which is either counterclockwise or inward along a spoke and <math>Y</math> denotes a move which is either clockwise or outward along a spoke.  (The proof of this basically boils down to the fact that which one depends on whether the bug is on the inner wheel or the outer wheel.)  Now the condition that the bug ends at A implies that the difference between the number of <math>X</math>s and the number of <math>Y</math>s is a multiple of <math>5</math>, and so we must have either <math>4</math>, <math>9</math>, or <math>14</math> <math>X</math>s within the first fourteen moves with the last move being an <math>X</math>.  This implies the answer is <cmath>\binom{14}4+\binom{14}9+\binom{14}{14} = 3004\equiv \boxed{004}\pmod{1000}.</cmath>
 +
 
 +
==Solution 3 (Similar To Solution 2 But Modified To Clarify)==
 +
Let an <math>O</math> signal a move that ends in the outer circle and <math>I</math> signal a move that ends in the inner circle. Now notice that for a string of <math>15</math> moves to end at <math>A</math>, the difference between <math>O</math>'s and <math>I</math>'s in the string must be a multiple of <math>5</math>.
 +
 
 +
<math>15</math> <math>I</math>'s: Trivially <math>1</math> case.
 +
 
 +
<math>5</math> <math>O</math>'s and <math>10</math> <math>I</math>'s: Since the string has to end in an <math>I</math> for the bug to land on <math>A</math>, there are a total of <math>\binom{14}{5}=2002</math> ways to put <math>5</math> <math>O</math>'s in the first <math>14</math> moves.
 +
 
 +
<math>10</math> <math>O</math>'s and <math>5</math> <math>I</math>'s: Similarly there are <math>\binom{14}{4}=1001</math> ways to put <math>5-1=4</math> <math>I</math>'s in the first <math>14</math> moves.
 +
 
 +
<math>15</math> <math>O</math>'s: Impossible since the string has to end with an I.
 +
 
 +
This brings us an answer of <math>1+2002+1001=3004 \equiv \boxed{004} \pmod{1000}</math>.
 +
 
 +
-Solution by mathleticguyyyyyyyyy-
 +
~Edited by ike.chen
 +
 
 +
== Solution 4 (Recursion) ==
 +
 
 +
Define <math>A_n</math> to be the number of sequences of length <math>n</math> that ends at <math>A</math> and similarly for the other spokes. Also let
 +
<cmath>S_n=A_n+B_n+C_n+D_n+E_n+F_n+G_n+H_n+I_n+J_n</cmath>
 +
Apparently everytime the bug has <math>2</math> choices for its next move, thus we have <math>S_n=2^n</math>. Now we attempt to find a recursive formula for <math>A_n</math>.
 +
<cmath>\begin{align*}
 +
A_n&=J_{n-1}+E_{n-1} \\
 +
&=(I_{n-2}+A_{n-2})+(D_{n-2}+F_{n-2}) \\
 +
&=(H_{n-3}+B_{n-3})+(J_{n-3}+E_{n-3})+(G_{n-3}+C_{n-3})+(J_{n-3}+E_{n-3}) \\
 +
&=(B_{n-3}+C_{n-3}+E_{n-3}+G_{n-3}+H_{n-3}+J_{n-3})+(J_{n-3}+E_{n-3}) \\
 +
&=(S_{n-3}-(I_{n-3}+A_{n-3}+D_{n-3}+F_{n-3}))+A_{n-2} \\
 +
&=2^{n-3}-(J_{n-2}+E_{n-2})+A_{n-2} \\
 +
&=2^{n-3}-A_{n-1}+A_{n-2} \\
 +
\end{align*}</cmath>
 +
Computing a few easy terms we have <math>A_0=0</math>, <math>A_1=0</math>, <math>A_2=1</math>, <math>A_3=0</math>, <math>A_4=3</math>. Continuing the process yields <math>A_{15}=3\boxed{004}</math>.
 +
 
 +
~ Nafer
  
So, the total number of ways is <math>3\boxed{004}</math>
+
==See Also==
 +
{{AIME box|year=2018|n=I|num-b=9|num-a=11}}
 +
{{MAA Notice}}

Revision as of 17:10, 6 September 2021

Problem

The wheel shown below consists of two circles and five spokes, with a label at each point where a spoke meets a circle. A bug walks along the wheel, starting at point $A$. At every step of the process, the bug walks from one labeled point to an adjacent labeled point. Along the inner circle the bug only walks in a counterclockwise direction, and along the outer circle the bug only walks in a clockwise direction. For example, the bug could travel along the path $AJABCHCHIJA$, which has $10$ steps. Let $n$ be the number of paths with $15$ steps that begin and end at point $A$. Find the remainder when $n$ is divided by $1000.$

[asy] unitsize(32); draw(unitcircle); draw(scale(2) * unitcircle); for(int d = 90; d < 360 + 90; d += 72){ draw(2 * dir(d) -- dir(d)); }  real s = 4; dot(1 * dir( 90), linewidth(s)); dot(1 * dir(162), linewidth(s)); dot(1 * dir(234), linewidth(s)); dot(1 * dir(306), linewidth(s)); dot(1 * dir(378), linewidth(s)); dot(2 * dir(378), linewidth(s)); dot(2 * dir(306), linewidth(s)); dot(2 * dir(234), linewidth(s)); dot(2 * dir(162), linewidth(s)); dot(2 * dir( 90), linewidth(s));  defaultpen(fontsize(10pt)); real r = 0.05; label("$A$", (1-r) * dir( 90), -dir( 90)); label("$B$", (1-r) * dir(162), -dir(162)); label("$C$", (1-r) * dir(234), -dir(234)); label("$D$", (1-r) * dir(306), -dir(306)); label("$E$", (1-r) * dir(378), -dir(378)); label("$F$", (2+r) * dir(378), dir(378)); label("$G$", (2+r) * dir(306), dir(306)); label("$H$", (2+r) * dir(234), dir(234)); label("$I$", (2+r) * dir(162), dir(162)); label("$J$", (2+r) * dir( 90), dir( 90)); [/asy]

Solution 1

We divide this up into casework. The "directions" the bug can go are $\text{Clockwise}$, $\text{Counter-Clockwise}$, and $\text{Switching}$. Let an $I$ signal going clockwise (because it has to be in the inner circle), an $O$ signal going counter-clockwise, and an $S$ switching between inner and outer circles. An example string of length fifteen that gets the bug back to $A$ would be $ISSIIISOOSISSII$. For the bug to end up back at $A$, the difference between the number of $I$'s and $O$'s must be a multiple of $5$.

Case 1 -- There are 15 more $I$'s than $O$'s.
There is clearly $1$ way for this to happen.
Case 2 -- There are $5$ more $I$'s than $O$'s.
We split this case up into several sub-cases based on the number of $S$'s.
Sub-case 1 -- There are $10$ $S$'s and $5$ $I$'s.
Notice that the number of ways to order the $I$'s and $O$'s are independent assortments because the $I$'s must be in the "even" spaces between $S$'s (i.e. before the 1st $S$, between the 2nd and 3rd $S$'s, etc.), while the $O$'s must be in the "odd" spaces.
There are $6$ places to put the $I$'s (after the 0th, 2nd, 4th, 6th, 8th, and 10th $S$'s), and $4$ places to put the (0) $O$'s. We use stars and bars to get an answer of $\binom{10}{5}\binom{4}{0}$
Sub-case 2 -- There are $8$ $S$'s, $6$ $I$'s, and $1$ $O$.
Similarly and by using stars and bars, we get an amount of $\binom{10}{4}\binom{4}{1}$
All the other sub-cases are similar, with a total of $\binom{10}{5}\binom{4}{0}+\binom{10}{4}\binom{4}{1}+\cdots+\binom{10}{1}\binom{4}{4}=\binom{14}{5}=2002$ by Vandermonde's Identity.
Case 3 -- There are $5$ more $O$'s than $I$'s.
This case is similar to the other case.
Here is an example of a sub-case for this case.
Sub-case
There are $10$ $S$'s and $5$ $O$'s.
There are $\binom{9}{4}\binom{5}{0}$ ways to do this.
We can see now that the pattern is going to be $\binom{9}{4}\binom{5}{0}+\binom{9}{3}\binom{5}{1}+\cdots+\binom{9}{0}\binom{5}{4}=\binom{14}{4}=1001$.


So, the total number of ways is $1+2002+1001=3004$ which gives $\boxed{004}$ as the answer.

Solution 2 (Official MAA)

Note that the set of sequences of moves the bug makes is in bijective correspondence with the set of strings of $X$s and $Y$s of length $15$, where $X$ denotes a move which is either counterclockwise or inward along a spoke and $Y$ denotes a move which is either clockwise or outward along a spoke. (The proof of this basically boils down to the fact that which one depends on whether the bug is on the inner wheel or the outer wheel.) Now the condition that the bug ends at A implies that the difference between the number of $X$s and the number of $Y$s is a multiple of $5$, and so we must have either $4$, $9$, or $14$ $X$s within the first fourteen moves with the last move being an $X$. This implies the answer is \[\binom{14}4+\binom{14}9+\binom{14}{14} = 3004\equiv \boxed{004}\pmod{1000}.\]

Solution 3 (Similar To Solution 2 But Modified To Clarify)

Let an $O$ signal a move that ends in the outer circle and $I$ signal a move that ends in the inner circle. Now notice that for a string of $15$ moves to end at $A$, the difference between $O$'s and $I$'s in the string must be a multiple of $5$.

$15$ $I$'s: Trivially $1$ case.

$5$ $O$'s and $10$ $I$'s: Since the string has to end in an $I$ for the bug to land on $A$, there are a total of $\binom{14}{5}=2002$ ways to put $5$ $O$'s in the first $14$ moves.

$10$ $O$'s and $5$ $I$'s: Similarly there are $\binom{14}{4}=1001$ ways to put $5-1=4$ $I$'s in the first $14$ moves.

$15$ $O$'s: Impossible since the string has to end with an I.

This brings us an answer of $1+2002+1001=3004 \equiv \boxed{004} \pmod{1000}$.

-Solution by mathleticguyyyyyyyyy- ~Edited by ike.chen

Solution 4 (Recursion)

Define $A_n$ to be the number of sequences of length $n$ that ends at $A$ and similarly for the other spokes. Also let \[S_n=A_n+B_n+C_n+D_n+E_n+F_n+G_n+H_n+I_n+J_n\] Apparently everytime the bug has $2$ choices for its next move, thus we have $S_n=2^n$. Now we attempt to find a recursive formula for $A_n$. \begin{align*} A_n&=J_{n-1}+E_{n-1} \\ &=(I_{n-2}+A_{n-2})+(D_{n-2}+F_{n-2}) \\ &=(H_{n-3}+B_{n-3})+(J_{n-3}+E_{n-3})+(G_{n-3}+C_{n-3})+(J_{n-3}+E_{n-3}) \\ &=(B_{n-3}+C_{n-3}+E_{n-3}+G_{n-3}+H_{n-3}+J_{n-3})+(J_{n-3}+E_{n-3}) \\ &=(S_{n-3}-(I_{n-3}+A_{n-3}+D_{n-3}+F_{n-3}))+A_{n-2} \\ &=2^{n-3}-(J_{n-2}+E_{n-2})+A_{n-2} \\ &=2^{n-3}-A_{n-1}+A_{n-2} \\ \end{align*} Computing a few easy terms we have $A_0=0$, $A_1=0$, $A_2=1$, $A_3=0$, $A_4=3$. Continuing the process yields $A_{15}=3\boxed{004}$.

~ Nafer

See Also

2018 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
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