Putnam 1996, Problem B-5

Given a finite string \( S \) of symbols \( X \) and \( O \), we write \( \Delta(S) \) for the number of \( X \)'s in \( S \) minus the number of \( O \)'s. For example, \( \Delta(XOOXOOX) = -1 \). We call a string \( S \) **balanced** if every substring \( T \) of (consecutive symbols of) \( S \) has \( -2 \leq \Delta(T) \leq 2 \). Thus, \( XOOXOOX \) is not balanced, since it contains the substring \( OOXOO \). Find, with proof, the number of balanced strings of length \( n \).

Solution:
Consider a \(1 \times n\) checkerboard, in which we write an \(n\)-letter string, one letter per square. If the string is balanced, we can cover each pair of adjacent squares containing the same letter with a \(1 \times 2\) domino, and these will not overlap (because no three in a row can be the same). Moreover, any domino is separated from the next by an even number of squares, since they must cover opposite letters, and the sequence must alternate in between.  

Conversely, any arrangement of dominoes where adjacent dominoes are separated by an even number of squares corresponds to a unique balanced string, once we choose whether the string starts with \(X\) or \(O\). In other words, the number of balanced strings is twice the number of acceptable domino arrangements.  

We count these arrangements by numbering the squares \(0, 1, \ldots, n - 1\) and distinguishing whether the dominoes start on even or odd numbers. Once this is decided, one simply chooses whether or not to put a domino in each eligible position. Thus we have \(2^{\lfloor n/2 \rfloor}\) arrangements in the first case and \(2^{\lfloor (n - 1)/2 \rfloor}\) in the second, but note that the case of no dominoes has been counted twice. Hence the number of balanced strings is  
\[
2^{\lfloor (n + 2)/2 \rfloor} + 2^{\lfloor (n + 1)/2 \rfloor} - 2.
\]