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 "2018 AIME I Problems/Problem 10"

m (→‎Solution)
m (→‎Solution)
Line 3: Line 3:
 
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 then <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.
 
−
    Sub-case 1:  There are <math>10</math> <math>S</math>'s and <math>5</math> <math>I</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
 
−
          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
 
−
          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>.
 
−
          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 Vandermonde's Identity.
 
−
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.
 
−
    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.
 
−
          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>.
 
  
−
So, the total number of ways is <math>3\boxed{004}</math>
+
;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.
 +
:;Sub-case 1  --  There are <math>10</math> <math>S</math>'s and <math>5</math> <math>I</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 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 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>.
 +
::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].
 +
 
 +
;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.
 +
: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.
 +
::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>.
 +
 
 +
So, the total number of ways is <math>1+2002+1001=3\boxed{004}</math>

Revision as of 16:51, 7 March 2018

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 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 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 $1+2002+1001=3\boxed{004}$

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