FOFO 9 años Problema 4

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 885
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

FOFO 9 años Problema 4

Mensaje sin leer por Fran5 » Jue 10 Oct, 2019 11:29 pm

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 // Costa Rica te entro"

Avatar de Usuario
Fran5

OFO - Medalla de Oro OFO - Jurado FOFO Pascua 2019 - Jurado FOFO 7 años - Jurado FOFO 8 años - Jurado
Mensajes: 885
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 9
Nivel: Exolímpico
Ubicación: Santa Fe

Re: FOFO 9 años Problema 4

Mensaje sin leer por Fran5 » Dom 13 Oct, 2019 8:36 pm

Solución oficial
Spoiler: mostrar
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
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro // Costa Rica te entro"

HelcsnewsXD

FOFO 9 años - Mención Especial
Mensajes: 23
Registrado: Jue 13 Sep, 2018 8:59 am
Medallas: 1
Nivel: 2

Re: FOFO 9 años Problema 4

Mensaje sin leer por HelcsnewsXD » Mar 15 Oct, 2019 10:21 am

Spoiler: mostrar
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

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla FOFO 9 años - Medalla Especial
Mensajes: 184
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 5
Nivel: 1

Re: FOFO 9 años Problema 4

Mensaje sin leer por BrunZo » Mar 15 Oct, 2019 11:43 am

HelcsnewsXD escribió:
Mar 15 Oct, 2019 10:21 am
Spoiler: mostrar
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
Spoiler: mostrar
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.
1  

Responder