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

Latest revision as of 00:30, 1 August 2024

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

Solution 5 (Stars and Bars)

The points on the outer circle and the points on the inner circle have a one-to-one correspondence. Therefore, it is equivalent to the scenario of switching directions back and forth in the inner circle but changing directions to make up for travelling on spokes. If the ant changes directions $s$ times, the number of moves the ant makes is $15-s$ . Also note that is switches directions an even number of times, so we think of it in pairs:

Case 1: 0 pairs

The ant would have to only be in the inner circle and go in one direction. Hence there is $1$ way.

Case 2: 1 pair

This is equivalent to the ant making 13 moves in the inner circle where it switches directions 2 times (counterclockwise-clockwise-counterclockwise). Note that the number of counterclockwise and clockwise moves must be equivalent $\pmod{5}$ . Let the number of counterclockwise moves be $C$ and clockwise moves be $C'$ . The only two feasible solutions for $(C,C')$ are $(4,9)$ and $(9,4)$ . Therefore, we use stars and bars to obtain $10+5=15$ ways for this case.

Case 3: 2 pairs

The ant changes directions 4 times and makes 11 moves, so we obtain $(3,8)$ and $(8,3)$ using similar logic. Using stars and bars once again, we obtain $90+180=270$ ways for this case.

Case 4: 3 pairs

