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**