Estrategia óptima para un juego de adivinación de números de dos jugadores (El precio es correcto)

Question

A dos jugadores se les da un rango de números enteros y luego cada uno toma un turno para adivinar un número.

Si el jugador adivina incorrectamente se anunciará "Más alto" o "Más bajo" y el otro jugador toma su turno.

Para una versión de un jugador de este juego, una búsqueda binaria sería óptima. Sin embargo, en la versión de dos jugadores, tu oponente obtiene la información de tu conjetura y puede utilizarla inmediatamente. ¿Hay alguna estrategia que funcione en este juego?

Answer 1

Dejemos que $p_n$ sea la probabilidad de que el primer jugador pueda ganar esta partida empezando por $n$ números, suponiendo que ambos jugadores jueguen de forma óptima. Demostraré por inducción que $$p_n=\begin{cases} \frac{1}{2} &\text{ if $ n $ is even} \\ \frac{n+1}{2n} &\text{ if $ n $ is odd.}\end{cases}$$

El caso base $n=1$ es trivial: $p_1=1$ ya que el primer jugador siempre gana.

Supongamos que $n>1$ y hemos demostrado la fórmula anterior para $p_k$ para todos $k<n$ y ahora considera el juego con $n$ números. En primer lugar, supongamos $n$ es impar. Desde $p_k\geq 1/2$ para todos $k<n$ Si el primer jugador no acierta, el segundo jugador tendrá al menos un $\frac{1}{2}$ posibilidad de ganar a continuación. Así que lo mejor que puede hacer el primer jugador es asegurarse de que si se equivoca, el intervalo restante de números tiene un número par de números, por lo que el segundo jugador tiene exactamente un $\frac{1}{2}$ posibilidad de ganar. El primer jugador siempre puede hacerlo adivinando el mayor o el menor número posible, ya que si se equivoca habrá $n-1$ números a la izquierda. Usando esta estrategia, el primer jugador tiene una $\frac{1}{n}$ posibilidad de ganar inmediatamente, y una $\frac{1}{2}$ oportunidad de ganar si no ganan inmediatamente, dando $$p_n=\frac{1}{n}+\frac{1}{2}\cdot\frac{n-1}{n}=\frac{n+1}{2n}.$$

Supongamos ahora que $n$ es par. Si el primer jugador adivina el $k$ número en el rango, tienen un $\frac{1}{n}$ posibilidad de ganar inmediatamente. Si su apuesta es demasiado alta ( $\frac{k-1}{n}$ azar), entonces ganan con probabilidad $1-p_{k-1}$ . Si su estimación es demasiado baja ( $\frac{n-k}{n}$ oportunidad) ganan con probabilidad $1-p_{n-k}$ . De los números $k-1$ y $n-k$ uno es par y el otro es impar; que $a$ sea el de impar así que $n-a-1$ es el par. Entonces la probabilidad de que el primer jugador gane en este escenario es $$\frac{1}{n}+\frac{a}{n}(1-p_a)+\frac{n-a-1}{n}(1-p_{n-a-1})=\frac{1}{n}+\frac{a}{n}\cdot\frac{a-1}{2a}+\frac{n-a-1}{2n}=\frac{1}{2}.$$ Esto no depende de $a$ , por lo que todas las opciones de $k$ son igualmente buenos y $p_n=\frac{1}{2}$ .

De la prueba anterior también podemos extraer una estrategia óptima. Si $n$ es impar, debe elegir el número más alto o el más bajo (en realidad, cualquier número que divida el rango en dos rangos de longitudes pares es igualmente bueno). Si $n$ es par, no importa el número que elijas.