Patterns and Integers | AIME I, 2001 | Question 14

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, find the number of different patterns of mail delivery are possible.

0=house receive no mail 1=house receives mail and last two digit is not 11 then 00, 01 and 10 let \(a_{n}\)=number of n digit string ending 00,\(b_{n}\)=number of n digit string ending 01 \(c_{n}\)=number of n digit string ending 10

when nth digit ends in 00 then previous digit is 1 and the last two digits in the n-1 th substring is 10 then \(a_{n}=c_{n-1}\) when nth digit string ends in 01 then previous digit 0 or 1 and the last two digits in the n-1 digit substring is 00 or 10 then \(b_{n}=a_{n-1}+c_{n-1}\) when nth digit string ends in 10 then previous digit 0 and the last two digit of the n-1 digit substring is 01 then \(c_{n}=b_{n-1}\)

\(a_{n} b_{n} c_{n}\)

for n=2 , 1 1 1

for n=3 , 1 2 1

for n=4 , 1 2 2

for n=5 , 2 3 2

for n=6 , 2 4 3

for n=7 , 3 5 4

for n=8 , 4 7 5

for n=9 , 5 9 7

for n-10 , 7 12 9

for n=11 , 9 16 12

for n=12, 12 21 16

for n=13 , 16 28 21

for n=14 , 21 37 28

for n=15 , 28 49 37

for n=16 , 37 65 49

for n=17 , 49 86 65

for n=18 , 65 114 86

for n=19 , 86 151 114

then \(a_{19}+b_{19}+c_{19}\)=86+151+114=351.

AMC - AIME Boot Camp... for brilliant students.

Use our exclusive one-on-one plus group class system to prepare for Math Olympiad

Learn More

Subscribe to Cheenta at Youtube