Olimpiadas de Matemáticas
Página de preparación y problemas

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\leq x\leq 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\geq 2k$, entonces $B$ puede asegurarse la victoria.
2. Para todo $k$ suficientemente grande, existe un entero $n\geq 1.99^k$ tal que $B$ no puede asegurarse la victoria.