¿Cómo minimizar el costo de adivinar un número en un juego de adivinanzas alto/bajo?

Question

En un juego de adivinanzas alto/bajo, el número "verdadero" es uno de $\{1, \cdots ,1000\}$ . Se te dirá si tu suposición es $<,>$ o $=$ el número verdadero para cada adivinanza que haces, y el juego termina cuando adivinas el número verdadero. Supongamos los siguientes tres escenarios:

1. Si tu suposición es más baja o más alta, pagas $\$ 1$ en ambos casos. Si tu suposición es correcta, no pagas nada y el juego termina.

2. Si tu suposición es más alta, pagas $\$ 1$ Si tu suposición es menor, pagas $\$ 2$ . Si tu suposición es correcta, no pagas nada y el juego termina.

3. Si tu suposición es más alta, pagas $\$ 1$ Si tu suposición es menor, pagas $\$ 1.5$ . Si tu suposición es correcta, no pagas nada y el juego termina.

En estos tres escenarios, lo que es, respectivamente, el mínimo número de $\$$ debes tener que Asegúrate puedes encontrar el número verdadero?

Formalmente, definir un espacio de todas las estrategias de adivinación $ \Sigma $ . Podemos entonces identificar el costo $C$ como una función $$ C:\Sigma\times \{1, \cdots ,1000\} \to\Bbb N_+, \quad v \mapsto C(S,v)$$ que mapea el par $(S,v)$ (donde $v$ es el número "verdadero") al costo que va a tomar bajo este arreglo. Nuestro problema es entonces encontrar $$ \min_ {S} \max_ {v} C(S,v).$$

¿Puede este problema min-max ser resuelto analíticamente? ¿Cuál sería la estrategia óptima correspondiente entonces?

Para el escenario 1, mi intuición es usar la búsqueda de bisección, lo que, en el peor de los casos, cuesta $\$ 10$ ( $2^{10}=1024$ ). Pero no puedo probar que esto sea realmente óptimo. Para el segundo escenario, ya que hacer una suposición errónea significa un costo mayor, tal vez sea más óptimo usar una bisección "derecha", es decir, seguir haciendo suposiciones en el $2/3$ -punto cuantitativo. Pero esto es sólo (más bien salvaje ) intuición, nada cercano a una prueba.

Answer 1

Para este juego, la representación más natural de una estrategia es un árbol binario rooteado, con vértices etiquetados por conjeturas (es decir, números de $\{1, \ldots, N=1000\}$ ), y cada vértice tiene a lo sumo dos aristas (que lo conectan con la conjetura a realizar a continuación, para los casos "inferior" y "superior").

Que las sanciones que se pagan por los casos "inferiores/ superiores" sean $L$ y $H$ respectivamente. Consideremos ahora un $N$ y considerar un árbol óptimo $T(N)$ (que alcanza la mínima penalización total en el peor de los casos). Su raíz está etiquetada con alguna conjetura $R$ , $1\leqslant R\leqslant N$ su subárbol izquierdo puede ser elegido para ser [isomorfo a] $T(R-1)$ y su subárbol derecho es isomorfo a $T(N-R)$ (suponiendo que $T(0)$ está vacío).

Así que si $P(N,L,H)$ es la sanción óptima, entonces $$P(0,L,H)=P(1,L,H)=0,\\ P(N,L,H)=\min_{1\leqslant R\leqslant N}\max\begin{cases}L+P(N-R,L,H)\\ H+P(R-1,L,H)\end{cases}\quad(N>1)$$ que permite calcular $$P(1000,1,1)=\color{red}{9},\quad P(1000,2,1)=14,\quad P(1000,1.5,1)=11.5$$ (nota $9$ pero no $10$ como has sugerido; el proceso de decisión no es sólo una bisección, sino que tiene un plus de " $=$ " resultados). Los árboles pueden ser calculados en el camino.

En cuanto a la asintótica comportamiento (con $N\to\infty$ ), si dejamos que $R(N,L,H)$ sea el "argmin" (digamos, la raíz más pequeña de los árboles óptimos), se puede demostrar que los límites $$\alpha=\alpha(L,H)=\lim_{N\to\infty}\frac{P(N,L,H)}{\ln N},\quad\beta=\beta(L,H)=\lim_{N\to\infty}\frac{R(N,L,H)}{N}$$ existen y satisfacen $$H+\alpha\ln\beta=L+\alpha\ln(1-\beta)=0.$$ En particular, $\beta(2,1)=(\sqrt{5}-1)/2$ y $\beta(1.5,1)$ es la raíz de $\beta^3=(1-\beta)^2$ .

