For a positive integer
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
define a sequence of zeros and ones to be balanced if it contains
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
zeros and
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
ones. Two balanced sequences
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
and
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
are neighbors if you can move one of the
![2n](/media/m/d/2/d/d2da874dc9bc356be9468cdbd57fbfdf.png)
symbols of
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
to another position to form
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
. For instance, when
![n = 4](/media/m/a/8/5/a855b286759b88abcea3d3dbbfe88d81.png)
, the balanced sequences
![01101001](/media/m/d/1/7/d1751f9d1ed28b5f8eee5b68adeb1a7b.png)
and
![00110101](/media/m/a/c/d/acd90b271f69c7f515f234a2e9e6b21d.png)
are neighbors because the third (or fourth) zero in the first sequence can be moved to the first or second position to form the second sequence. Prove that there is a set
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
of at most
![\frac{1}{n+1} \binom{2n}{n}](/media/m/d/3/f/d3f7180a741a326a6c1b417c2e5fe5ff.png)
balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in
![S](/media/m/c/6/3/c63593c3ec0773fa38c2659e08119a75.png)
.
%V0
For a positive integer $n$ define a sequence of zeros and ones to be balanced if it contains $n$ zeros and $n$ ones. Two balanced sequences $a$ and $b$ are neighbors if you can move one of the $2n$ symbols of $a$ to another position to form $b$. For instance, when $n = 4$, the balanced sequences $01101001$ and $00110101$ are neighbors because the third (or fourth) zero in the first sequence can be moved to the first or second position to form the second sequence. Prove that there is a set $S$ of at most $\frac{1}{n+1} \binom{2n}{n}$ balanced sequences such that every balanced sequence is equal to or is a neighbor of at least one sequence in $S$.