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.)
 re: a manual count solution | Comment 2 of 7 |

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

 Search: Search body:
Forums (0)