Ibero 2005 - P6

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 829
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Ibero 2005 - P6

Mensaje sin leer por Gianni De Rico » Sab 04 Ago, 2018 5:44 pm

Sea $n$ un entero positivo. Se marcan en una recta los puntos $A_1,A_2,\ldots ,A_{2n}$. Y se colorean los puntos de azul o rojo de la siguiente manera: Se dibujan $n$ circunferencias disjuntas dos a dos, cada una con diámetro $A_iA_j$ para $1\leqslant i<j\leqslant 2n$ de forma que cada punto $A_k$ pertenezca a exactamente una circunferencia. Dos puntos de la misma circunferencia se pintan del mismo color.
Determinar la cantidad de formas distintas de colorear los $2n$ puntos siguiendo este procedimiento.
[math]

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 829
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Ibero 2005 - P6

Mensaje sin leer por Gianni De Rico » Sab 04 Ago, 2018 5:48 pm

Spoiler: mostrar
Dos puntos se conectan si son el diámetro de una de las circunferencias. Dentro de cada circunferencia debe haber una cantidad par de puntos, pues en caso contrario quedaría un punto que debe conectarse con un punto de afuera de la circunferencia, luego, estas no son disjuntas, absurdo. Se sigue que si dos puntos se conectan entonces son de distinta paridad, luego, la cantidad de puntos pares pintados de rojo es la misma que la cantidad de puntos impares pintados de rojo. Como hay $n$ puntos pares y $n$ puntos impares, la cantidad de formas de elegir $2k$ puntos rojos es $\binom{n}{k}^2$, ya que para cada forma de elegr $k$ puntos rojos pares hay $\binom{n}{k}$ formas de elegir los puntos rojos impares, y hay $\binom{n}{k}$ formas de elegir los puntos rojos pares. Por lo tanto, la cantidad de formas de elegir los puntos rojos es $\sum \limits_{k=0}^n \binom{n}{k}^2=\binom{2n}{n}$.

Veamos que todas son alcanzables.
Dada una coloración, comenzando desde la izquierda conectamos cada punto con el primer punto de su color que aparezca, como la cantidad de puntos entre dos puntos del mismo color es par, entonces las circunferencias son todas disjuntas, y la coloración cumple con las condiciones del enunciado.
[math]

Responder