Answer 2

Para el caso de (2,1), he comprobado que el coste en el peor de los casos aumenta en 1 en cada número de Fibonacci, por lo que $P(F_n,2,1)=1+P(F_n-1,2,1)=1+P(F_{n-1},2,1)$ . Estos valores clave $F_n$ aumentar en proporción $F_n/F_{n-1}\to\phi=(1+\sqrt{5})/2$ .
Crecen exponencialmente; a la inversa, el coste máximo para $P(N,2,1)$ crece logarítmicamente.

Para (1,5,1) el coste del peor caso aumenta en $0.5$ a estos valores: $$P(N,2,1)>P(N-1,1.5,1)\,if\, N=2,3,4,5,7,9,12,16,21,28,37,49,65,86,114,\ldots$$

La recursión en esta secuencia es $a_{n+1}=a_{n-1}+a_{n-2}$ . Su proporción, $a_{n+1}/a_n$ se acerca a 1,3246, que es la raíz de $P^3=P+1$ , al igual que $\phi$ para el caso (2,1) es la raíz de $P^2=P+1$ .

Answer 3

A continuación se presentan algunos casos resueltos para listas más pequeñas y penalizaciones variables.

Suponga que paga $a$ por una conjetura demasiado baja y $b$ por una conjetura demasiado alta.

Dada una lista como $\{1,\ldots,1000\}$ el coste $C$ de la estrategia óptima es una función sólo del número de elementos $n$ en la lista. Sin pérdida de generalidad, supongamos que $a\leq b$ . (Si quiere el caso $a\geq b$ , sólo hay que invertir el orden de la lista).

Podemos determinar el coste de la estrategia óptima en algunos casos sencillos:

• $C(1) = 0$ . Sólo hay una suposición, y es correcta.
• $C(2) = a$ . Las suposiciones altas se penalizan más, así que adivina el elemento más bajo.
• $C(3) = b$ . Adivina el elemento del medio. Si te equivocas, sabes cuál es el elemento correcto y cuesta en el peor de los casos $b$ total.

---

Para valores mayores de $C(n)$ Considera cuál es el primer movimiento óptimo. Supongamos que hay $n$ elementos en la lista y se elige el índice $1\leq k\leq n$ . En el peor de los casos, se equivoca. Si la respuesta verdadera es más baja, debe pagar $b$ y buscar en una lista de $k-1$ elementos. Si la respuesta verdadera es más alta, debe pagar $a$ y buscar en una lista de $n-k$ elementos. Así que en el peor de los casos, al elegir $k$ en la primera ronda, incurrirá en un coste de $$\max\left(b + C(k-1),\; a + C(n-k)\right).$$ Podemos buscar un óptimo $k$ que minimiza este coste en la primera jugada, en cuyo caso la solución recursiva nos dice cuál es el resto de la estrategia (y su correspondiente coste).

Tenga en cuenta que la estrategia óptima nunca estará en la última mitad de la lista. Esto se debe a que $C$ es monótona. Cuando $k$ está en la mitad derecha de la lista (para que $n-k \leq k-1$ ), siempre podemos reducir el coste del peor caso $\max(b+C(k-1), a+C(n-k))$ mediante el intercambio de $k-1$ y $n-k$ , poniendo $k$ en la posición simétrica de la mitad izquierda de la lista.

Por este razonamiento, encontramos:

• $C(4) = \max(2a,b).$ Elija el segundo elemento. Si es demasiado alto, pagará un coste de $b$ pero conocer la verdadera respuesta. Si es demasiado baja, pagará un coste de $a$ y, a continuación, buscar entre los dos elementos restantes un coste en el peor de los casos de $C(2)=a$ .

• $C(5) = a+b$ . Puedes elegir el segundo o el tercer elemento (del medio). En el peor de los casos, si eliges el elemento del medio, es demasiado alto y pagas $b+C(2) = a+b$ para buscar los dos restantes. Si eliges el segundo elemento, en el peor de los casos es demasiado bajo por lo que pagas $a+C(3) = a+b$ para buscar los tres restantes.

• $C(6) = a+b$ . Elige el tercer elemento. En el peor de los casos, o bien es demasiado alto, por lo que se paga $b+C(2) = a+b$ o es demasiado bajo, por lo que se paga $a+C(3)=a+b$ .

• $C(7) = \min(a+C(4), b+C(3)).$ Como en el caso $n=4$ la estrategia óptima depende de las magnitudes relativas de $a$ y $b$ . Si $2b > 3a$ entonces elija el tercer elemento de la lista. En caso contrario, elige el cuarto (el del medio).