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

2018 AIME I Problems/Problem 10

Revision as of 16:34, 7 March 2018 by Cooljoseph (talk | contribs) (→‎Solution)

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 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 $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$

Solution

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 [i]inner[/i] 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 then $O$'s. 

    There is clearly $1$ way for this to happen.

Case 2: There are $5$ more $I$'s then $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 $5$ 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 $3\boxed{004}$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_10&oldid=92842"