Adivina el número a pesar de la respuesta falsa

Question

¡Este es el juego de Adivina el Número con un giro!

Variante 1

Tome cualquier número entero positivo $n$ .

El director del juego elige un $n$ -bit entero $x$ .

El jugador realiza consultas una a una, cada una de ellas de la forma "¿Es $x$ (estrictamente) menos de $k$ ?".

El maestro de ceremonias responde inmediatamente a cada pregunta, siempre con la verdad, excepto como máximo una vez.

Al final el jugador debe adivinar $x$ correctamente para ganar.

¿Cuál es la mejor estrategia para que el jugador minimice el número de consultas utilizadas en el peor de los casos? Ten en cuenta que el jugador puede elegir cada consulta en función de todas las respuestas a las consultas anteriores. Tengo un algoritmo que toma $n + O(\sqrt{n})$ consultas, pero no sé si esto es óptimo. Obsérvese que podemos suponer que el director del juego no tiene que elegir $x$ al principio, pero sólo tiene que mantener sus respuestas coherentes con al menos una posible $x$ .

Variante 2

Además, ¿cuál es la mejor estrategia si el director del juego puede responder falsamente a una fracción $r$ de las consultas (lo que significa que después de la primera $k$ consultas que el game-master ha respondido como máximo $rk$ de ellos falsamente). Es evidente que si $r \ge \frac12$ entonces el jugador no tiene una estrategia ganadora definida si $n>2$ porque el director del juego puede simplemente responder a la primera pregunta con la verdad eligiendo $x$ para estar en la mitad mayor, y entonces cualquier estrategia de este tipo debe funcionar incluso si el game-master ahora le dice al jugador dos valores que él garantiza $x$ está entre, en cuyo caso sólo hay una pregunta útil y el game-master simplemente responde a esas preguntas "sí" y "no" alternativamente (y responde a todas las demás preguntas con la verdad), y el jugador no puede saber nunca cuál de las dos $x$ es. ¿Y si $r < \frac12$ ?

[Editar: No veo por qué esto debe ser downvoted, porque he proporcionado mi propio algoritmo en una respuesta a continuación, a pesar de que no sé su optimalidad. Si alguien puede demostrar su optimidad o puede proporcionar un algoritmo mejor, por favor, publique una respuesta].

Answer 1

Aquí hay un análisis para números m=3 - así que en lugar de números de n bits donde $m$ tiene que ser una potencia de dos. Voy a minimizar el número medio de preguntas.
A elige el número, y responde a las preguntas, para maximizar el número medio de preguntas.
B elige las preguntas para minimizar el número medio de preguntas.
A debe elegir el número 1,2 o 3 al azar. Sean las probabilidades $p,q,r$ respectivamente, por lo que $p+q+r=1$ .
Los conocimientos de B pueden resumirse en un vector $(a,b,c)$ . Esto es
"O el número es 1, y hay $a$ queda, O el número es 2, y hay $b$ queda, O el número es 3, y hay $c$ se encuentra a la izquierda". Cada pregunta cambiará este vector.
Al principio, los conocimientos de B son $(1,1,1)$ . Utilizaré $a=-1$ para significar que el número 1 ha sido descartado. $B$ necesita llegar a $(a,-1,-1)$ o $(-1,b,-1)$ ou $(-1,-1,c)$ .
Dejemos que $F(a,b,c)$ será el número de preguntas necesarias; será una función de $p,q,r$ .

• $F(a,b)$ : Si sólo quedan dos números, $B$ debe agotar todas las mentiras antes de obtener una respuesta fiable. Utiliza una mentira por pregunta. Esto le llevará $a+b+1$ preguntas en total.

• $F(0,0,0)$ : $B$ puede preguntar "es menos de 3". Si $A$ responde "sí", $B$ va al estado $(0,0,-1)$ y gana en una pregunta más. Si $A$ responde "no", $B$ va al estado $(-1,-1,0)$ y gana inmediatamente. Así que el número esperado de preguntas es $1r+2(p+q)=2-r$ . Por otro lado, $B$ puede preguntar "es menos de 2", y el número medio de preguntas es $2-p$ . $B$ La estrategia de la empresa debe tomar $\min(2-p,2-r)$ preguntas.

