Selectivo IMO 2016 P6

Problemas que aparecen en el Archivo de Enunciados.
jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
FOFO 9 años - Jurado-FOFO 9 años OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 402
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 13
Nivel: Exolímpico

Re: Selectivo IMO 2016 P6

Mensaje sin leer por jujumas »

Emerson Soriano escribió:El problema es muy bueno, pero yo creo eso de probar la maximilidad de sobrevivientes no me cuadra. Si bien es cierto, el máximo es [math], pero para esa estrategia, ¿cómo podemos garantizar que no hay otra estrategia que nos garantice un sobreviviente más? El enunciado del problema es bastante subjetivo, pues podemos maximizar números, pero no estrategias.
Spoiler: mostrar
Porque al haber [math] colores, para que todos los posibles casos de elección de colores para el prisionero [math] resulte con el sabiendo el color que tiene es necesario que el prisionero [math] y el prisionero [math] entre sus respuestas de "si" o "no" puedan hacer que haya una única combinación de respuestas para cada color, y como hay [math] combinaciones de estas respuestas, necesariamente habrá dos combinaciones de respuestas asignada al mismo color, por lo que el prisionero [math] en el caso hipotético de que reciba alguno de estos dos colores, no se aseguraría que color recibe.
Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
OFO - Medalla de Plata-OFO 2022
Mensajes: 826
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 6

Re: Selectivo IMO 2016 P6

Mensaje sin leer por Emerson Soriano »

Claro, pero eso es para esa estrategia. No para todas! Lo que estás analizando sólo es para cuando ellos se ponen de acuerdo en una determinada estrategia (en este caso tuya). ¿Cómo podrías probar que NO hay otra estrategia que te garantice al menos [math] sobrevivientes?
ltaravilse
Mensajes: 3
Registrado: Sab 09 Abr, 2011 4:54 pm

Re: Selectivo IMO 2016 P6

Mensaje sin leer por ltaravilse »

Hola, vengo a iluminarlos y a no tirar fruta, algo raro en mí.

Mi solución es la que explicaré a continuación y les pido por favor a los que me conocen que si realmente piensan que voy a mandar fruta posteen antes de leer "Noooo seguro que lo que dice Leo es re fruta" y después si ven que no es fruta admitan que me viven tratando de frutero :P jajaja
Spoiler: mostrar
Observación 1: Si no se puede salvar a 3 personas para n = 3 tampoco se puede para n = 2016, porque supongamos que se pueda para n = 2016, entonces nos inventamos 2013 prisioneros con color de sombrero 0, usamos la misma estrategia y cuando llegamos al 4to prisionero el ogro dice "Uhh no hay más prisioneros, me cagaron, pero sobrevivió al menos uno" entonces usamos esa estrategia para 3, entonces ahora reduje el problema a demostrar que si son 3 prisioneros pueden morir todos si tienen mala suerte.

Observación 2: Si fijamos el color del prisionero 3 (indices desde 1) en 0 (indices desde 0) y podemos asegurarnos de que hay 6 configuraciones de sombreros del 1 y del 2 que hagan que el 1 y el 2 se mueran y el 3 sepa que es color 0, ya se mueren todos por palomar, porque para los 5 colores del 3 pasa lo mismo, entonces tenemos 30 configuraciones tales que las dividimos en 5 grupos de 6, cada grupo es "Si el 1 y el 2 tienen estos colores entonces el 3 tiene color X" una para cada X, pero por palomar 30 > 25 entonces hay dos configuraciones que son iguales en los primeros dos prisioneros, que los hacen morirse, y que derivan en distinto color del prisionero 3. Si no se entendió no importa, más adelante se va a entender mejor y sino alguien que lo entendió explique lo que quise decir con mejores palabras.

Ahora sólo nos falta ver que si fijamos el color del prisionero 3 en 0 hay 6 configuraciones del 1 y del 2 que hacen que ambos se mueran:

El 1 va a basar su estrategia en lo que vea del 2 y del 3, como el 3 es fijo (cero) entonces la basa en lo que vea del 2. Si ante 3 posibles colores del 2 dice "Uhh no se que onda mi sombrero" el ogro lo mata y entonces hay 5 casos (5 colores posibles del sombrero 1) ante los que el 1 muere. Pero el 2 como sólo tiene información de que tiene uno de esos 3 colores, va a elegir uno de esos 3 en el mejor de los casos y los otros dos colores lo van a matar, habiendo en total 10 combinaciones de colores que matan al 1 y al 2, entonces en este caso ya ganó el ogro. Entonces el 1 tiene que "suicidarse" (es decir, decir que no sabe su color) ante máximo 2 colores posibles del 2, o sea que arriesga un color ante 3 o más colores del 2.

Caso 1: El prisionero 1 arriesga un color ante 3 posibles colores del prisionero 2, sean estos 0, 1 y 2 y sean A, B y C respectivamente los colores que dice el 1 que tiene (si el 2 tiene 0 el 1 dice que tiene A, si el 2 tiene 1 el 1 dice que tiene B y si el 2 tiene 3 el 1 dice que tiene C). Notemos que no necesariamente A, B y C son distintos, pero existen al menos 2 colores (D y E) que son distintos de A, B y C. Entonces si el 1 tiene color D o E muere y el 2 tiene que elegir un color, que va a ser 0, 1 o 2, supongamos que elije 0, entonces si tiene sombreros 1 o 2 muere, entonces tenemos 2 * 2 (D y E por 1 y 2 producto cartesiano) combinaciones ante las cuales mueren el 1 y el 2. Nos faltan 2 para llegar a nuestro argumento, ahora supongamos que A, B, C son distintos, entonces ante las combinaciones (0,B) y (0,C) el 1 muere, y el 2 sabe que tiene 0 o 2 (en el caso B) y 0 o 1 (en el caso C), de cualquiera de las dos formas, va a elegir uno de los dos y con el otro muere, ahí ya tenemos los 6 casitos, el tema es si por ejemplo A = B, A = C o B = C. Supongamos sin pérdida de generalidad A = B (no importa si A = C), entonces existe un color más (llamémosle F) que cumple con las propiedades de D y E, entonces ahí hay dos casos más en los que muere el primero y el segundo sigue entre 3 opciones y hay 2 que lo hacen morir, entonce si el primero arriesga un color ante 3 posibles colores del segundo ya hay 6 o más casos en el que los dos mueren.

Caso 2: El prisionero 1 arriesga un color ante 4 posibles colores del prisionero 2, sean estos 0, 1, 2 y 3, y sean A, B, C y D los respectivos colores que arriesga el 1 para si mismo según el color del 2. Si hay entre A, B, C y D a lo sumo 3 colores, entonces hay 2 colores del 1 que no le dicen nada al 2, y el 1 arriesga un color para cada uno, entonces con los otros tres muere, entonces ya tenemos 6 combinaciones que los matan a ambos, entonces A, B, C y D son todos distintos, y ahora si el 1 ve 0 elige A, entonces si tiene B, C o D son 3 casos en los que quedan 3 posibles colores para el 2, el cual elige uno y los otros dos lo matan, nuevamente tenemos 6 combinaciones que matan al 1 y al 2.

Caso 3: El prisionero 1 arriesga siempre un color. Entonces para cada color del 2 hay 4 colores que hacen que el 1 se muera, y va a haber al menos 4 colores del 1 que los elija con a lo sumo 2 colores del 2 cada uno (porque sino hay sólo 3 o menos con esa propiedad, entonces hay 2 o más, sean A y B, que los elige en 3 oportunidades cada uno quiere decir que el 2 tenía al menos 6 colores posibles, lo que es mentira), entonces para esos 4 colores si tiene el sombrero de ese color y el 2 tiene de alguno de los otros 3 colores que no le hacen elegir ese color, entonces se muere, ahora de las 3 (o más) opciones que sabe el 2 que puede tener, tiene que elegir 1, pero si elige una sóla entonces 2 lo matan, y 2*4 = 8 > 6.

