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.
Share
Autor: ^DiAmOnD^ | Publicado el 6 de agosto de 2012
Categorías: Juegos | 
Imprime este post
Trackback | 6 ago, 2012
Bitacoras.com
sqrmatrix | 15 de agosto de 2012 | 03:47
Vótalo
0
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.
Omar | 20 de agosto de 2012 | 23:13
Vótalo
0
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 donde supuestamente no está x -llamémoslo
- preguntamos si x está en esta mitad, la mitad en que la respuesta no está x, llamémoslo 
, procedemos a hacer lo mismo. Es decir se divide el conjunto de N números en k+1 subconjuntos donde el último está compuesto por 
elementos. puesto que en este último subconjunto no están ciertos números y por la forma como fueron construidos no están en ningún otros subconjunto, se puede afirmar que en éstos no está x.
Hasta ahora no hemos detallado el número N, si es par o impar , etc. Veamos como influye esto en el procedimiento:
En este caso, siempre se puede eliminar al menos un número, puesto que el último subconjunto tendrá al menos un elemento.
En este caso cambiamos el procedimiento: Siguiendo los mismos pasos, cuando se llegue a la última pregunta habrá un número del cual no podrá obtenerse información, pero igual se pregunta si este número ![{y} \](http://s.wordpress.com/latex.php?latex=%20%7By%7D%20%5C%20&bg=ffffff&fg=000000&s=0 "{y} \")
es igual a x. Si se dice que no, este número puede descartarse, si se responde que sí, se parte de ésta para reiniciar el procedimiento, pero esta vez teniendo 
respuestas, de donde se podrá descartar algún numero.
no se podrá obtener más información, así que si 
se tendría con certeza que x pertenece al subconjunto de 
sin contar el último número encontrado y el valor mínimo elementos de este subconjunto es 
1.
2.
3. Finalmente, cuando
De esta manera se demuestra que por este procedimiento se obtiene una respuesta.
Para la segunda parte, de acuerdo a los preceptos tenidos en cuenta y ya que N es grande, se tendría
y por lo tanto, no podría asegurarse la victoria.
De esta manera se tendría la respuesta al problema, pero tengo dos observaciones:
1. Que este procedimiento sea óptimo, porque de lo contrario no podría responder la parte b del problema ya que podría existir otro procedimiento aún mejor y que pueda encontrar una solución con menos valores.
2. He pensado en este problema varias horas y creo haber encontrado una solución, sin embrago, estos niños en hora y media deben haber encontrado la respuesta, NOTABLE!!