• $F(1,0,0)$ : Si $B$ pregunta "es menos de 2", entonces $A$ debería decir "no". Esto tomará $1+F(0,0,0)=\min(3-p,3-r)$ preguntas. Si $B$ pregunta "es menos de 3", terminamos en el estado (0,-1,0), con 1 pregunta más; o en el estado (1,0,-1), con dos preguntas más. $A$ debe decir "sí" si el número es 1 o 2; y debe decir "no" si el número es 3. El número de preguntas es 3(p+q)+2r=3-r. Así que $B$ debe preguntar "es menos de 2" para $\min(3-p,3-r)$ preguntas.

• $F(0,1,0)$ : El número de preguntas es $3-r$ ou $3-p$ , en función de $B$ de la primera pregunta. Así que de nuevo, termina como $\min(3-p,3-q)$ preguntas.

• $F(0,0,1)$ : El número de preguntas es el mismo que $F(1,0,0)$ .

• $F(1,1,0)$ : Si $B$ pregunta "es menos de 3", $A$ debe decir "sí" si es posible, dando $4p+4q+\min(4-p,4-r)r$ preguntas. Si $B$ pregunta "es menos de 2", $A$ La respuesta del Sr. G. de la Cruz lleva a $\max(3,1+F(0,1,0))=\min(4-p,4-r)$ preguntas.

• $F(0,1,1)$ también conduce a $\min(4-p,4-r)$ preguntas.

• $F(1,1,1)$ : $A$ debe responder para que el estado se mueva a $(1,1,0)$ ou $(0,1,1)$ por lo que el número total de preguntas es $\min(5-p,5-q)$ .
  $A$ puede hacer que el número medio de preguntas sea lo más parecido a $5$ como ella quiere al elegir $2$ casi todo el tiempo.

Answer 2

¡Qué pregunta más bonita! Me concentraré en la Variante 1.

De hecho, estás tratando de adivinar dos números. En el transcurso de $Q$ preguntas (que numeraré del 1 al $Q$ ), está tratando de determinar:

1. El número, entre $0$ y $2^n$ . Es decir $n$ bits de información.
2. La respuesta fue una mentira. Este es un número entre $1$ y $Q$ , además $Q+1$ para denotar "no mentira", lo que hace que $Q+1$ valores posibles, o $\log_2 (Q+1)$ bits de información.

Dado que cada una de las preguntas aporta 1 bit de información, el mejor número posible de preguntas sería parece para ser $Q=\lceil n+\log_2 (Q+1) \rceil$ . Sí, se trata de una ecuación trascendental con $Q$ en ambos lados; pero se ve mucho mejor que el atado que has propuesto.

En cuanto al algoritmo en sí, lo que yo haría es una búsqueda binaria directa, entendiendo que:

• Estoy buscando no sólo el número $x$ sino también por el número $f$ de la respuesta falsa, donde (como antes) $f=Q+1$ significa que no hay respuesta falsa.
• En cada etapa, mi objetivo es maximizar la información extraída teniendo tantas posibilidades procedentes de una respuesta "Sí" como de una "No". Pero las posibilidades que hay que contar no son los posibles valores de $x$ como lo harían en una búsqueda binaria ordinaria, pero los posibles valores de $\langle x,f\rangle$ . Esto da una opción de pregunta diferente a la tradicional de "punto medio del intervalo".

En lo que sigue, tomaré $n=5$ para que $0\le x\le 31$ . Una simple conjetura implica que $Q$ será 9: es decir, 5 para adivinar $x$ , más un poco más de 3 para adivinar $1\le f\le 10$ . ( $Q=8$ est no suficiente, porque tenemos que tener en cuenta la posibilidad de que no haya ninguna mentira).

Por simetría, la primera pregunta es claramente la misma que en la búsqueda binaria tradicional: "¿es $x\le 16$ ?". Sin pérdida de generalidad, supongamos que la respuesta es afirmativa. En ese caso, las posibilidades son:

