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

Solución. El principio del palomar nos asegura que el número máximo de representantes es $n^2$ ya que, si hubiera más de $n^2$, entonces algún país tendría al menos $n+1$ representantes y al menos dos de ellos tendrían a su derecha a alguien del mismo país (hay sólo $n$ países). Veamos que esta cota superior es óptima mostrando que existe una forma de colocar a $n$ representantes de $n$ países de forma que dos del mismo país tengan a su derecha a alguien de distinto país, y lo vamos a mostrar por inducción sobre $n$.

En primer lugar, para $n=2$, está claro que se pueden sentar $n^2=4$ representantes de la siguiente manera: \[1\succ 2\succ 2\succ 1.\]

En este diagrama entendemos que un representante del país $1$ (el primer uno) tiene a su derecha a uno del país $2$ (el primer dos), quien tiene a su derecha a otro del país $2$ (el segundo dos), quien tiene a su derecha a uno del país $1$ (el último uno) y, cerrando el ciclo, éste tiene a su derecha a uno del país $1$ (otra vez el primer uno). Supongamos entonces que podemos sentar a $n^2$ representantes de $n$ países e intentemos hacerlo con $n+1$ países. En los $n^2$ representantes habrá dos del país $1$ consecutivos, luego su cadena podremos escribirla de la forma \[1\succ\ldots\succ1.\] Ahora añadimos los $(n+1)^2-n^2=2n+1$ representantes adicionales ($n+1$ del país $n+1$ y uno de cada uno de los $n$ países originales) de la siguiente manera: \[\overbrace{1\succ\ldots\succ 1}^{\text{cadena original}}\succ(n+1)\succ 2\succ(n+1)\succ 3\succ \ldots\succ (n+1)\succ n\succ (n+1)\succ(n+1)\succ 1.\] Está claro que los del país $n+1$ tienen a todos los países a su derecha y el resto tienen al país $n+1$. La hipótesis de inducción nos dice que en la cadena original estaban ya todas las posibles combinaciones entre los $n$ países originales, luego tenemos probado el resultado.

Solución. El primer jugador tiene la siguiente estrategia ganadora:

• en primer lugar, escribe $-1$ en el coeficiente de $x$;
• el segundo jugador escribe cualquier entero en uno de los huecos restantes (no podemos decir qué escribe ni en qué hueco porque es libre de elegir);
• finalmente, el primer jugador escribe el opuesto del número que escribió el segundo jugador en el hueco sobrante.

El polinomio resultante siempre es de la forma \[x^3+ax^2-x-a=(x-1)(x+1)(x+a),\] luego efectivamente el primer jugador se asegura la victoria.

Solución. Evidentemente no existe ninguna estrategia que permita salvar a todos los presos ya que el último de la fila no tiene información sobre su propio sombrero. No obstante, se pueden salvar los otros 2017, acordando previamente una forma de proceder que explicamos a continuación.

Al color negro le asignan el número 1 y al blanco el $-1$. El último de la fila multiplica todos los sombreros que ve por delante de él y dice el color correspondiente (puede acertar si tiene suerte pero no se garantiza que acierte). Sin embargo el que está delante de él puede dividir el número que ha dicho su predecesor entre el producto de los 2016 sombreros que puede ver, con lo que sabe el color de su sombrero. Análogamente, los siguientes presos dividen el primer número entre el producto de los sombreros que ven o que ya se han dicho, con lo que averiguan el suyo propio. De esta forma, se garantiza que todos se salvan salvan todos (salvo posiblemente el último de la fila).

Nota. El mismo razonamiento vale par una fila de $N$ presos y se garantiza que se salvan $N-1$.

Solución. Marcamos aquellas casillas cuyas dos coordenadas son pares. Por ejemplo, para un tablero $8\times 9$, las casillas marcadas seguirían el siguiente esquema:

	$\times$		$\times$		$\times$		$\times$
	$\times$		$\times$		$\times$		$\times$
	$\times$		$\times$		$\times$		$\times$
	$\times$		$\times$		$\times$		$\times$

Una ficha $2\times2$ siempre ocupa una casilla marcada, mientras que una $1\times 4$ ocupa dos o ninguna. Como la paridad es distinta, no puede recubrirse de nuevo el tablero al intercambiar una de un tipo por otra del otro tipo.

Solución. Probaremos por inducción que José tiene una estrategia tal que, para todo $n\geq 0$, la primera vez que hay $4n+2$ puntos utilizados, José ha sido el último en jugar. Como $98$ es de la forma $4n+2$, esto nos dice que José tiene una estrategia ganadora.

El caso base de inducción es $n=0$, que se cumple ya que, coloque donde coloque José, habrá $4\cdot 0+2=2$ puntos utilizados y él ha sido el último en jugar. Supongamos entonces que después de jugar José, hay $4n+2$ puntos utilizados y demostremos que, después de cierto número de jugadas de ambos jugadores, habrá $4n+6$ puntos utilizados y José habrá sido el último en jugar. La forma de proceder de José después de cada jugada de María es la siguiente:

• Si después de la jugada de María sigue habiendo $4n+2$ puntos utilizados (María ha unido dos que ya habían sido utilizados), entonces José une uno ya utilizado con otro no utilizado previamente y ahora hay $4n+3$ utilizados.
• Si después de la jugada de María hay $4n+3$ puntos utilizados, entonces José une dos que ya hayan sido utilizados previamente y siguen quedando $4n+3$ utilizados.
• Si después de la jugada de María hay $4n+4$ puntos utilizados, entonces José une dos que ya no hayan sido utilizados hasta el momento, quedando utilizados $4n+6$.
• Si después de la jugada de María hay $4n+5$ puntos utilizados, entonces José une uno que no haya sido utilizados con otro que sí y quedan utilizados $4n+6$.

Está claro que José puede hacer siempre utilizar puntos no utilizados, luego sólo habrá que justificar que si después de la jugada de María hay $4n+3$ puntos utilizados, entonces quedan dos de ellos que no han sido unidos y José puede unirlos. El número de uniones posibles entre $4n+3$ puntos está dado por $(4n+3)(2n+1)$, que es un número impar. Como José siempre juega en los turnos impares, no puede ser María la que complete todas las uniones posibles entre los $4n+3$ puntos.

Finalmente, observemos que María en su turno nunca se le presentan $4n+4$ ni $4n+5$ puntos utilizados, luego no puede ser la primera en utilizar los $4n+6$ puntos, lo que demuestra que esta es la estrategia ganadora para José.

Nota. Este es un problema que admite muchas discusiones de casos y aproximaciones ligeramente distintas. La solución arriba presentada tiene la ventaja de que se puede adaptar para cualquier número de la forma $4n+2$ en lugar de $98$.