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

Solución. El volumen del cubo de arista $n$ tiene que ser al menos $1996$ ya que cada cubo de los $1996$ con aristas naturales tiene volumen mayor o igual que $1$. Por lo tanto, $n^3\geq 1996$, de donde $n\geq 13$. Si probamos que un cubo de arista $13$ puede dividirse en $1996$ cubos de aristas números naturales, habremos terminado y $13$ será la respuesta.

En efecto, tenemos que, usando $1970$ cubos de arista $1$, $25$ cubos de arista $2$ y un cubo de arista $3$ se consigue el resultado ya que $13^3=1970\cdot 1^3+25\cdot 2^3+1\cdot 3^3$.

Solución. Cada fila del tablero como un subconjunto de $k=p+1$ elementos (los que están marcados con el número $0$) de un conjunto $S$ de $k^2-k+1=p^2+p+1$ elementos. Aparecerá un rectángulo con $0$ en sus vértices cuando dos de los subconjuntos así formados tengan al menos dos elementos en su intersección. La idea será construir $p^2+p+1$ subconjuntos de un conjunto $S$ de $p^2+p+1$ (cada subconjunto con $p+1$ elementos) cumpliendo estas dos condiciones:

1. Dos elementos de $S$ pertenecen simultáneamente a exactamente uno de los subconjuntos.
2. Dos subconjuntos cualesquiera tienen intersección no vacía (y, por tanto, formada por un único elemento por (a)).

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:

• Verticales. Se obtienen para $b\equiv 0$, luego $a\not\equiv 0$ y podemos despejar $x\equiv a^{-1}c$ (siendo $a^{-1}$ el inverso de $a$ módulo $p$). Por tanto, las podemos escribir como $x\equiv n$ para algún $0\leq n\lt p$.
• No verticales. Si $b\not\equiv 0$, podemos despejar $y\equiv b^{-1}c-b^{-1}ax$. Las podemos escribir como $y\equiv mx+n$ para ciertos $0\leq m,n\lt p$.

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:

• Cada recta tiene exactamente $p$ elementos. Por un lado, la recta vertical $x\equiv n$ tiene a los $p$ elementos $(n,y)$ para $0\leq y\lt p$. Por otro lado, la recta no vertical $y\equiv mx+n$ tiene también $p$ puntos, uno para cada elección $0\leq x\lt p$ ya que sólo hay que calcular $y$, que está despejado.
• Dos rectas se cortan en un único punto salvo que sean paralelas. En efecto, el sistema formado por dos rectas verticales distintas es incompatible (son paralelas), al igual que el formado por dos rectas no verticales de la misma pendiente. Si tomamos una vertical y una no vertical o bien dos no verticales con distinta pendiente, el sistema se puede resolver fácilmente módulo $p$ y tenemos una única solución.
• Dada una recta, hay exactamente $p$ rectas paralelas a ella (incluyéndo a la propia recta), lo que nos da un total de $p(p+1)$ rectas. Observemos que $p^2$ de ellas son no verticales (según elección de $0\leq m,n\lt p$ y hay $p$ para cada pendiente) y las $p$ restantes son las verticales.

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.

Solución. Llamemos $S(n)$ a la suma de fracciones que nos dice el enunciado y veamos que $S(n)=\frac{1}{2}$ por inducción sobre $n$. En el caso inicial $n=2$, la única fracción que cumple esos requisitos es $\frac{1}{2}$ para $a=1$ y $b=2$, luego $S(2)=\frac{1}{2}$. Supongamos que $S(n)=\frac{1}{2}$ para cierto $n\geq 2$ y probemos que $S(n+1)=\frac{1}{2}$. Observemos que las sumas $S(n)$ y $S(n+1)$ contienen los mismos sumandos excepto los siguientes:

• Los sumandos que aparecen en $S(n)$ y no en $S(n+1)$ son aquellos en que $a+b=n+1$.
• Los sumandos que aparecen en $S(n+1)$ y no en $S(n)$ son aquellos en que $b=n+1$.

Ahora bien, cada par $(a,b)$ de primos relativos con $a+b=n+1$ se puede poner en correspondencia con los pares de primos relativos $(a,n+1)$ y $(b,n+1)$. El valor total de los sumandos no varía ya que \[\frac{1}{a(n+1)}+\frac{1}{b(n+1)}=\frac{a+b}{ab(n+1)}=\frac{1}{ab},\] luego $S(n+1)=S(n)=\frac{1}{2}$ y el enunciado queda demostrado.

Solución. La figura (para $n=3$) tiene 18 aristas que se pueden agrupar en 6 triángulos equiláteros de lado 1 (con orientación $\triangle$) o bien, si previamente quitamos los lados del triángulo grande, quedan 9 aristas que se agrupan en tres triángulos (con orientación $\bigtriangledown$). Para el caso de $n$ general, tenemos $\frac{n(n+1)}{2}$ triángulos de tipo $\triangle$ y $\frac{n(n-1)}{2}$ triángulos de tipo $\bigtriangledown$ (tras eliminar los lados grandes). Vamos a distinguir dos casos:

• Si $n$ es de la forma $3k$ o $3k+2$, entonces el número de triángulos de tipo $\triangle$ es múltiplo de $3$. Los dividimos en tres subconjuntos que de forma que en cada subconjunto haya el mismo número $m$ de triángulos, estén conectados entre sí a través de vértices y en un subconjunto esté el vértice $A$, en otro el $B$ y en otro el $C$ (ver la nota). Las aristas de tales triángulos forman un grafo tal que en cada vértice hay un número par de aristas (cada triángulo aporta dos aristas en cada vértice). Por tanto, usando el teorema de Euler para grafos, partiendo de $A$ hay un camino de longitud $3m$ que empieza y acaba en $A$ y lo mismo con $B$ y $C$.
• Si $n$ es de la forma $3k+1$, hay una cantidad de triángulos $\bigtriangledown$ que es múltiplo de $3$, luego repartimos el segmento $AB$ para $A$, el segmento $BC$ para $B$ y el segmento $CA$ para $C$. Ahora los triángulos $\bigtriangledown$ los dividimos en tres subconjuntos al igual que en el caso anterior, pero en este caso conectados con los segmentos correspondientes a los jugadores. De esta manera, los lados de los $m$ triangulitos $\bigtriangledown$ asignados a cada jugador junto con el lado grande forman un grafo euleriano en el que todos los vértices tienen un número par de aristas menos los extremos del lado grande. Por tanto, existen caminos disjuntos de longitud $3m+n$ que van de $A$ a $B$, de $B$ a $C$ y de $C$ a $A$, respectivamente.

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).