• $x\le 16$ y $1\lt f \le Q+1$ : $16Q$ posibilidades.
• $x\gt 16$ y $f=1$ : $16$ posibilidades.

así que efectivamente hemos cortado el $32(Q+1)$ posibilidades a la mitad.

Para la segunda pregunta, nos preguntamos "¿Es $x\le y$ ?" para algún número entero $y$ . Voy a dejar de lado la posibilidad de que $y>16$ porque parece demasiado ineficiente. Hay dos respuestas posibles:

Sí

• $x\le y$ y $2\lt f \le Q+1$ : $(Q-1)y$ posibilidades.
• $y\lt x\le 16$ y $f=2$ : $16-y$ posibilidades.

No

• $y\lt x \le 16$ y $2\lt f\le Q+1$ : $(16-y)(Q-1)$ posibilidades.
• $16\lt x\le 32$ y $f=1$ : $16$ posibilidades.
• $x\le y$ y $f=2$ : $y$ posibilidades.

lo que suma $16(Q+1)$ como era de esperar. Pero las posibilidades se dividen entre $Qy+16$ para Sí y el resto para No por lo que el equilibrio más parejo se logra cuando $Qy+16$ está lo más cerca posible de $8(Q+1)$ es decir, cuando $y$ es lo más parecido a $y=8\frac{Q-1}{Q}$ .

Con $Q=9$ el valor objetivo es $8\times\frac{8}{9}$ que es $7\frac{1}{9}$ . Así que la segunda pregunta debe ser no "¿Es $x\le 8$ ?", como preguntaría una búsqueda binaria ingenua, pero "¿Es $x\le 7$ ?".

Por lo tanto, el algoritmo general antes de formular cada pregunta es:

1. Tenga en cuenta todos los $\langle x,f\rangle$ pares que todavía son posibles dadas las preguntas y respuestas hasta ahora.
2. Recorrer todos los valores posibles de $y$ .
3. Para cada valor de $y$ Considera cuántos $\langle x,f\rangle$ pares coinciden con la respuesta "Sí" a "¿Es $x\le y$ ?" y cuántos responden "No".
4. Elige el valor de $y$ para el que los recuentos de "Sí" y "No" sean los más cercanos, y haga la pregunta utilizando ese valor.

Aunque afirmo que una búsqueda binaria en $\langle x,f\rangle$ espacio es el mejor algoritmo posible, y aunque he dado un valor aproximado para $Q$ En realidad no he demostrado nada.

Answer 3

Este es un algoritmo para Variante 1 que utiliza como máximo $n+2\sqrt{2n}+2$ consultas, junto con su prueba.

1. Dejemos que $k = \lceil \sqrt{2n} \rceil$ .

2. Sigue el algoritmo de búsqueda binaria pero confirma el intervalo actual cada $k$ pasos.

   1. Las consultas utilizadas para confirmar el intervalo actual $[a,b)$ son " $x < a$ " y " $x < b$ ".

   2. Esto requiere como máximo $n + 2 \lfloor \frac{n}{k} \rfloor \le (1+\frac2k)n$ consultas si se ejecuta hasta el final.

   3. Obsérvese que la respuesta coherente a cualquier consulta de confirmación implica que es veraz.

   4. Y las respuestas incoherentes a cualquier consulta de confirmación implican que la mentira se ha agotado.

3. Si esta búsqueda binaria modificada llega al final:

   1. Señala un número determinado $y$ como respuesta (si no se ha mentido).

   2. Si no lo ha hecho ya, utilice $2$ consultas para confirmar $y$ , es decir, " $x < y$ " y " $x < y+1$ ".

4. Si hay una respuesta incoherente a cualquier consulta de confirmación para el intervalo actual $I$ :

   1. Utilizar la búsqueda binaria ordinaria en el intervalo anterior confirmado $J$ .

   2. Para una confirmación en el medio, $J$ es menor que $2^{k+1}$ veces el tamaño de $I$ .

   3. Para una confirmación al final, si $k \nmid n$ entonces $J$ es menor que $2^k$ veces el tamaño de $I$ .

