Cono Sur 2021 - P3

Problemas que aparecen en el Archivo de Enunciados.
Felibauk

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022
Mensajes: 43
Registrado: Dom 19 Ene, 2020 12:43 am
Medallas: 9
Nivel: 1

Cono Sur 2021 - P3

Mensaje sin leer por Felibauk »

En un club de tenis, cada socio tiene exactamente $k>0$ amigos, y se organiza un torneo por rondas para que cada par de amigos se enfrenten en partidas una única vez. Las rondas se juegan en partidas simultáneas anotando parejas hasta que no se pueda anotar nadie más (es decir, entre las personas no anotadas no hay una pareja de amigos que tengan su partida pendiente). Determine el máximo número de rondas que el torneo puede tener, en función de $k$.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
Mensajes: 561
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 15
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Cono Sur 2021 - P3

Mensaje sin leer por Turko Arias »

Spoiler: mostrar
Lema: El torneo no puede tener más de $2k-1$ rondas.

Demostración:
Spoiler: mostrar
Consideremos la última ronda del torneo. Supongamos que en una de las partidas de esa ronda se enfrentan $A$ y $B$. Notemos que si en alguna ronda previa no jugaron ni $A$ ni $B$ entonces... En esa ronda podrían haber jugado entre ellos, luego hasta la última ronda no sucedió nunca que $A$ y $B$ se encuentren ambos sin jugar. Por otro lado, como es la última ronda tenemos que $A$ ya jugó $k-1$ partidas y que $B$ ya jugó $k-1$ partidas, luego antes de la última ronda sucedieron como máximo $(k-1)+(k-1)=2k-2$ rondas y tiene como máximo $2k-1$ rondas el torneo.

Pensando los socios como nodos de un grafo y a las amistades como aristas, planteamos los siguientes ejemplos para alcanzar la cota:

Si $k$ es par entonces consideramos el $k+1$ cliqué. Como la cantidad de nodos es impar, en cada ronda va a haber un jugador que no juegue. Notamos que mientras se lleven adelante todas las partidas del $k$ cliqué que no contiene a $A$ (un total de $k-1$ partidas) el no va a jugar. Notamos también que las únicas partidas que restan jugar son las $k$ partidas en las que participa $A$, luego tenemos un total de $2k-1$ partidas.


Si $k$ es impar, consideramos un grafo con $2k$ nodos. Sean $A, x_1, x_2,...,x_{2k-2}, B$ los nodos. Armamos dos $k$ cliqués, en uno los nodos $A, x_1,...,x_{k-1}$, en otro los nodos $x_k,...x_{2k-2}, B$. Por último, conectamos los nodos $A-B$, $x_1-x_k$, $x_2-x_{k+1}$, ..., $x_{k-1}-x_{2k-2}$. Notamos que el grado de cada nodo resulta ser $k$.

Consideremos ahora los siguientes dos $k-1$ cliqués: el que tiene los nodos $A, x_1,..., x_{k-2}$ y el que tiene los nodos $x_k,x_{k+1},...,x_{2k-2}$. Durante las primeras $k-2$ rondas, se juegan todas las partidas entre si dentro de esos cliqués y $x_{k-1}$ y $B$ no juegan ninguna.

Para este momento, $A, x_1,...,x_{k-2},x_k,...,x_{2k-2}$ ya jugaron $k-2$ partidas y $x_{k-1}$ y $B$ no jugaron ninguna.

Durante los $k$ rondas siguientes, $x_{k-1}$ juega con $x_1, x_2, ..., x_{k-2}, x_{2k-2}, A$ respectivamente y durante los primeros $k-1$ de esas rondas $B$ juega con $x_{2k-2}, x_k, x_{k+1},...,x_{2k-3}$ respectivamente. Notemos que las jugadas no se superponen, y en la ronda $k$, $B$ solo puede jugar con $A$ pero $A$ juega con $x_{k-1}$ por lo que $B$ no juega en esa ronda. Por último, en la última ronda juegan $A$ y $B$ y queda completado el torneo con $2k-1$ rondas.

El grafo para $k=5$ de las amistades:
Spoiler: mostrar
P3 Cono 2021.jpg
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Responder