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 "2001 AIME I Problems/Problem 14"

(→‎Solution 2 ( Less recursion than solution 1))
(→‎Solution 3 (Tedious Casework))
Line 39: Line 39:
  
 
==Solution 3 (Tedious Casework) ==
 
==Solution 3 (Tedious Casework) ==
−
We split the problem into cases using the number of houses that get mail. Let "|" represent a house that gets mail, and "o" represent a house that doesn't. With a fixed number of |, an o can be inserted between 2 |'s or on the very left or right. There cannot be more than one o that is free to arrange to be placed between two |'s because no three o's can be adjacent, but there can be a maximum of two o's placed on the very left or right. Note that according to the Pigeonhole Principle, no more than 10 houses can get mail on the same day.  
+
We split the problem into cases using the number of houses that get mail. Let "|" represent a house that gets mail, and "o" represent a house that doesn't. With a fixed number of |, an o can be inserted between 2 |'s or on the very left or right. There cannot be more than one o that is free to arrange to be placed between two |'s because no three o's can be adjacent, but there can be a maximum of two o's placed on the very left or right. Note that according to the [[Pigeonhole Principle|Pigeonhole Principle]], no more than 10 houses can get mail on the same day.  
  
 
Case 1: 10 houses get mail. No 2 adjacent houses can get mail on the same day, so there must be an o between every two |. <math>10-1=9</math> o's are fixed so we count the number of ways to insert <math>19 - 10 - 9 = 0</math> o's to <math>10+1 = 11</math> spots, or <math>\binom{11}{0} = 1</math>.
 
Case 1: 10 houses get mail. No 2 adjacent houses can get mail on the same day, so there must be an o between every two |. <math>10-1=9</math> o's are fixed so we count the number of ways to insert <math>19 - 10 - 9 = 0</math> o's to <math>10+1 = 11</math> spots, or <math>\binom{11}{0} = 1</math>.

Revision as of 21:40, 21 November 2018

Problem

A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible?

Solutions

Solution 1

Let $0$ represent a house that does not receive mail and $1$ represent a house that does receive mail. This problem is now asking for the number of $19$-digit strings of $0$'s and $1$'s such that there are no two consecutive $1$'s and no three consecutive $0$'s.

The last two digits of any $n$-digit string can't be $11$, so the only possibilities are $00$, $01$, and $10$.

Let $a_n$ be the number of $n$-digit strings ending in $00$, $b_n$ be the number of $n$-digit strings ending in $01$, and $c_n$ be the number of $n$-digit strings ending in $10$.

If an $n$-digit string ends in $00$, then the previous digit must be a $1$, and the last two digits of the $n-1$ digits substring will be $10$. So \[a_{n} = c_{n-1}.\]

If an $n$-digit string ends in $01$, then the previous digit can be either a $0$ or a $1$, and the last two digits of the $n-1$ digits substring can be either $00$ or $10$. So \[b_{n} = a_{n-1} + c_{n-1}.\]

If an $n$-digit string ends in $10$, then the previous digit must be a $0$, and the last two digits of the $n-1$ digits substring will be $01$. So \[c_{n} = b_{n-1}.\]

Clearly, $a_2=b_2=c_2=1$. Using the recursive equations and initial values: \[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \multicolumn{19}{c}{}\\\hline n&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\\\hline a_n&1&1&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65&86\\\hline b_n&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65&86&114&151\\\hline c_n&1&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65&86&114\\\hline \end{array}\]

As a result $a_{19}+b_{19}+c_{19}=\boxed{351}$.

Solution 2 ( Less recursion than solution 1)

Let $M_n$ represent the number of mail delivery patterns that end with the last house receiving mail. This is $b_n$ in Solution 1. Similarly define $A_n$ to be the number of mail delivery patterns that end with last house not receiving mail. This is just $a_n$ and $c_n$ in solution 1. Let $T_n$ be the total number of mail delivery patterns.

Here are the possible ending cases: the string ends in $1, 10,$ or $100$. The first case is just $M_n$. The second case is $M_{n-1}$. The third case is $M_{n-2}$. So we have $T_n = M_n + M_{n-1} + M_{n-2}$. Since we want $T_{19}$, it is just $M_{18} + M_{17} + M_{16}$. Now using the same logic as above we can find $M_n = M_{n-2} + M_{n-3}$ ( the cases are 01 and 001). We can refer back to solution 1's table and only keep track of $b_n$, ignoring both $a_n$ and $c_n$.

- MathLegend27

Solution 3 (Tedious Casework)

We split the problem into cases using the number of houses that get mail. Let "|" represent a house that gets mail, and "o" represent a house that doesn't. With a fixed number of |, an o can be inserted between 2 |'s or on the very left or right. There cannot be more than one o that is free to arrange to be placed between two |'s because no three o's can be adjacent, but there can be a maximum of two o's placed on the very left or right. Note that according to the Pigeonhole Principle, no more than 10 houses can get mail on the same day.

Case 1: 10 houses get mail. No 2 adjacent houses can get mail on the same day, so there must be an o between every two |. $10-1=9$ o's are fixed so we count the number of ways to insert $19 - 10 - 9 = 0$ o's to $10+1 = 11$ spots, or $\binom{11}{0} = 1$.

Case 2: 9 houses get mail. In this case, $9-1 = 8$ o's are fixed so we count the number of ways to insert $19 - 9 - 8 = 2$ o's to $9+1=10$ spots. However, there is also the case where two o's are both on the very left / right. When both o's that are free to arrange are put on a side, there are $10-1=9$ spots left to insert $2-2=0$ o's. Hence the total number of ways in this case is $\binom{10}{2} + 2\binom{9}{0} = 47$.

Case 3: 8 houses get mail. In this case, $8-1=7$ o's are fixed so we count the number of ways to insert $19-8-7=4$ o's to $8+1=9$ spots. When two o's are put to the very left / right, there are $9-1=8$ spots left to insert $4-2=2$ o's. We also need to take care of the case where two o's are on the very left and two o's are on the very right: we have $9-1-1=7$ spots to insert $4-2-2=0$ o's. Hence the total number of ways in this case is $\binom{9}{4} + 2\binom{8}{2} + \binom{7}{0} = 183$.

Case 4: 7 houses get mail. In this case, $7-1=6$ o's are fixed so we count the number of ways to insert $19-7-6=6$ o's to $7+1=8$ spots. When two o's are put to the very left / right, there are $8-1=7$ spots left to insert $6-2=4$ o's. When two o's are on the very left and two o's are on the very right, we have $8-1-1=6$ spots to insert $6-2-2=2$ o's. Hence the total number of ways in this case is $\binom{8}{6} + 2\binom{7}{4} + \binom{6}{2} = 113$.

Case 5: 6 houses get mail. We have to be careful in this case: $6-1=5$ o's are fixed so we are inserting $19-6-5=8$ o's to $6+1=7$ spots, which means that at least 1 of the 2 sides must have two o's. When 1 of the 2 sides have two o's, there are $7-1=6$ spots to insert $8-2=6$ o's. When both sides have two o's, there are $7-1-1=5$ spots to insert $8-2-2=4$ o's. Hence the total number of ways in this case is $2\binom{6}{6} + \binom{5}{4} = 7$.

When less than 6 houses get(s) mail, it's again not possible since at least three o's must be together (again, according to the Pigeonhole Principle). Therefore, the desired answer is $1+47+183+113+7=\boxed{351}$.

- MP8148

See also

2001 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_I_Problems/Problem_14&oldid=98909"