5. Por lo tanto, el número total de consultas utilizadas es como máximo $(1+\frac2k)n + k + 2 \le n + 2 \sqrt{2n} + 2$ .

La pregunta es si esto es asintóticamente óptimo, y si no es así, ¿cuál es un algoritmo asintóticamente mejor?

Answer 4

Esta respuesta se basa en la anterior y ofrece los resultados de la simulación y el código del programa. Por lo tanto, quien lo desee puede comprobarlo ejecutando el programa.

Afirmación (para la versión 1)

Una serie de preguntas, $Q$ suficiente para garantizar una solución correcta incluso en el peor de los casos satisface $$Q=\lceil n+\log_2 (Q+1) \rceil$$

En la práctica, hay que añadir 1 o 2 al número de preguntas formuladas, ya que nunca se puede conseguir un corte binario perfecto: véase la sección de Motivación y los resultados de la verificación más adelante.

Verificación

Esta afirmación se ha verificado programáticamente de la siguiente manera:

• $n=4$ necesita 8 preguntas.
• $n=5$ necesita 9 preguntas.
• $n=6$ necesita 10 preguntas.
• $n=7$ necesita 11 preguntas.
• $n=8$ necesita 13 preguntas.
• $n=9$ necesita 14 preguntas.
• $n=10$ necesita 15 preguntas.
• $n=11$ necesita 16 preguntas.
• $n=12$ necesita 17 preguntas.
• $n=13$ necesita 18 preguntas.

Los valores más altos pueden comprobarse con un programa más optimizado, y más adelante se dan notas para la optimización del tiempo de ejecución. Sin embargo, la comprobación por definición requiere $2^n$ operaciones, de cualquier grado de complejidad, por lo que comprobar cada una de $2^100$ casos no es factible.

Motivación

La motivación clave de este algoritmo es que es imposible deducir $x\in[0,2^n)$ sin deducir simultáneamente también $q\in[0,Q]$ , donde $q$ es el número de la pregunta a la que se ha respondido falsamente. De hecho, se está adivinando $\langle x,q\rangle$ pares, porque adivinar $x$ solo no es posible. Nota: el rango de valores posibles de $q$ abarca uno más que el número de preguntas, porque hay que tener en cuenta la posibilidad de que el contestador no mienta nunca.

Por lo tanto, el contenido de información de un juego es $n+\log_2 (Q+1)$ bits.

Este número es necesario y suficiente. Para ver esto, considere el caso en el que el que responde le dice a un intermediario que haga la respuesta por él. Para poder hacer este trabajo, no basta con que el intermediario sepa cuál es el valor de $x$ es ( $n$ bits). También necesita saber sobre qué pregunta mentir ( $\log_2 (Q+1)$ bits).

Desde el punto de vista de la información, la manera de obtener la máxima información de una pregunta es asegurarse de que [con la mayor exactitud posible] la mitad de los estados de cosas posibles en ese momento coincidan con una respuesta "Sí" y la otra mitad con un "No". Así es también como funciona la clásica búsqueda binaria unidimensional. Si la reducción a la mitad fuera exactamente posible, se obtendría un bit completo de información con cada pregunta y se alcanzaría exactamente el límite mencionado anteriormente.

En la práctica, al construir la pregunta $q$ el equilibrio entre el Sí y el No salta en pasos de $Q-q$ , lo que hace posible que se obtenga algo menos de un bit de información.

Estructuras de datos

La estructura básica es un mapa de bits de $2^n$ bits, marcando qué valores de $x$ son posibles en la actualidad. Necesitamos un conjunto de $Q+1$ estos mapas de bits, uno por cada posible pregunta con respuesta falsa $q$ más uno para el caso de que ninguna respuesta sea falsa. La matriz de mapas de bits se llama Guess en el programa.

Estrategia de solución

En cualquier etapa, el Guess contiene 1 bits para todas las conclusiones ( $\langle x,q\rangle$ pares) que actualmente son compatibles con las respuestas recibidas hasta ahora. Cuando no se han formulado preguntas, el Guess por lo tanto, comienza con todos sus bits a 1. Cuando se han formulado suficientes preguntas para poder deducir el número, sólo un bit de Guess será 1.

