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 A y B. Las reglas del juego dependen de dos enteros positivos k y n conocidos por ambos jugadores.

Al principio del juego, el jugador A elige enteros x y N con 1 \le x \le N. El jugador A mantiene x en secreto, y le dice a B el verdadero valor de N. A continuación, el jugador B intenta obtener información acerca de x formulando preguntas a A de la siguiente manera: en cada pregunta, B especifica un conjunto arbitrario S de enteros positivos (que puede ser uno de los especificados en alguna pregunta anterior), y pregunta a A si x pertenece a S. El jugador B puede hacer tantas preguntas de ese tipo como desee. Después de cada pregunta, el jugador A debe responderla inmediatamente con sí o no, pero puede mentir tantas veces como quiera. La única restricción es que entre cualesquiera k+1 respuestas consecutivas, al menos una debe ser verdadera.

Cuando B haya formulado tantas preguntas como haya deseado, debe especificar un conjunto X de a lo más n enteros positivos. Si x pertenece a X entonces gana B; en caso contrario, pierde.

Demostrar que:

  1. Si n \ge 2^k, entonces B puede asegurarse la victoria.
  2. Para todo k suficientemente grande, existe un entero n \ge (1,99)^k tal que B no puede asegurarse la victoria.

Que se os dé bien.

Print Friendly, PDF & Email
0 0 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