Luego queda demostrado que pase lo que pase si jugamos los 125 juegos posibles hay juegos que hacen que los 3 se mueran, luego no tiene sentido seguir jugando con los demás 2013 porque la estrategia para que mueran sólo 3 era trivial, y por lo tanto la respuesta es 2013.
xyz

OFO - Medalla de Bronce-OFO 2016 FOFO 6 años - Mención Especial-FOFO 6 años FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Mención-OFO 2018
Mensajes: 30
Registrado: Jue 11 Jun, 2015 8:30 pm
Medallas: 4
Nivel: 2

Re: Selectivo IMO 2016 P6

Mensaje sin leer por xyz »

Voy a plantear una forma de que el tercer prisionero sobreviva (no digo que se pueda con 2014, pero solo para ver que hay otra idea que se puede usar):
El prisionero 1 responderá "si" en caso de que el color de 3 sea [math], [math] o [math], y "no" en caso contrario.
En el peor de los casos, el prisionero 3 esta entre tres colores. En ese caso, el prisionero 1 puede, al responderle al ogro, decir el color del prisionero 3 (claramente los prisioneros ya establecieron esto antes de comenzar el juego). Como 3 ya sabe el color de 1, o bien sabe que su color es el de 1(en caso de que no sea petrificado), o bien que no es el de 1(en caso de que sea petrificado).
Asi, podemos conseguir que 3 este como mucho entre 2 colores. El prisionero 2, que pudo como 3 deducir los dos colores, puede decir "si" en caso de que sea el primero(en este caso, el primero sería [math] y no [math] si [math]) y "no" en caso contrario, y asi 3 tiene asegurada su supervivencia.
Última edición por xyz el Mar 24 May, 2016 6:49 pm, editado 1 vez en total.
Avatar de Usuario
Emerson Soriano

OFO - Mención-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Bronce-OFO 2018 OFO - Mención-OFO 2020
OFO - Medalla de Plata-OFO 2022
Mensajes: 826
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 6

Re: Selectivo IMO 2016 P6

Mensaje sin leer por Emerson Soriano »

xyz escribió:Voy a plantear una forma de que el tercer prisionero sobreviva (no digo que se pueda con 2014, pero solo para ver que hay otra idea que se puede usar):
El prisionero 1 responderá "si" en caso de que el color de 3 sea [math], [math] o [math], y "no" en caso contrario.
En el peor de los casos, el prisionero 3 esta entre tres colores. En ese caso, el prisionero 1 puede, al responderle al ogro, decir el color del prisionero 3 (claramente los prisioneros ya establecieron esto antes de comenzar el juego). Como 3 ya sabe el color de 1, o bien sabe que su color es el de 1(en caso de que no sea petrificado), o bien que no es el de 1(en caso de que sea petrificado).
Asi, podemos conseguir que 3 este como mucho entre 2 colores. El prisionero 2, que pudo como 3 deducir los dos colores, puede decir "si" en caso de que sea el primero(en este caso, el primero sería [math] y no [math] si [math]) si y "no en caso contrario, y asi 3 tiene asegurada su supervivencia.
Spoiler: mostrar
El asunto es que si el prisionero [math] se salva, entonces es muy probable que ejecuten a más prisioneros.
xyz

OFO - Medalla de Bronce-OFO 2016 FOFO 6 años - Mención Especial-FOFO 6 años FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Mención-OFO 2018
Mensajes: 30
Registrado: Jue 11 Jun, 2015 8:30 pm
Medallas: 4
Nivel: 2

Re: Selectivo IMO 2016 P6

Mensaje sin leer por xyz »

Si, pero no se como demostrarlo... era solo para mostrar que no es cierto que los primeros 3 van a morir si o si
ltaravilse
Mensajes: 3
Registrado: Sab 09 Abr, 2011 4:54 pm

Re: Selectivo IMO 2016 P6

Mensaje sin leer por ltaravilse »

Perdón pero eso falla