Que le digan que " $x<k$ " como respuesta a la pregunta $q$ tiene dos efectos sobre Guess :

1. Para el $q$ El mapa de bits en Guess sabemos que la respuesta es una mentira, por lo que podemos poner a cero todos los bits correspondientes a $x<k$ .
2. Para el resto de mapas de bits, sabemos que la respuesta es verdadera, por lo que podemos poner a cero todos los bits correspondientes a $x\ge{k}$ .

Queda por saber qué valor de $k$ para usar al hacer la pregunta. El valor de $k$ utilizar es la que reduzca al máximo el número de bits en Guess . En el programa siguiente, he utilizado una búsqueda lineal exhaustiva para encontrar este valor.

El programa en C++

#include <iostream>
#include <bitset>
#include <vector>
#define NBITS 10
#define NQUESTIONS 16 // The maximum number of questions to allow for.
#define NVALUES (1<<(NBITS))
typedef std::bitset<NVALUES> Bits;
class Guess
{Bits valid[NQUESTIONS+1];
public:
 void splitInto(Guess &ifLess,Guess &ifGreaterOrEqual,int questionNumber,int k) const
  {Bits temp;
   for (int i=0;i<k;i++)
    temp.set(i);
   for (int q=0;q<=NQUESTIONS;q++)
    if (q!=questionNumber)
      {ifLess.valid[q] = this->valid[q] & temp;
       ifGreaterOrEqual.valid[q] = this->valid[q] & ~temp;
       }
     else
      {ifGreaterOrEqual.valid[q] = this->valid[q] & temp;
       ifLess.valid[q] = this->valid[q] & ~temp;
       }
   }
 Guess() {for (int q=0;q<=NQUESTIONS;q++) valid[q].set();};
 int count(int maxQ=NQUESTIONS) const {int total=0; for (int q=0;q<=maxQ;q++) total += valid[q].count(); return total;};
 };

La función splitInto toma un preexistente Guess y rellena los dos resultados del objeto Guess objetos: uno en la suposición de que la respuesta a la pregunta es " $x<k$ " y otro sobre la suposición de que la respuesta a la pregunta es " $x\ge k$ ". Los dos objetos, combinados, contendrán tantos bits como el objeto original. Esta no es la forma más eficiente de jugar al juego de las adivinanzas, pero es la mejor manera de investigar todas las posibles secuencias de respuestas para calcular el peor de los casos.

static int maxQuestion=0;
void recursion(int questionNumber,const Guess &status)
{if (questionNumber>=NQUESTIONS)
   exit(3); // Overflowed the space available in `Guess`.
 if (questionNumber>maxQuestion) maxQuestion=questionNumber;
 Guess ifLess,ifGreaterOrEqual;
 /* The first task is to calculate the best estimate of k. 
    Find the value for which the Yes and No answers generate the most equal numbers of results.
    */
 int k=-1; // Best value so far.
 int deltaLast=NVALUES*(NQUESTIONS+1); // Smallest difference so far.
 for (int k2=1;k2<NVALUES;k2++) // Linear search: inefficient but certain.
  {status.splitInto(ifLess,ifGreaterOrEqual,questionNumber,k2);
   int delta=std::abs(ifLess.count()-ifGreaterOrEqual.count());
   if (delta<deltaLast)
     {k=k2;
      deltaLast=delta;
      };
   };
 /* Now split `Guess` according to "x<k?". */ 
 status.splitInto(ifLess, ifGreaterOrEqual, questionNumber, k);
 /* If more than one possibility in the Yes branch, ask deeper.
 if (ifLess.count(questionNumber+1)>1)
   recursion(questionNumber+1,ifLess);
 /* If more than one possibility in the No branch, ask deeper. */
 if (ifGreaterOrEqual.count(questionNumber+1)>1)
   recursion(questionNumber+1,ifGreaterOrEqual);
 }

La función recursion busca el valor más prometedor de $k$ ( es decir. la que tenga resultados más equilibrados) y luego divide la conjetura actual de acuerdo con ella. Si alguno de los resultados (el que asume que la respuesta es verdadera y el que asume que la respuesta es falsa) tiene más de un 1 bit, ese resultado debe ser investigado más a fondo y recursion se llama a sí mismo recursivamente para hacer esto.

