Problem:
A mail carrier delivers mail to the nineteen houses on the east side of Elm Street. The carrier notices that no two adjacent houses ever get mail on the same day, but that there are never more than two houses in a row that get no mail on the same day. How many different patterns of mail delivery are possible?
Solution:
The first condition implies that at most ten houses get mail in one day, while the second condition implies that at least six houses get mail. If six houses get mail, they must be separated from each other by a total of at least five houses that do not get mail. The other eight houses that do not get mail must be distributed in the seven spaces on the sides of the six houses that do get mail. This can be done in ways: put two at each end of the street and distribute the other four in ways, or put one in each of the seven spaces and an extra one at one end of the street or the other. If seven houses get mail, they create eight spaces, six of which must contain at least one house that does not get mail. The remaining six houses that do not get mail can be distributed among these eight spaces in ways: six of the eight spaces can be selected to receive a single house in ways; two houses can be placed at each end of the street and two intermediate spaces be selected in ways; and two houses can be placed at one end of the street and four spaces selected for a single house in ways. Similar reasoning shows that there are patterns when eight houses get mail, and patterns when nine houses get mail. When ten houses get mail, there is only one pattern, and thus the total number of patterns is .
Consider -digit strings of zeros and ones, which represent no mail and mail, respectively. Such a sequence is called acceptable if it contains no occurrences of or . Let be the number of acceptable -digit strings, let be the number of acceptable -digit strings in which follows the leftmost , and let be the number of acceptable -digit strings in which follows the leftmost . Notice that for . Deleting the leftmost occurrence of shows that , and deleting from the leftmost occurrence of shows that . It follows that for . It is straightforward to verify the values of , and . Then the recursion can be used to find that .
The problems on this page are the property of the MAA's American Mathematics Competitions