Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Vamos a asignar a cada jugador una casilla de un tablero $p\times p$. En la ronda $0$, se organizan $p$ partidas en cada una de las cuales participan todos los jugadores de una fila del tablero. Ahora organizamos $p$ rondas más con $p$ partidas cada una, de forma que cada partida incluye exactamente un jugador de cada fila. Concretamente, en la partida $j$ de la ronda $i$ (con $1\leq i,j\leq p$) participan los jugadores que se encuentran en las casillas de coordenadas $(k,j+ik)$ módulo $p$ con $1\leq k\leq p$.

Los jugadores que se encuentran en las casillas $(a,b)$ y $(c,d)$ jugarán entre ellos en la ronda $0$ cuando $a=c$. En caso contrario, jugarán en la partida $j=(ab-cd)(a-c)^{-1}$ de la ronda $i=(b-d)(a-c)^{-1}$, donde los inversos se consideran módulo $p$. Esto se comprueba fácilmente ya que ambos puntos deben escribirse de la forma $(a,b)=(k_1,j+ik_1)$ y $(c,d)=(k_2,j+ik_2)$ para $1\leq k_1,k_2\leq p$, lo cual equivale al sistema lineal formado por $j+ai=b$ y $j+ci=d$, cuya solución única módulo $p$ es la indicada anteriormente.

Esto nos da un total de $p(p+1)$ partidas en las que todas las parejas se han enfrentado al menos una vez. Como en cada partida cada jugador se enfrenta a $p-1$ jugadores (distintos de sí mismo), el mínimo número de rondas necesario para enfrentarse a todos será $p+1$ (así, se enfrenta a como mucho $(p+1)(p-1)=p^2-1$ jugadores distintos, que son todos menos él mismo) y en cada ronda hay un máximo de $p$ partidas. Deducimos así que el mínimo número de partidas necesario es $p(p+1)$ luego la forma que hemos dado de emparejar hace que este sea realmente el mínimo que nos pide el problema. Deducimos así, que el número que nos piden es $p+1$.

Nota. Si consideramos $\mathbb{Z}_p$, el cuerpo de $p$ elementos, como si fuera una recta geométrica, el plano sería $\mathbb{Z}_p\times\mathbb{Z}_p$ y los conjuntos que hemos considerado no son otra cosa que las rectas de este plano, es decir, los conjuntos de puntos $(x,y)\in\mathbb{Z}_p\times\mathbb{Z}_p$ dados por una ecuación de la forma $ax+by=c$ con $a,b\in\mathbb{Z}_p$ y realizando todas las operaciones módulo $p$. Cada ronda se corresponde con una pendiente de la recta (añadiendo las rectas verticales) y cada partida de la ronda con una ordenada en el origen.