Por último, inicie la recursión con una nueva inicialización de Guess y 0 preguntas hechas hasta ahora.

int main(int argc, const char * argv[])
{Guess base;
 recursion(0,base);
 std::cout << maxQuestion+1;
 return 0;
}

Optimización

Las mejores optimizaciones serían:

• Representar los posibles resultados mediante $[low,high)$ rangos en lugar de por mapas de bits. Esto restringe el tipo de pregunta que se hace, que pasa de ser una pregunta completamente general, "¿ $x$ tener una propiedad $P$ ", a una específica " $x<k$ ?", uno de los utilizados en este problema concreto. También reduce los bits necesarios para almacenar el conjunto de resultados posibles.
• Tenga en cuenta que el número de resultados coincidentes con " $x<k$ "aumenta monótonamente con $k$ excepto cuando se mira el bloque de resultados correspondiente a una mentira en el número de pregunta actual cuando disminuye. Por lo tanto, el gráfico general de "número de resultados que coinciden Sí si elegimos este valor de $k$ " es monótona hacia arriba, luego hacia abajo, luego hacia arriba, y esto se puede buscar en tiempo logarítmico en lugar de lineal.

Versión 2 de la pregunta

El mismo principio debe aplicarse al caso en que hasta $rQ$ las preguntas pueden ser contestadas falsamente. De nuevo, la clave es que lo que se deduce no es el valor de $x$ solo pero, inevitablemente, el valor de $\langle x,\vec q\rangle$ , donde $\vec q$ es la lista de preguntas que han sido contestadas falsamente. Por lo tanto, la estrategia óptima, una vez más, es la que en cada etapa se acerca más a la bisectriz de las preguntas aún válidas $\langle x,\vec q\rangle$ valores.

Reescribiendo la fórmula original para $Q$ como $$2^Q\ge 2^n(Q+1)$$ y simplificando temporalmente "como máximo $rQ$ mentiras" a "exactamente $rQ$ mentiras", obtenemos la fórmula revisada para $Q$ : $$2^Q\ge 2^n\binom{Q}{rQ}$$ Cuando $r=\frac12$ utilizando la aproximación estándar para los factoriales, esto se aproxima a $$2^Q\ge 2^n 2^Q$$

Esto es imposible, lo que corresponde al argumento verbal de imposibilidad dado en la pregunta original. En efecto, con un factor de sobra de $2^n$ para jugar, un límite ligeramente inferior para $r$ debe ser justificable.

Answer 5

Variante 1

Tratamos el caso general en el que $x \in \{1..m\}$ para cualquier número entero positivo $m$ , en lugar de sólo $x \in \{1..2^n\}$ . Sea $k$ sea el número mínimo de consultas necesarias. Si $m = 1$ entonces $k = 0$ por lo que a partir de ahora supondremos que $m \ge 2$ en cuyo caso es fácil ver que $k \ge 3$ . $\def\floor#1{\left\lfloor #1\right\rfloor }$ $\def\ceil#1{\left\lceil #1\right\rceil }$

Límite inferior

Considere la siguiente estrategia del director del juego:

Para cada $i \in \{1..k\}$ mantener $S_i$ como la colección de todos los posibles $x$ que satisface las respuestas a las consultas hasta el momento en que el $i$ -se supone que se responde falsamente, y se mantiene $S_0$ como la colección de todos los posibles $x$ que satisface las respuestas a todas las consultas hasta el momento. A continuación, en cada consulta, elige la respuesta que maximiza el total de los tamaños de las $S_i$ , a saber $\sum_{i=0}^k \#(S_i)$ .

Al principio, $\sum_{i=0}^k \#(S_i) = (k+1)m$ . En cada consulta, para cada $i \in \{0..k\}$ dejar $T_i$ y $U_i$ sea la resultante $S_i$ al responder "sí" y "no" respectivamente. A continuación, $S_i$ es la unión disjunta de $T_i,U_i$ porque cada posibilidad queda bajo exactamente una de las dos respuestas. Así, $\sum_{i=0}^k \#(S_i)$ $= \sum_{i=0}^k \#(T_i) + \sum_{i=0}^k \#(U_i)$ y, por tanto, la resultante $\sum_{i=0}^k \#(S_i)$ será al menos la mitad del valor anterior.

