Try this beautiful problem from the American Invitational Mathematics Examination I, AIME I, 2001 based on Patterns and integers.

## Patterns and integers – AIME I, 2001

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.

- is 107
- is 351
- is 840
- cannot be determined from the given information

**Key Concepts**

Algebra

Patterns

Integers

## Check the Answer

Answer: is 351.

AIME I, 2001, Question 14

Elementary Number Theory by David Burton

## Try with Hints

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.

## Other useful links

- https://www.cheenta.com/equations-and-integers-aime-i-2008-question-4/
- https://www.youtube.com/watch?v=5_c9ZkX-Wgo&t=60s