Again, the only solutions for $(C,C')$ are $(2,7)$ and $(7,2)$ . Using stars and bars, we obtain $360+720=1080$ .

Case 5: 4 pairs

The only solutions are $(1,6)$ and $(6,1)$ . Using stars and bars, we obtain $840+420=1260$ .

Case 6: 5 pairs

The only solutions are $(0,5)$ and $(5,0)$ . Using stars and bars, we obtain $252+126=378$ . Note that there are no more cases since $C$ and $C'$ have to be equivalent $\pmod{5}$ , which would need to make $C$ or $C'$ negative. Adding all the cases, we get $1+15+270+1080+1260+378=3004$ . Taking modulo $1000$ , we obtain $3004 \equiv \boxed{004} \pmod{1000}$

The process of using stars and bars was the number of ways to group the counterclockwise and clockwise moves. For instance, if there are $p$ pairs of switches, then based on the solutions for $(C,C')$ , we can divide $C$ into $p+1$ subsets and $C'$ into $p$ subsets. This is equivalent to putting $C$ objects in $p+1$ bins and $C'$ objects into $p$ bins where a bin can be empty which is modeled by consecutive switches. Then, we multiply both results. Therefore, for each $p$ , we compute $\dbinom{C+p}{p}\dbinom{C'+p-1}{p-1}$ and add them up.

~Magnetoninja

Solution 6(Generating Functions???)

We can view the diagram as a collection of points on the complex plane that are connected by transformations/symmetries. The inner circle can be represented as the fifth roots of unity(WLOG let $A$ correspond to $1$ ) where moving between the inner circle can be mapped to multiplying by $e^{\frac{2i\pi}{5}}$ we can also view moving between circles as a multiplying by $-e^{-2i\pi} = -1.$

Therefore the generating function for the paths beginning at $1$ or $A$ can be seen as $(e^{\frac{2i\pi}{5}} - 1)^{15}.$

We want the positive real terms or the ones that end on $1$ and those add up to $\dbinom{15}{5}(e^{2i\pi/5})^5(-1)^{10} + \dbinom{15}{15}(e^{2i\pi/5})^{15} = 3004 \equiv \boxed{004} \pmod{1000}.$

~SailS

Solution 7 (Official MAA, clarified)

Our motivation is that moving along the outer circle "counters" moving along the inner circle in terms of angular position. Hence, denote $I$ as moving along the inner circle OR moving from the outside circle to the inner circle. Also denote $O$ as moving along the outer circle OR moving from the inside circle to the outside circle.

Notice that eventually, moves that go from the inner circle to the outer circle must equal to moves that go from the outer circle from the inner circle. This is because we must always end up at the inner circle at the last move, meaning that every time we moved to the outer circle, we must have also eventually moved back to the inner circle.

With this in mind, we can now "ignore" moving between inner and outer circle. We find that $O \equiv I \pmod 5$ , since we must end up at our original angular position, and taking 5 moves in one direction lands us back in the same position.

Using this fact, we form $3$ cases:

$O - I = 5$ , $O + I = 15$ which gives us $O = 10$ . Since we have $10$ $O$ s and $5$ $I$ s, but the last move must be an $I$ , we have $\binom{14}{10}=1001$ ways for this case.

$O - I = -5$ , $O + I = 15$ which gives us $O = 5$ . We have $\binom{14}{5}=2002$ ways for this case.

$O - I = -15$ , $O + I = 15$ which gives us $O = 0$ . (aka only moving in the inner circle). We have $\binom{14}{0}=1$ ways for this case.

Ultimately, the total number of ways is $1001 + 2002 + 1 = 3004$ , and our answer is $\boxed{004}$ .

~xHypotenuse

@@ Line 102: / Line 102: @@
 == Solution 5 (Stars and Bars) ==
-We approach this problem by casework for how many times the ant passes on a pair of spokes in and out of the circle (switching back and forth between the inner and outer circle). Since each point on the outer circle is connected to a point in the inner circle by a spoke, the points have a one-to-one correspondence. Therefore, we can rethink of the scenario as switching directions back and forth in the inner circle (whenever we "go on a spoke" we change directions). The number of "moves" the ant makes in this inner circle in this scenario would then be <math>15</math> minus the (number of times we switch directions in our scenario) since each time we switch directions in our scenario, it would act as going on a spoke in the original scenario. Also, note that we will have to end up at point <math>A</math> in the inner circle, so there will be an even number of "switches" that the ant moves from the outer and inner circles so we can think of it in pairs, where each pair is the action of moving to the outer circle and back to the inner circle. We proceed as follows:
+The points on the outer circle and the points on the inner circle have a one-to-one correspondence. Therefore, it is equivalent to the scenario of switching directions back and forth in the inner circle but changing directions to make up for travelling on spokes. If the ant changes directions <math>s</math> times, the number of moves the ant makes is <math>15-s</math>. Also note that is switches directions an even number of times, so we think of it in pairs:
-Case 1: 0 "pairs"
+Case 1: 0 pairs
 The ant would have to only be in the inner circle and go in one direction. Hence there is <math>1</math> way.
-Case 2: 1 "pair"
+Case 2: 1 pair
-That means we can think about <math>13</math> "moves" in the inner circle where we switch directions <math>2</math> times (counterclockwise-clockwise-counterclockwise). Note that the number of counterclockwise and clockwise moves are equivalent <math>\pmod{5}</math>, which is the only way they can return to point <math>A</math>. Let the number of counterclockwise moves be <math>x</math> and clockwise moves be <math>y</math>. Then, the only two feasible solutions for <math>(x,y)</math> are <math>(4,9)</math> and <math>(9,4)</math>. Therefore, we use stars and bars to obtain <math>10+5=15</math> ways for this case.
+This is equivalent to the ant making 13 moves in the inner circle where it switches directions 2 times (counterclockwise-clockwise-counterclockwise). Note that the number of counterclockwise and clockwise moves must be equivalent<math>\pmod{5}</math>. Let the number of counterclockwise moves be <math>C</math> and clockwise moves be <math>C'</math>. The only two feasible solutions for <math>(C,C')</math> are <math>(4,9)</math> and <math>(9,4)</math>. Therefore, we use stars and bars to obtain <math>10+5=15</math> ways for this case.
-Case 3: 2 "pairs"
+Case 3: 2 pairs
-Using similar logic, we obtain <math>(3,8)</math> and <math>(8,3)</math>. Using stars and bars once again, we obtain <math>90+180=270</math> ways for this case.
+The ant changes directions 4 times and makes 11 moves, so we obtain <math>(3,8)</math> and <math>(8,3)</math> using similar logic. Using stars and bars once again, we obtain <math>90+180=270</math> ways for this case.
-Case 4: 3 "pairs"
+Case 4: 3 pairs
-Again, the only solutions for <math>(x,y)</math> are <math>(2,7)</math> and <math>(7,2)</math>. Using stars and bars, we obtain <math>360+730=1080</math>.
+Again, the only solutions for <math>(C,C')</math> are <math>(2,7)</math> and <math>(7,2)</math>. Using stars and bars, we obtain <math>360+720=1080</math>.
-Case 5: 4 "pairs"
+Case 5: 4 pairs
 The only solutions are <math>(1,6)</math> and <math>(6,1)</math>. Using stars and bars, we obtain <math>840+420=1260</math>.
-Case 6: 5 "pairs"
+Case 6: 5 pairs
 The only solutions are <math>(0,5)</math> and <math>(5,0)</math>. Using stars and bars, we obtain <math>252+126=378</math>.
-Note that there are no more cases since <math>x</math> and <math>y</math> have to be equivalent <math>\pmod{5}</math>, which would need to make <math>x</math> or <math>y</math> negative, hence not possible. Adding all the cases, we get <math>1+15+270+1080+1260+378=3004</math>. Taking modulo <math>1000</math>, we obtain <math>3004 \equiv \boxed{004} \pmod{1000}</math>
+Note that there are no more cases since <math>C</math> and <math>C'</math> have to be equivalent<math>\pmod{5}</math>, which would need to make <math>C</math> or <math>C'</math> negative. Adding all the cases, we get <math>1+15+270+1080+1260+378=3004</math>. Taking modulo <math>1000</math>, we obtain <math>3004 \equiv \boxed{004} \pmod{1000}</math>
-The process of using stars and bars was the number of ways to group the counterclockwise and clockwise moves. For instance, if there are <math>n</math> "pairs" of switches, then based on the solutions for <math>(x,y)</math>, we can partition <math>x</math> into <math>n+1</math> subsets (indistinguishable) and <math>y</math> into <math>n</math> subsets respectively. Then, we multiply both results. This is equivalent to putting <math>x</math> objects into <math>n+1</math> bins where a bin can have <math>0</math> objects since the subsets are indistinguishable. We use the formula <math>\dbinom{a+b-1}{a-1}</math> for putting <math>b</math> objects into <math>a</math> bins. Plugging in <math>x</math>, <math>y</math> and <math>n+1</math>, <math>n</math> for <math>b</math> and <math>a</math> respectively helps us reach the conclusion for each case.
-Also, we derived the solutions <math>(x,y)</math> since they have to differ by a multiple of <math>5</math> and <math>x+y</math> equals the number of moves in the inner circle in our scenario. The only feasible difference is <math>5</math>. Therefore, <math>2x+5</math> is equivalent to the number of moves in the inner circle in our scenario. We can also switch <math>(x,y)</math> to <math>(y,x)</math> giving us two feasible solutions for each case.
+The process of using stars and bars was the number of ways to group the counterclockwise and clockwise moves. For instance, if there are <math>p</math> pairs of switches, then based on the solutions for <math>(C,C')</math>, we can divide <math>C</math> into <math>p+1</math> subsets and <math>C'</math> into <math>p</math> subsets. This is equivalent to putting <math>C</math> objects in <math>p+1</math> bins and <math>C'</math> objects into <math>p</math> bins where a bin can be empty which is modeled by consecutive switches. Then, we multiply both results. Therefore, for each <math>p</math>, we compute <math>\dbinom{C+p}{p}\dbinom{C'+p-1}{p-1}</math> and add them up.
 ~[https://artofproblemsolving.com/wiki/index.php/User:Magnetoninja Magnetoninja]
+==Solution 6(Generating Functions???)==
+We can view the diagram as a collection of points on the complex plane that are connected by transformations/symmetries. The inner circle can be represented as the fifth roots of unity(WLOG let <math>A</math> correspond to <math>1</math>) where moving between the inner circle can be mapped to multiplying by <math>e^{\frac{2i\pi}{5}}</math> we can also view moving between circles as a multiplying by <math>-e^{-2i\pi} = -1.</math>
+Therefore the generating function for the paths beginning at <math>1</math> or <math>A</math> can be seen as <math>(e^{\frac{2i\pi}{5}} - 1)^{15}.</math>
+We want the positive real terms or the ones that end on <math>1</math> and those add up to <math>\dbinom{15}{5}(e^{2i\pi/5})^5(-1)^{10} + \dbinom{15}{15}(e^{2i\pi/5})^{15} = 3004 \equiv \boxed{004} \pmod{1000}.</math>
+~SailS
+== Solution 7 (Official MAA, clarified)==
+Our motivation is that moving along the outer circle "counters" moving along the inner circle in terms of angular position. Hence, denote <math>I</math> as moving along the inner circle OR moving from the outside circle to the inner circle. Also denote <math>O</math> as moving along the outer circle OR moving from the inside circle to the outside circle.
+Notice that eventually, moves that go from the inner circle to the outer circle must equal to moves that go from the outer circle from the inner circle. This is because we must always end up at the inner circle at the last move, meaning that every time we moved to the outer circle, we must have also eventually moved back to the inner circle.
+With this in mind, we can now "ignore" moving between inner and outer circle. We find that <math>O \equiv I \pmod 5</math>, since we must end up at our original angular position, and taking 5 moves in one direction lands us back in the same position.
+Using this fact, we form <math>3</math> cases:
+<math>O - I = 5</math>, <math>O + I = 15</math>   which gives us <math>O = 10</math>. Since we have <math>10</math> <math>O</math>s and <math>5</math> <math>I</math>s, but the last move must be an <math>I</math>, we have <math>\binom{14}{10}=1001</math> ways for this case.
+<math>O - I = -5</math>, <math>O + I = 15</math>   which gives us <math>O = 5</math>. We have <math>\binom{14}{5}=2002</math> ways for this case.
+<math>O - I = -15</math>, <math>O + I = 15</math>   which gives us <math>O = 0</math>. (aka only moving in the inner circle). We have <math>\binom{14}{0}=1</math> ways for this case.
+Ultimately, the total number of ways is <math>1001 + 2002 + 1 = 3004</math>, and our answer is <math>\boxed{004}</math>.
+~xHypotenuse
 ==See Also==
 {{AIME box|year=2018|n=I|num-b=9|num-a=11}}
 {{MAA Notice}}

2018 AIME I (Problems • Answer Key • Resources)
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

Page

Toolbox

Search