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.
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 »