Difference between revisions of "2018 AIME I Problems/Problem 10"
(→Solution 6(Generating Functions???)) |
(→Solution 6(Generating Functions???)) |
||
Line 138: | Line 138: | ||
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> | 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> | + | 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 | ~SailS |
Revision as of 12:18, 29 March 2024
Contents
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 . 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
, which has
steps. Let
be the number of paths with
steps that begin and end at point
. Find the remainder when
is divided by
![[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]](http://latex.artofproblemsolving.com/5/e/1/5e14e54dea77f9fbb819cf7f81efad0cfbce0990.png)
Solution 1
We divide this up into casework. The "directions" the bug can go are ,
, and
. Let an
signal going clockwise (because it has to be in the inner circle), an
signal going counter-clockwise, and an
switching between inner and outer circles. An example string of length fifteen that gets the bug back to
would be
.
For the bug to end up back at
, the difference between the number of
's and
's must be a multiple of
.
- Case 1 -- There are 15 more
's than
's.
- There is clearly
way for this to happen.
- Case 2 -- There are
more
's than
's.
- We split this case up into several sub-cases based on the number of
's.
- Sub-case 1 -- There are
's and
's.
- Notice that the number of ways to order the
's and
's are independent assortments because the
's must be in the "even" spaces between
's (i.e. before the 1st
, between the 2nd and 3rd
's, etc.), while the
's must be in the "odd" spaces.
- Sub-case 1 -- There are
- There are
places to put the
's (after the 0th, 2nd, 4th, 6th, 8th, and 10th
's), and
places to put the (0)
's. We use stars and bars to get an answer of
- Sub-case 2 -- There are
's,
's, and
.
- Similarly and by using stars and bars, we get an amount of
- There are
- All the other sub-cases are similar, with a total of
by Vandermonde's Identity.
- Case 3 -- There are
more
's than
's.
- This case is similar to the other case.
- Here is an example of a sub-case for this case.
- Sub-case
- There are
's and
's.
- There are
ways to do this.
- We can see now that the pattern is going to be
.
So, the total number of ways is which gives
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 s and
s of length
, where
denotes a move which is either counterclockwise or inward along a spoke and
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
s and the number of
s is a multiple of
, and so we must have either
,
, or
s within the first fourteen moves with the last move being an
. This implies the answer is
Solution 3 (Similar To Solution 2 But Modified To Clarify)
Let an signal a move that ends in the outer circle and
signal a move that ends in the inner circle. Now notice that for a string of
moves to end at
, the difference between
's and
's in the string must be a multiple of
.
's: Trivially
case.
's and
's: Since the string has to end in an
for the bug to land on
, there are a total of
ways to put
's in the first
moves.
's and
's: Similarly there are
ways to put
's in the first
moves.
's: Impossible since the string has to end with an I.
This brings us an answer of .
-Solution by mathleticguyyyyyyyyy- ~Edited by ike.chen
Solution 4 (Recursion)
Define to be the number of sequences of length
that ends at
and similarly for the other spokes. Also let
Apparently everytime the bug has
choices for its next move, thus we have
. Now we attempt to find a recursive formula for
.
Computing a few easy terms we have
,
,
,
,
. Continuing the process yields
.
~ 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 times, the number of moves the ant makes is
. 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 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. Let the number of counterclockwise moves be
and clockwise moves be
. The only two feasible solutions for
are
and
. Therefore, we use stars and bars to obtain
ways for this case.
Case 3: 2 pairs
The ant changes directions 4 times and makes 11 moves, so we obtain and
using similar logic. Using stars and bars once again, we obtain
ways for this case.
Case 4: 3 pairs
Again, the only solutions for are
and
. Using stars and bars, we obtain
.
Case 5: 4 pairs
The only solutions are and
. Using stars and bars, we obtain
.
Case 6: 5 pairs
The only solutions are and
. Using stars and bars, we obtain
.
Note that there are no more cases since
and
have to be equivalent
, which would need to make
or
negative. Adding all the cases, we get
. Taking modulo
, we obtain
The process of using stars and bars was the number of ways to group the counterclockwise and clockwise moves. For instance, if there are pairs of switches, then based on the solutions for
, we can divide
into
subsets and
into
subsets. This is equivalent to putting
objects in
bins and
objects into
bins where a bin can be empty which is modeled by consecutive switches. Then, we multiply both results. Therefore, for each
, we compute
and add them up.
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 correspond to
) where moving between the inner circle can be mapped to multiplying by
we can also view moving between circles as a multiplying by
Therefore the generating function for the paths beginning at or
can be seen as
We want the positive real terms or the ones that end on and those add up to
~SailS
See Also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.