Categories
AIME I Algebra Arithmetic Math Olympiad USA Math Olympiad

Patterns and Integers | AIME I, 2001 | Question 14

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

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


But try the problem first…

Answer: is 351.

Source
Suggested Reading

AIME I, 2001, Question 14

Elementary Number Theory by David Burton

Try with Hints


First hint

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

Second Hint

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}\)

Final Step

\(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.

Subscribe to Cheenta at Youtube


Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.