Given a finite string $S$ of symbols $X$ and $O$, we write $@(S)$ for the number of $X$'s in $S$ minus the number of $O$'s. (For example, $@(XOOXOOX) =-1$.) We call a string $S$ balanced if every substring $T$ of (consecutive symbols) $S$ has the property $-2 \leq @(T) \leq 2$. (Thus $XOOXOOX$ is not balanced since it contains the sub-string $OOXOO$ whose $@$-value is $-3$.) Find, with proof, the number of balanced strings of length $n$.
Problem
Source: From the Indian Team Selection Tests 2007
Tags: geometry, rectangle, combinatorics unsolved, combinatorics
16.06.2007 09:49
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.
19.06.2007 15:37
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
22.06.2007 10:45
This problem was also on Croatian MEMO Selection Test 2007. It was one of the most difficult problems.