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"

m (typo)
m (minor)
Line 1: Line 1:
 
== Problem ==
 
== 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?
+
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?
  
 
== Solution ==
 
== Solution ==
Line 9: Line 9:
 
Let <math>a_n</math> be the number of <math>n</math>-digit strings ending in <math>00</math>, <math>b_n</math> be the number of <math>n</math>-digit strings ending in <math>01</math>, and <math>c_n</math> be the number of <math>n</math>-digit strings ending in <math>10</math>.  
 
Let <math>a_n</math> be the number of <math>n</math>-digit strings ending in <math>00</math>, <math>b_n</math> be the number of <math>n</math>-digit strings ending in <math>01</math>, and <math>c_n</math> be the number of <math>n</math>-digit strings ending in <math>10</math>.  
  
−
If an <math>n</math>-digit string ends in <math>00</math>, then the previous digit must be a <math>1</math>, and the last two digits of the <math>n-1</math> digits substring will be <math>10</math>.  
+
If an <math>n</math>-digit string ends in <math>00</math>, then the previous digit must be a <math>1</math>, and the last two digits of the <math>n-1</math> digits substring will be <math>10</math>. So
−
 
+
<cmath>a_{n} = c_{n-1}.</cmath>
−
So <math>a_{n} = c_{n-1}</math>
 
 
   
 
   
−
If an <math>n</math>-digit string ends in <math>01</math>, then the previous digit can be either a <math>0</math> or a <math>1</math>, and the last two digits of the <math>n-1</math> digits substring can be either <math>00</math> or <math>10</math>.  
+
If an <math>n</math>-digit string ends in <math>01</math>, then the previous digit can be either a <math>0</math> or a <math>1</math>, and the last two digits of the <math>n-1</math> digits substring can be either <math>00</math> or <math>10</math>. So
 +
<cmath>b_{n} = a_{n-1} + c_{n-1}.</cmath>
  
−
So <math>b_{n} = a_{n-1} + c_{n-1}</math>
+
If an <math>n</math>-digit string ends in <math>10</math>, then the previous digit must be a <math>0</math>, and the last two digits of the <math>n-1</math> digits substring will be <math>01</math>. So
 +
<cmath>c_{n} = b_{n-1}.</cmath>
  
−
If an <math>n</math>-digit string ends in <math>10</math>, then the previous digit must be a <math>0</math>, and the last two digits of the <math>n-1</math> digits substring will be <math>01</math>.
+
Clearly, <math>a_2=b_2=c_2=1</math>. Using the [[recursion|recursive]] equations and initial values:  
−
 
+
<cmath>\begin{tabular}[t]{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
−
So <math>c_{n} = b_{n-1}</math>.
 
−
 
 
−
Clearly, <math>a_2=b_2=c_2=1</math>. Using the recursive equations and initial values:  
 
−
 
 
−
<math>\begin{tabular}[t]{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
 
 
\multicolumn{19}{c}{}\\\hline
 
\multicolumn{19}{c}{}\\\hline
 
n&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\\\hline
 
n&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19\\\hline
Line 29: Line 25:
 
b_n&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65&86&114&151\\\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
 
c_n&1&1&2&2&3&4&5&7&9&12&16&21&28&37&49&65&86&114\\\hline
−
\end{tabular}</math>
+
\end{tabular}</cmath>
  
 
Therefore, the number of <math>19</math>-digit strings is <math>a_{19}+b_{19}+c_{19} = 86+151+114 = \boxed{351}.</math>
 
Therefore, the number of <math>19</math>-digit strings is <math>a_{19}+b_{19}+c_{19} = 86+151+114 = \boxed{351}.</math>
  
 
== See also ==
 
== See also ==
−
{{AIME box|year=2001|n=I|num-b=13|num-a=15}}
+
{{AIME box|year=2001|n=I|num-b=13|num-a=15|t=384210}}
 +
 
 +
[[Category:Intermediate Combinatorics Problems]]

Revision as of 11:06, 15 June 2008

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?

Solution

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{tabular}[t]{|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{tabular}\] (Error compiling LaTeX. Unknown error_msg)

Therefore, the number of $19$-digit strings is $a_{19}+b_{19}+c_{19} = 86+151+114 = \boxed{351}.$

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_AIME_I_Problems/Problem_14&oldid=26548"