IMO

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 2^k$, 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.