Al final, el jugador debe saber $x$ y, por lo tanto, saber también qué pregunta se ha contestado falsamente, si es que se ha contestado. Por lo tanto, sólo una de $S_{0..k}$ es no vacía, y por lo tanto $\sum_{i=0}^k \#(S_i) = 1$ .

Por lo tanto, $2^k \ge (k+1)m$ . De esto obtenemos $k \ge \log_2(4m) = \log_2(m)+2$ y por lo tanto:

$k \ge \log_2( \ceil{\log_2(m)+3} \cdot m ) = \log_2(m) + \log_2(\ceil{\log_2(m)+3})$ .

Obsérvese que el razonamiento de Martin no es válido porque afirma que el jugador debe distinguir $(k+1)m$ posibilidades, lo que nunca es cierto en ningún momento del juego; desde el punto de vista del jugador el número de escenarios posibles es siempre como máximo $m$ . Sin embargo, lo anterior muestra que la idea de Martin de cómo el jugador puede encontrar $x$ eficientemente se puede convertir en una estrategia para que el game-master pueda retrasar al jugador de encontrar $x$ .

También hay que tener en cuenta que esta estrategia para el director del juego puede no ser óptima. Es posible que la elección de la respuesta que deja un $\sum_{i=0}^k \#(S_i)$ podría ser mejor en algunos casos raros porque los "cortes" posteriores podrían ser lo suficientemente desiguales como para que sea peor que elegir la respuesta contraria.

Estrategia óptima

Obsérvese que en la estrategia óptima, dada cualquier $2$ consultas precedentes " $<a$ " y " $<b$ ", si las respuestas son ambas "sí", entonces $x < \max(a,b)$ porque sólo puede haber como máximo una respuesta falsa, y del mismo modo si las respuestas son ambas "no" entonces $x \ge \min(a,b)$ . Como es inútil hacer una consulta que "corte" fuera del intervalo posible para $x$ la estrategia óptima siempre mantendría tres intervalos adyacentes de longitud $p,q,r$ en ese orden tal que $x$ está en uno de ellos y se encuentra en el intervalo medio si las consultas que lo delimitan fueron respondidas con veracidad. Sea $f(p,q,r)$ sea el número mínimo de consultas necesarias para determinar $x$ .

Entonces obtenemos inmediatamente el siguiente programa recursivo (en Javascript con memoización):

var v=[];
function f(p,q,r)
{ 
    if( p+q+r<=1 ) return 0;
    if( q==0 ) return Math.ceil(Math.log(p+r)/Math.log(2));
    if( !v[[p,q,r]] )
    {
        var m=2*(p+q+r);
        if( p>0 ) m=Math.min(m,Math.max(f(p,0,q),f(0,q,r)));
        if( r>0 ) m=Math.min(m,Math.max(f(p,q,0),f(q,0,r)));
        for(var a=1;a<q;a++) m=Math.min(m,Math.max(f(p,a,q-a),f(a,q-a,r)));
        v[[p,q,r]]=1+m;
    }
    return v[[p,q,r]];
}

Brevemente, los casos base son obvios, es decir, cuando sólo hay un valor posible para $x$ o el intervalo central está vacío, lo que significa que la mentira se ha agotado y podemos realizar una búsqueda binaria ordinaria en el intervalo restante. Los casos de transición se deben a que es inútil hacer una consulta que "corte" fuera del intervalo medio (¡esto requiere algo de reflexión!), y también es inútil hacer la misma consulta la tercera vez si las dos primeras se responden de forma consistente.

Por supuesto, $k = f(0,m,0)$ y se necesita $O(M^4)$ para calcular todos los $k$ para $m \in \{1..M\}$ Así que lo ejecuté para $M = 100$ :

Si $m = 2$ entonces $k = 3$ .

