2001 IMO Shortlist S10

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$ .

对于正整数 $n$，如果它包含 $n$ 个零和 $n$ 个，则定义要*平衡*的零和一序列。如果您可以将 $a$ 的 $2n$ 符号之一移动到另一个位置以形成 $b$ ，则两个平衡序列 $a$ 和 $b$ 是*邻居*。例如，当 $n = 4$ 时，平衡序列 $01101001$ 和 $00110101$ 是邻居，因为第一个序列中的第三个(或第四个)零可以移动到第一个或第二个位置以形成第二个序列。证明存在一组 $S$ 至多 $\frac{1}{n+1} \binom{2n}{n}$ 平衡序列，使得每个平衡序列等于 $S$ 中的至少一个序列或者是 $S$ 中至少一个序列的邻居。