Ibero 2008 - P6

Avatar de Usuario
Gianni De Rico

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

Ibero 2008 - P6

Mensaje sin leer por Gianni De Rico » Mar 26 Jun, 2018 1:51 pm

Biribol es un juego jugado entre dos equipos de $4$ personas cada uno (los equipos cambian después de cada juego). Hallar todos los valores de $n$ para los cuales es posible armar un torneo con $n$ jugadores de forma tal que cada par de personas juega al biribol en equipos contrarios exactamente una vez.
[math]

Avatar de Usuario
Gianni De Rico

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

Re: Ibero 2008 - P6

Mensaje sin leer por Gianni De Rico » Jue 09 Ago, 2018 8:25 pm

Spoiler: mostrar
Armemos el grafo donde los vértices son los jugadores están conectados por una arista si y sólo si jugaron en equipos contrarios. Del enunciado sale que el grafo es simple, luego, al estar completo tendrá exactamente $\binom{n}{2}=\frac{n(n-1)}{2}$ aristas.
Ahora, si entre dos jugadores hay una arista, entonces no pueden volver a jugar, luego, en cada partida a cada vértice se le agregan $4$ aristas y en total se agregan $16$ aristas. Luego, $16\mid \frac{n(n-1)}{2}\Rightarrow 32\mid n(n-1)$. Además, el grado de cada vértice es invariante módulo $4$, por lo que siempre será múltiplo de $4$. Luego, si miramos un vértice en particular, tenemos que la cantidad de vecinos es múltiplo de $4$, de donde $n\equiv 1(4)$, por lo que es corpimo con $32$ y $32\mid n-1\Rightarrow n=32k+1$.

Veamos por inducción que se puede para todo $k\in \mathbb{N}$.
Para el caso base $k=1$ tenemos $n=33$, numeramos las personas del $1$ al $33$, y formamos un equipo con las primeras $4$ y otro con las personas $5$, $9$, $13$, y $17$, luego, vamos moviendo los equipos hacia la derecha. De esta forma, cada persona está en exactamente $4$ equipos, y juega contra otros $4$, luego, juega contra $32$ personas. Además éstas personas son distintas, ya que todas están separadas de a $4$ y las otras personas son consecutivas.
Ahora, supongamos que se puede para $k$, veamos que se puede para $k+1$.
Tomamos una persona genial $G$ y otras $32k$ personas, y las hacemos jugar un torneo, podemos por hipótesis inductiva. Después hacemos jugar a $G$ y las $32$ personas sobrantes otro torneo (podemos porque es el caso base). Por último, dividimos el grupo de $32k$ personas en equipos disjuntos de $4$ personas, y el grupo de $32$ personas en equipos disjuntos de $4$ personas, y hacemos que todos los equipos formados por personas del grupo de $32k$ jueguen contra los equipos formados por personas del grupo de $32$. Entonces cada persona juega contra otra exactamente una vez. La inducción está completa.

Queda demostrado que $n$ cumple si y sólo si $n=32k+1$ con $k\in \mathbb{N}$
[math]

Responder