Tercer problema de la IMO 2012, celebrada en Mar del Plata en julio de este año. Ahí va:
El juego de la adivinanza del mentiroso es un juego para dos jugadores
y
Las reglas del juego dependen de dos enteros positivos
y
conocidos por ambos jugadores.
Al principio del juego, el jugador
elige enteros
y
con
. El jugador
mantiene
en secreto, y le dice a
el verdadero valor de
. A continuación, el jugador
intenta obtener información acerca de
formulando preguntas a
de la siguiente manera: en cada pregunta,
especifica un conjunto arbitrario
de enteros positivos (que puede ser uno de los especificados en alguna pregunta anterior), y pregunta a
si
pertenece a
. El jugador
puede hacer tantas preguntas de ese tipo como desee. Después de cada pregunta, el jugador
debe responderla inmediatamente con sí o no, pero puede mentir tantas veces como quiera. La única restricción es que entre cualesquiera
respuestas consecutivas, al menos una debe ser verdadera.
Cuando
haya formulado tantas preguntas como haya deseado, debe especificar un conjunto
de a lo más
enteros positivos. Si
pertenece a
entonces gana
; en caso contrario, pierde.
Demostrar que:
- Si
, entonces
puede asegurarse la victoria.
- Para todo
suficientemente grande, existe un entero
tal que
no puede asegurarse la victoria.
Que se os dé bien.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: Tercer problema de la IMO 2012, celebrada en Mar del Plata en julio de este año. Ahí va: El juego de la adivinanza del mentiroso es un juego para dos jugadores y Las reglas del juego dependen de dos enteros positivos y cono……
Según está planteado el problema, B nunca podrá asegurarse la respuesta correcta salvo que n=N. Para ello, la estrategia que seguirá A será responder sí-no-sí-no-… a las preguntas de B. Esta secuencia cumple la condición impuesta de que haya al menos una respuesta verdadera en cualquier secuencia de k+1 respuestas consecutivas, y no da ninguna información a B.
El objetivo del juego es obtener información; puesto que la opción inicial es que al menos una cualquiera de las k+1 respuestas debe ser verdadera, se puede considerar como k+1 opciones lógicas unidas con una «o» Sería imposible verificar cuál de todas es verdadera, así que enfrentemos el reto por la negación de estas «o» es decir que evaluemos si para algún conjunto de números se puede obtener algún número que no esté en de los k+1 subconjuntos. Para hacer esto, empecemos dividiendo el conjunto original en la mitad y preguntando si x pertenece a este subconjunto; de la mitad… Lee más »