Torneo de las Ciudades Marzo 2015 P6 Nivel Mayor

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

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Torneo de las Ciudades Marzo 2015 P6 Nivel Mayor

Mensaje sin leer por Joacoini »

Un emperador invitó a $2015$ magos a un festival. Cada mago sabe cuáles de los magos son buenos y cuales son malos, pero el emperador no lo sabe. Si un mago es bueno siempre dice la verdad y si es malo a veces dice la verdad y a veces miente. El emperador le pregunta a cada mago (en un orden que él elige) una sola pregunta, aunque puede hacer preguntas distintas a magos distintos, y escucha las respuestas, que solo pueden ser “sí” o “no”. Habiendo escuchado todas las respuestas, el emperador expulsa a uno solo de los magos por una puerta mágica que le muestra si ese mago es bueno o malo. A continuación el emperador repite el proceso con los restantes magos, y así siguiendo. El emperador puede detenerse después de cualquier respuesta y a continuación el emperador puede expulsar o no a algún mago. Demostrar que el emperador puede expulsar a todos los magos malos habiendo expulsado, además, a lo sumo un solo mago bueno. ($10$ Puntos)
NO HAY ANÁLISIS.
Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 68
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario

Re: Torneo de las Ciudades Marzo 2015 P6 Nivel Mayor

Mensaje sin leer por Fran2001 »

Spoiler: mostrar
Decimos que "preguntamos $(a, b)$" cuando le preguntamos al mago $a$ "¿El mago $b$ es bueno?".

Sea $n$ la cantidad de magos. Vamos por inducción en $n$.
Para el caso base $n=1$ simplemente echamos a $a_1$.

Ahora el paso inductivo:
Sean $a_1, a_2, \dots, a_n$ los magos.
Para $i = 2, 3, \dots, n$ vamos a preguntar $(a_i, a_1)$.
Si para algún $i$ obtenemos un "sí" entonces echamos a $a_i$:
Spoiler: mostrar
Si era malo, no pasa nada, y volvemos a comenzar con $n$ habiendo decrementado una unidad.
Si era bueno, entonces sabemos que $a_1$ es bueno:
Spoiler: mostrar
(*)Numeramos de vuelta de $1$ a $n-1$ (porque ya echamos a un mago), manteniendo fijo $a_1$, que sabemos que es bueno. Ahora podemos preguntar $(a_i, a_{i+1})$ para $i = 1, 2, \dots, n-2$. Si obtenemos todos "sí" entonces sabemos que todos los magos son buenos, y terminamos.
Si en algún $i$ obtuvimos un "no", entonces sabemos que $a_{i+1}$ es malo. Lo echamos y volvemos a (*).
Si en ningún momento obtuvimos un "sí", entonces echamos a $a_1$. Si este era bueno, sabemos que todos los demás son malos, y podemos echarlos.
Si era malo, no pasa nada, y volvemos a comenzar con $n$ habiendo decrementado una unidad.
1  
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4
Responder