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$.
"La matemática es para pensar. El fútbol es para sacar mi instinto animal y decirle al árbitro hdp te voy a m4t4r." Anónimo
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.