Estrategia óptima para el juego de adivinanzas

Question

El juego va como esto:

Me escoger un número al azar entre 1 y 1000. Usted tiene que adivinar cuál es ese número. Si adivina correctamente, consigue 1150. Si responde mal, se pierde 98. Usted también puede pedir para cualquier número de pistas, pero la primera pista le costará 2, la segunda pista tendrá un costo de 4, el tercero tendrá un costo de 8, etc. Las sugerencias son sólo preguntas sí/no. ¿Cuál es la estrategia óptima?

Pensé en hacerlo con búsqueda binaria, sino que utiliza demasiados consejos. Sin embargo binario de búsqueda quita la mitad de los valores de cada tiempo y yo no puedo averiguar algo que es más eficiente. Existe una mejor estrategia?

Answer 1

Añadido: ahora creo que usted debería ser capaz de adivinar tantas veces como sea necesario, pagar $98$ por cada mal supongo. En virtud de esta regla que debe desempeñar. Do $7$ etapas de la búsqueda binaria, cálculo de $510$ y dejando $7$ (con una probabilidad de $\frac 3{16}$) o $8$ (con una probabilidad de $\frac {13}{16}$) posibilidades de la izquierda. Ahora supongo que el resto de los números uno por uno. Que esperas para adivinar la mitad de los números equivocados antes de la de la derecha, por lo que su expectativa es $1150-\frac 3{16}\cdot 3\cdot 98 -\frac {13}{16}\cdot \frac 72 \cdot 98-510=306.1875$. Su mejor resultado es $1150-510=640$ y su peor es $1150-510-7\cdot 98=-46$. Usted no quiere preguntar a uno más de la búsqueda de la pregunta debido a que los costos de $512$ y sólo le ahorra a usted acerca de una suposición para $98$. Usted no desea iniciar la adivinación después de las seis de la búsqueda de las preguntas debido a que ahorra $256$, pero se añaden cuatro más esperado mal conjeturas.

Esto fue escrito suponiendo que sólo tiene una, y supongo obtenía $1150$ si fue la correcta y pagado $98$ si estaba mal. De cualquier manera usted detenido. Claramente no quieren pedir a la última pregunta, ya que los costos de $1024$ para que se de $2$ posibilidades a $1$ (aquí vamos a considerar los números vayan a $1024$, de modo de tener siempre dos a la izquierda después de nueve aciertos. Eso no va a cambiar mucho). Mejorar tus ganancias esperadas de$\frac 12(1150-98)=526$$1150$. Si usted hace una búsqueda binaria para $k$ preguntas que usted ha $\frac {1024}{2^k}$ posibilidades a la izquierda y pasar $2^{k+1}-2$. Entonces supongo que entre el resto de posibilidades. Su ganancia esperada es $1150 \cdot \frac {2^k}{1024}-98\left(1-\frac {2^k}{1024}\right)-2^{k+1}+2$. Me parece de hacer cualquier pregunta disminuye su expectativa, así que lo mejor que puedes hacer es adivinar la derecha de la caja. Volviendo a $1000$ posibilidades, las ganancias esperadas es, a continuación,$\frac {1150-98\cdot 999}{1000}=-96.752$. Preguntando una pregunta disminuye a este a $\frac {1150-499\cdot 499}{500}-2=-97.504$ no jugar el juego.

Answer 2

Deje $f(n,c)$ ser el mínimo costo esperado para un intervalo de tamaño de $n$ y el coste de partida de la sugerencia $c$,$f(1, c) = 0$$f(n, c)$, en general, es igual a:

$$ \min\left(\frac{n-1}{n}\cdot(98 + f(n-1, c)), c+\frac{\lfloor n/2 \rfloor \cdot f(\lfloor n/2\rfloor,2c)}{n}+\frac{\lceil n/2 \rceil \cdot f(\lceil n/2\rceil,2c)}{n} \right) $$

Ahora $f(1000, 2) = 588.768$ que es mejor que sólo con sugerencias, y así que la respuesta a tu pregunta es que sí, hay una estrategia mejor (en realidad se puede rastrear los minutos allí, si desea recuperar el árbol de decisión).

Espero que esto ayude a $\ddot\smile$.