En una cárcel, $2019$ prisioneros se juegan la libertad a partir del siguiente problema: un ogro no muy selectivo los ubica en ronda y les coloca arbitrariamente un sombrero de uno de $2019$ colores disponibles (los prisioneros saben de antemano cuales son los $2019$ colores posibles) de modo que cada uno sólo pueda ver los colores de los demás $2018$ prisioneros. Luego, les pide que escriban el color de sombrero que creen tener. Ninguno puede hablar en voz alta, y para liberarse al menos uno tiene que decir correctamente el color de su sombrero. Determinar si existe alguna estrategia que les permita obtener la libertad.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Podemos ordenar a los prisioneros en algún orden (digamos, altura) y enumerarlos desde el $0$ hasta el $2018$, de modo que $p_i$ sea el prisionero con el número $i$.
Del mismo modo, podemos ordenar los colores de los sombreros en algún orden (digamos, alfabético) y enumerarlos desde el $0$ hasta el $2018.$
Sea también $S$ el resto de la suma de los $a_i$ en la división por $2019$, esto es, $$S \equiv a_0+a_1+ \ldots + a_{2018} \pmod{2019}. $$
Supongamos que el prisionero $p_i$ tiene entonces asignado un sombrero de color $a_i$. Como $p_i$ sabe el valor de $a_j$ para todo $ j \neq i$, entonces sabe el valor de $S-a_i$, que es la suma de los valores de los $2018$ colores de sombrero que ve en los restantes prisioneros.
Observemos entonces que, para cada $p_i$, conocer el valor de $a_i$ es equivalente a conocer el valor de $S$, puesto que $S = (S-a_i)+a_i$, donde el primer sumando del lado derecho es conocido para cada uno de ellos.
Observemos aquí que el número $S$ es uno y sólo uno de los posibles restos de la suma $a_0+\ldots + a_{2018}$ módulo $2019$, lo cual nos permitirá elaborar la estrategia
La estrategia entonces es la siguiente. Cada prisionero $p_i$ supondrá que $S \equiv i \pmod{2019}$. De este modo $p_i$ supondrá que el color de su sombrero es $$a_i \equiv S-(S-a_i) \equiv i - (a_0+ \ldots +a_{i-1}+a_{i+1} + \ldots a_{2018} )\pmod{2019}.$$
En virtud de la primer observación cada prisionero puede suponer perfectamente cual podría ser el color de su sombrero.
Finalmente, en virtud de la segunda observación, uno y sólo uno de los prisioneros (digamos, $p_r$, donde $S\equiv r \pmod{2019}$) acertará el valor $a_r$ de su sombrero.
De este modo, todos los prisioneros se pueden asegurar la libertad sin importar cómo distribuya el otro los sombreros
Tal y como se aclaró luego el enunciado, los presos saben qué colores hay pero no la cantidad. Además, ellos pueden armar una estrategia antes y saber todos cuál es. Por esta razón, cuando se enteren cuáles son los posibles colores de los sombreros, toman el primero en órden alfabético y lo escriben todos (no pueden decir nada en voz alta, claro). Por esto, sí o sí alguno va a decir el color de su sombrero. Cumple todas las condiciones del problema
Tal y como se aclaró luego el enunciado, los presos saben qué colores hay pero no la cantidad. Además, ellos pueden armar una estrategia antes y saber todos cuál es. Por esta razón, cuando se enteren cuáles son los posibles colores de los sombreros, toman el primero en órden alfabético y lo escriben todos (no pueden decir nada en voz alta, claro). Por esto, sí o sí alguno va a decir el color de su sombrero. Cumple todas las condiciones del problema
Por lo que entiendo, el ogro no necesariamente usa todos los colores. Esto es, puede usar dos sombreros de color rojo y ninguno blanco (aún si está entre los $2019$ colores), por lo que esto no siempre funciona, ponele: Si todos escriben el color "amarillo" pero todos tienen sombrero rojo, perdieron todos.
