OME Local |
OME Nacional |
OIM |
OME Andalucía |
Retos UJA |
En la figura se pueden ver ejemplos de los caminos propuestos para $n=5$, $n=6$ y $n=7$, donde se han usado colores distintos para cada jugador y se han coloreado los triangulitos $\triangle$ y $\bigtriangledown$ asignados.
Nota. No se ha dicho realmente cómo se asignan los triángulos $\triangle$ y $\bigtriangledown$ y en realidad hay muchas formas de hacerlo manteniendo la conexión del territorio de cada jugador. Una forma práctica de asignar es darle a cada jugador el triángulo más cercano a su vértice (caso $n=3k$ o $n=3k+2$) o a su lado (caso $n=3k+1$) y repartir aquellos triángulos que equidistan de dos jugadores de forma simétrica (no hay ninguno que equidiste de los tres jugadores en ninguno de los dos casos).
Veamos en primer lugar que esto resuelve el problema original. Para cada elemento de $a\in S$, cada uno de los $p^2+p=(p+1)p$ elementos restantes de $S$ tiene que estar en un único subconjunto que también contenga a $a$, lo que nos fuerza a que haya exactamente $p+1$ subconjuntos que contengan a $a$ y esto prueba que en cada columna de la tabla habrá exactamente $k=p+1$ elementos. Además, esta configuración es óptima, ya que al haber exactamente $p+1$ subconjuntos que contienen a cada $a\in S$, iterando sobre todos los $a\in S$ tendremos un total de $(p^2+p+1)(p+1)$ subconjuntos, cada uno contado $p+1$ veces (una por cada uno de sus elementos), lo que nos dice que el número de subconjuntos debe ser $p^2+p+1$.
El mejor modelo de subconjuntos tales dos elementos cualesquiera definen exactamente uno de los subconjuntos lo dan las rectas del plano: dos puntos definen una única recta que pasa por ellos. Vamos a hacer lo mismo pero en un conjunto de $p$ elementos, para lo que vamos a trabajar en lo que sigue con puntos de coordenadas enteras módulo el primo $p$. Concretamente, consideraremos los $p^2$ puntos $(x,y)$ que cumplen $0\leq x,y\lt p$ (luego añadiremos los $p+1$ puntos restantes para que las rectas paralelas también se corten en algún punto, la otra condición que buscamos). Las rectas módulo $p$ son los subconjuntos dados por una ecuación $ax+by\equiv c\ (\text{mod }p)$ siendo $0\leq a,b,c\lt p$ y $a$ y $b$ no ambos nulos. Hay dos tipos de rectas:
Por ejemplo, en la imagen, hemos dibujado las rectas clasificadas según su pendiente para $p=5$ y los distintos colores corresponden a cambiar $n$. Veamos algunas propiedades:
Con todo esto en mente, vamos a añadir $p+1$ elementos adicionales $P_0,P_1,\ldots,P_p,P_v$ a nuestro plano: a cada recta de ecuación $y\equiv m+nx$ le añadimos el $P_m$, según su pendiente, y a cada recta $x\equiv m$ le añadimos $P_v$. De esta forma, rectas paralelas tienen un punto adicional común y obtenemos $p(p+1)$ rectas con $p+1$ puntos cada una. Nos falta definir una última recta: la formada por los puntos $P_0,P_1,\ldots,P_p,P_v$. Es inmediato comprobar que estos $p^2+p+1$ subconjuntos cumplen las condiciones (a) y (b) propuestas y esto demuestra el enunciado.
Nota. Aunque parezca increíblemente sofisticado, lo que se hace en la solución no es otra cosa que construir el plano proyectivo sobre un cuerpo de $p$ elementos. Las rectas afines o proyectivas sobre cuerpos finitos dan multitud de ejemplos con interesantes propiedades combinatorias.