Si $m \in \{3..4\}$ entonces $k = 5$ .

Si $m \in \{5..7\}$ entonces $k = 6$ .

Si $m \in \{8..12\}$ entonces $k = 7$ .

Si $m \in \{13..22\}$ entonces $k = 8$ .

Si $m \in \{23..40\}$ entonces $k = 9$ .

Si $m \in \{41..70\}$ entonces $k = 10$ .

Si $m \in \{71..100\}$ entonces $k = 11$ .

Por todo esto, $k$ es como máximo $1$ más que el límite inferior, por lo que conjetura :

? $k \le \ceil{ \log_2(m) + \log_2(\ceil{\log_2(m)+3}) } + 1$ .

Pero, ¿cómo demostrarlo? Lo he intentado pero no he encontrado la manera. ¿Alguien puede probarlo o refutarlo?

Una estrategia más sencilla que podría ser óptima

El jugador puede (dado $k$ ) siguen la siguiente estrategia:

Mantener el mismo $S_{0..k}$ como se ha definido anteriormente. En cada paso, elija $y$ y hacer la pregunta " $x < y$ " de manera que el resultado $\sum_{i=0}^k \#(S_i)$ es lo más cercano posible a la mitad del valor anterior.

No está claro si ésta es la estrategia óptima, aunque es probable que lo sea. Martin afirma que es la mejor, pero esto es un error clásico de asumir que la solución codiciosa es globalmente óptima. ¿Cómo podemos saber si un "corte" un poco menos uniforme en un paso no garantiza "cortes" más fáciles más adelante? Pero si sabemos que la estrategia del director del juego anterior es óptima, entonces la optimalidad de esta estrategia se deduce porque las posibilidades resultantes son monótonas en la ubicación del "corte si la respuesta a la consulta es la misma.

Dejemos que $c_t$ sea $\sum_{i=0}^k \#(S_i)$ después del paso $t$ , donde $c_0$ es el valor inicial al comienzo del juego.

En el paso $t \in \{1..k\}$ , eligiendo $y = 0$ hará $\sum_{i=0}^k \#(T_i) = 0$ , mientras que la elección de $y = m$ hará $\sum_{i=0}^k \#(T_i) = \sum_{i=0}^k \#(S_i)$ . También aumenta $y$ por $1$ hará $\sum_{i=0}^k \#(T_i)$ aumentar en algún número en el rango $[0,k-t+2]$ porque $S_i,S_j$ son disjuntos para cualquier $i,j \in \{0..t-1\}$ . Por lo tanto, siempre podemos elegir $y$ tal que $\sum_{i=0}^k \#(T_i)$ está dentro de $\frac{k-t+2}{2}$ de $\frac12 c_{t-1}$ , lo que implicaría que $c_t \le \floor{ \frac12 c_{t-1} + \frac{k-t+2}{2} }$ .

Esta es la recurrencia más ajustada que puedo conseguir, ¡pero aún no es suficiente! Si no me he equivocado, al resolver la recurrencia se obtiene el límite superior de $c_k$ siendo siempre mayor que $3$ lo que significa que no podemos garantizar analíticamente que $k$ Las consultas que siguen esta estrategia son suficientes independientemente del tamaño $k$ ¡es! Sé que esto parece ridículo, pero no veo la manera de apretar los límites.

Por lo tanto, dado que no podemos demostrar la optimalidad de la estrategia del game-master o el éxito de la estrategia de este jugador, incluso la implementación de este algoritmo tal cual es inútil, porque sí sabemos si la respuesta con menor $c_t$ será mejor para el game-master o no, y por tanto acabamos teniendo que realizar una búsqueda exponencial (podada o no) para asegurar la corrección.

Además, no sabemos $k$ así que no podemos ni siquiera implementar este algoritmo a menos que encontremos $k$ por algún otro medio primero (como la estrategia óptima).

Variante 2

El límite inferior se extiende a esta variante por un argumento similar. Sin embargo, la estrategia óptima no lo hace. La estrategia más sencilla sí lo hace, pero está aún menos claro si es óptima, y de nuevo nos enfrentamos al problema de encontrar $k$ .