Olimpiada Internacional de Matemáticas , Lista Corta 2001 Problema C6
Para un entero positivo \( n \), define una secuencia de ceros y unos como balanceada si contiene \( n \) ceros y \( n \) unos. Dos secuencias balanceadas \( a \) y \( b \) son vecinas si puedes mover uno de los \( 2n \) símbolos de \( a \) a otra posición para formar \( b \). Por ejemplo, cuando \( n = 4 \), las secuencias balanceadas \( 01101001 \) y \( 00110101 \) son vecinas porque el tercer (o cuarto) cero en la primera secuencia puede moverse a la primera o segunda posición para formar la segunda secuencia. Demuestra que existe un conjunto \( S \) de a lo más \( \frac{1}{n+1} \binom{2n}{n} \) secuencias balanceadas tal que toda secuencia balanceada es igual o es vecina de al menos una secuencia en \( S \).
0
0
Inicia sesión para agregar soluciones y pistas