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?
I was expecting something fibonacci-like when I read this problem, and I now see it, based on examining my table.
Let T(n) be the total distinct patterns of delivery if there are n houses.
T(1) = 2
T(2) = 3
T(3) = 4
Thereafter, T(n) = T(n-3) + T(n-2)
So T(4) = 2 + 3 = 5
T(5) = 3 + 4 = 7
T(19) = T(16)+T(17) = 151 + 200 = 351
In this puzzle, there are 1 or 2 non-delivered houses between every delivered house. If instead there were 0 or 1 non-delivered houses between every pair of delivered houses, then we would have had a true fibonacci.
Edited on September 4, 2014, 5:39 pm