# Mock AIME 1 2006-2007 Problems/Problem 11

## Problem

Let be the set of strings with only 0's or 1's with length such that any 3 adjacent place numbers sum to at least 1. For example, works, but does not. Find the number of elements in .

## Solution

We will solve this problem by constructing a recursion satisfied by .

Let be the number of such strings of length ending in 1, be the number of such strings of length ending in a single 0 and be the number of such strings of length ending in a double zero. Then and .

Note that . For we have (since we may add a 1 to the end of any valid string of length to get a valid string of length ), (since every valid string ending in 10 can be arrived at by adding a 0 to a string ending in 1) and (since every valid string ending in 100 can be arrived at by adding a 0 to a string ending in 10).

Thus . Then using the initial values we can easily compute that .

## Solution 2

We come up with a different recursion. Overcounting, we can add either a 0 or a 1 onto any string of length n. However, we have to back out the times we've added a third 0. In that case, the previous two will be 0, the one before that will be one, and preceeding that can be any string of length . We thus have the recursion . We proceed as above.