3 El juego de adivinanzas del mentiroso es un juego entre dos jugadores $A$ y $B$. Las reglas del juego dependen de dos enteros positivos $k$ y $n$ que ambos jugadores conocen. Al inicio del juego, $A$ elige enteros $x$ y $N$ con $1 \le x \le N$. El jugador $A$ mantiene $x$ en secreto y le dice la verdad a $B$ sobre $N$. El jugador $B$ ahora intenta obtener información sobre $x$ haciendo preguntas a $A$ de la siguiente manera: cada pregunta consiste en que $B$ especifica un conjunto arbitrario $S$ de enteros positivos (posiblemente uno ya especificado en una pregunta anterior) y le pregunta a $A$ si $x$ pertenece a $S$. $B$ puede hacer tantas preguntas como quiera. Después de cada pregunta, $A$ debe responder inmediatamente 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. Después de que $B$ haya hecho tantas preguntas como quiera, debe especificar un conjunto $X$ de a lo más $n$ enteros positivos. Si $x$ pertenece a $X$, entonces $B$ gana; de lo contrario, pierde. Demuestra 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. Propuesto por David Arthur, Canadá