Si 1 tiene un color que es de los 2 que si lo tiene 3 se suicida ta 3 sigue con 3 opciones, y 2 solo se lo puede reducir a 2 opciones.
xyz escribió:Voy a plantear una forma de que el tercer prisionero sobreviva (no digo que se pueda con 2014, pero solo para ver que hay otra idea que se puede usar):
El prisionero 1 responderá "si" en caso de que el color de 3 sea [math], [math] o [math], y "no" en caso contrario.
En el peor de los casos, el prisionero 3 esta entre tres colores. En ese caso, el prisionero 1 puede, al responderle al ogro, decir el color del prisionero 3 (claramente los prisioneros ya establecieron esto antes de comenzar el juego). Como 3 ya sabe el color de 1, o bien sabe que su color es el de 1(en caso de que no sea petrificado), o bien que no es el de 1(en caso de que sea petrificado).
Asi, podemos conseguir que 3 este como mucho entre 2 colores. El prisionero 2, que pudo como 3 deducir los dos colores, puede decir "si" en caso de que sea el primero(en este caso, el primero sería [math] y no [math] si [math]) y "no" en caso contrario, y asi 3 tiene asegurada su supervivencia.
xyz

OFO - Medalla de Bronce-OFO 2016 FOFO 6 años - Mención Especial-FOFO 6 años FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 OFO - Mención-OFO 2018
Mensajes: 30
Registrado: Jue 11 Jun, 2015 8:30 pm
Medallas: 4
Nivel: 2

Re: Selectivo IMO 2016 P6

Mensaje sin leer por xyz »

ltaravilse escribió:Perdón pero eso falla

Si 1 tiene un color que es de los 2 que si lo tiene 3 se suicida ta 3 sigue con 3 opciones, y 2 solo se lo puede reducir a 2 opciones.
xyz escribió:Voy a plantear una forma de que el tercer prisionero sobreviva (no digo que se pueda con 2014, pero solo para ver que hay otra idea que se puede usar):
El prisionero 1 responderá "si" en caso de que el color de 3 sea [math], [math] o [math], y "no" en caso contrario.
En el peor de los casos, el prisionero 3 esta entre tres colores. En ese caso, el prisionero 1 puede, al responderle al ogro, decir el color del prisionero 3 (claramente los prisioneros ya establecieron esto antes de comenzar el juego). Como 3 ya sabe el color de 1, o bien sabe que su color es el de 1(en caso de que no sea petrificado), o bien que no es el de 1(en caso de que sea petrificado).
Asi, podemos conseguir que 3 este como mucho entre 2 colores. El prisionero 2, que pudo como 3 deducir los dos colores, puede decir "si" en caso de que sea el primero(en este caso, el primero sería [math] y no [math] si [math]) y "no" en caso contrario, y asi 3 tiene asegurada su supervivencia.
Fijate que si 1 dice si, 3 queda entre tres colores. En ese caso, 1 le responde al ogro el color de 3(3 ya sabe que va a hacer esto). Entoncés hay dos casos:
1)que 1 se salve. Como dijo el color de 3, si se salva significa que 1 y 3 tienen el mismo color, y como 3 ya sabe el color de 1, sabe tambien su color.
2)Que 1 sea petrificado. En tal caso, 3 sabe que su color es el de 1, y luego 2 puede indicarle cual es su color a 3.
Avatar de Usuario
MateoCV

OFO - Medalla de Bronce-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 FOFO 7 años - Medalla Especial-FOFO 7 años
OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021
Mensajes: 255
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 14
Nivel: Exolímpico
Ubicación: Córdoba

Re: Selectivo IMO 2016 P6

Mensaje sin leer por MateoCV »

Igual la respuesta es
Spoiler: mostrar
se salvan 2014
$2^{82589933}-1$ es primo
Avatar de Usuario
MateoCV

OFO - Medalla de Bronce-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 FOFO 7 años - Medalla Especial-FOFO 7 años
OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años
OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021
Mensajes: 255
Registrado: Vie 18 Dic, 2015 12:35 am
Medallas: 14
Nivel: Exolímpico
Ubicación: Córdoba

Re: Selectivo IMO 2016 P6

Mensaje sin leer por MateoCV »

Publico la solución oficial:
Spoiler: mostrar
Screenshot_2017-06-27-19-57-16.png
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
6  
$2^{82589933}-1$ es primo
Responder