Art, the mail carrier delivers mail to the 19 houses on the east side of a street.

Art notices that:
(i) No two adjacent houses ever get mail on the same day, and:
(ii) There are never more than two houses in a row that get no mail on the same day.

How many distinct patterns of mail delivery are possible?

Each daily mail distribution can be represented by a binary sequence of 19 bits, consisting of m segments of 01 and n segments of 001.

Taking in account all possible distribution boils down to evaluating the number of solution of 2m+3n=19 for sequences commencing with 0  plus  the number of solution of 2m+3n=18 for sequences commencing with 1.

1.  2m+3n= 19 renders     (m,n)=  (2,5) ; (5,3) ; (8,1)

2.  2m+3n= 18 renders     (m,n)=  (0,6) ; (3,4) ; (6,2) ; (9,0)

(2,5)  can be composed within the sequence in C(7,2) i.e. 21 ways

(5,3) can be composed within the sequence in C(8,3) i.e. 56 ways

(8,1) can be composed within the sequence in C(9,1) i.e. 9 ways

Total for case a 21+56+9=86 ways

Similar reasoning for case b gets :    C(6,0)+ C(7,3)+ C(8,2)+ C(9,0)= 1+35+28+1=65

So the total number of distinct distribution patterns is 86+65=151 ways

r  e  v  i  s  i  o  n:     Not quite!

after reading Steve Hermans comment

 the above number ,call it F(19)  addresses only the sequences  terminating wth 1,- forgetting those that end with sngle zer0 or 00.

Many sincere thanks for SH's comments 

 

Edited on September 5, 2014, 4:06 am

Posted by Ady TZIDON on 2014-09-04 14:43:10