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

Home > Just Math
Distinct Delivery Deduction (Posted on 2014-09-04) Difficulty: 3 of 5
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.)
Solution 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!

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.


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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information