All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Distinct Delivery Deduction (Posted on 2014-09-04)
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?

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 a manual count solution | Comment 1 of 7

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!

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

Then the total T requested for n houses is:
T=F(n) + F(n-1) + F(n-2)
For n=19:

(F19)= 151
(F18)=65+49=114
(F17)= 49+37=86   CALCULATED as above

This sums up to 351 (check it!).

****

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

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: