Q36 Matemática  (IMO Shortlist 2001)

Para um inteiro positivo $n$, defina uma sequência de zeros e uns a serem balanceados se contiver $n$ zeros e $n$ uns. Duas sequências balanceadas $a$ e $b$ são vizinhas se você puder mover um dos símbolos $2n$ de $a$ para outra posição para formar $b$. Por exemplo, quando $n=4$, as sequências balanceadas $01101001$ e $00110101$ são vizinhas porque o terceiro (ou quarto) zero na primeira sequência pode ser movido para a primeira ou segunda posição para formar a segunda sequência. Prove que existe um conjunto $S$ de no máximo $\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ sequências balanceadas tal que toda sequência balanceada é igual ou vizinha de pelo menos uma sequência em $S$.