Define $facevalue$ of $X$ as $1$ and that of $0$ as $-1$. Let $S_{k}$ be the sum of the facevalues of the first $k$ elements of the string. A string is balanced if and only if for any two naturals, l and m, $S_{l}-S_{m}$ $\in$ $\{-2, 2 \}$. Clearly, $S_{k}$ and $S_{k+1}$ can differ only by $1$. So if we write a sequence for $S_{i}$, say $1,0,{-1},0,{-1},0,1$, we are actually referring to the sequence XOOXOXX. which satisfies the given conditions. So if we write such a balanced sequence of $S_{i}$, we have effectively written a balanced string. Use the following rules to write a sequence of $S_{i}$, and then count the total number of strings that you can write: 1. Assume that the first character of the balanced string is X. At the end double your answer. Each $S_{i}$ string thus starts with $1$ 2. Note that in each string of $S_{i}$, there can only appear $3$ different characters. These may be $\{-1, 0, 1\}$ or $\{0, 1, 2\}$ $-2$ can not appear as $1$ exists in the string. 3. Consider each of the above two cases and count the number of possible strings in each case. The easiest way is to find manually for trivial cases ,then prove by induction.

This was as I solved it in the TST, Map each string to a diagonal lattice path starting at the origin.Say X corresponds to a step of length sqrt (2) at 45 degrees to the positive x axis and O to a -45. Then every balanced string of length is bounded by a 2*n rectangle and vice versa.Thus we have a bijection,count the number of such paths, (easy recursive calculation). Cheers Bhargav

This problem was also on Croatian MEMO Selection Test 2007. It was one of the most difficult problems.