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 re: a manual count solution | Comment 2 of 7 |
(In reply to a manual count solution by Ady TZIDON)

Well, I wasn't going to post my solution, but I love disagreeing with Ady, so here it is.  Ady has correctly identified the 151 distribution patterns that end with a 1.  There are also 114 that end with a single 0 and 86 that end in 00.  151 + 114 + 86 = 351, which is my answer.


I got my solution iteratively, using Excel.
Let f(n) be the number of strings of length n that end with a 1.
Let g(n) be the number of strings of length n that end with a single 0.
Let h(n) be the number of strings of length n that end with a double 0.

Then f(n+1) = g(n) + h(n)
        g(n+1) = f(n)
        h(n+1) = g(n)

My Excel table looked as follows:

n f(n) g(n) h(n) Total
1 1 1 0 2
2 1 1 1 3
3 2 1 1 4
4 2 2 1 5
5 3 2 2 7
6 4 3 2 9
7 5 4 3 12
8 7 5 4 16
9 9 7 5 21
10 12 9 7 28
11 16 12 9 37
12 21 16 12 49
13 28 21 16 65
14 37 28 21 86
15 49 37 28 114
16 65 49 37 151
17 86 65 49 200
18 114 86 65 265
19 151 114 86 351








  Posted by Steve Herman on 2014-09-04 17:24:41
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 (6)
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