El juego de adivinanzas del mentiroso es un juego jugado entre dos jugadores $A$ y $B$. Las reglas del juego dependen de dos enteros positivos $k$ y $n$ los cuales son conocidos por ambos jugadores. Al inicio del juego $A$ escoge enteros $x$ y $N$ con $1 \le x \le N.$ El jugador $A$ mantiene $x$ secreto, y le dice honestamente $N$ al jugador $B$. El jugador $B$ ahora intenta obtener información sobre $x$ preguntándole al jugador $A$ preguntas de la siguiente manera: cada pregunta consiste en que $B$ especifica un conjunto arbitrario $S$ de enteros positivos (posiblemente uno especificado en alguna pregunta anterior), y preguntándole a $A$ si $x$ pertenece a $S$. El jugador $B$ puede hacer tantas preguntas como desee. Después de cada pregunta, el jugador $A$ debe responderla inmediatamente con sí o no, pero se le permite mentir tantas veces como quiera; la única restricción es que, entre cada $k+1$ respuestas consecutivas, al menos una respuesta debe ser veraz. Después de que $B$ ha hecho tantas preguntas como quiere, debe especificar un conjunto $X$ de a lo sumo $n$ enteros positivos. Si $x$ pertenece a $X$, entonces $B$ gana; de lo contrario, pierde. Demuestre que: 1. Si $n \ge 2^k,$ entonces $B$ puede garantizar una victoria. 2. Para todo $k$ suficientemente grande, existe un entero $n \ge (1.99)^k$ tal que $B$ no puede garantizar una victoria.