2001 AIME I Problems/Problem 14

From AoPSWiki

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}{}\\\hlinen&2&3&4&5&6&7...$

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

2001 AIME I (Problems • Resources)
Preceded by Problem 13	Followed by Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Personal tools

Navigation

Search

Toolbox

2001 AIME I Problems/Problem 14

From AoPSWiki

Problem

Solution

See also