Adivinar el número en el conjunto 1-100 con preguntas ponderadas.

Question

Se necesita adivinar un número del 1 al 100. Puedo hacer preguntas y obtener respuestas: "sí" o "no". Por la respuesta "sí" debo pagar un dólar, por la respuesta "no" - dos dólares. ¿Cuántos dólares debo tener para adivinar exactamente mi número?

La decisión obvia es el producto del límite superior de $log_2 100$ en 2 (siempre dividimos nuestro conjunto en dos partes iguales y esperamos el peor caso).

Pero creo que no es un algoritmo óptimo, quizás sea mejor dividir mi conjunto en otra proporción que no sea uno a uno debido a los costos desiguales de las preguntas. Tal vez en una proporción de dos a uno.

Ayuda a encontrar la mejor solución por favor. Gracias de antemano.

Answer 1

Un poco de formalización, marquemos las preguntas por $A_{i}, 1\leq i\leq n$. Notemos $P(A_{i})=x_{i}$ - probabilidad de obtener un "sí" para $A_{i}$. La media es $1 \cdot x_{i} + 2 \cdot (1-x_{i})=2-x_{i}$. El precio total es $2 \cdot n-\sum_{i=1}^{n}x_{i}$ - un problema de optimización de $x_{i}$ y $n$. En particular, $x_{1}=x_{2}=...=x_{n}=x$, entonces el precio es $n \cdot (2 - x)$.

Al dividir el conjunto (y subconjuntos subsecuentes) en una proporción $M:K$, tenemos 2 casos extremos:

• supongamos que cada pregunta es sobre el lado $M$ y siempre acertamos "sí", $(\frac{M}{M+K})^{n} \cdot 100 \approx 1$ o $n \approx -\log_{\frac{M}{M+K}}100$ y el precio es $\approx -\log_{\frac{M}{M+K}}100$, (porque $x=1) que asciende por $y=\frac{M}{M+K}$ en $(0,1)$ http://www.wolframalpha.com/input/?i=-log_%7Bx%7D%28100%29. Es decir, tendemos a reducir M e incrementar K, para que acertemos "sí" en subconjuntos más pequeños.
• supongamos que cada pregunta es sobre $M$ y siempre acertamos "no" (como si el número no estuviera en ese lado), entonces continuaremos con el otro lado siempre, es decir, $(1-\frac{M}{M+K})^{n} \cdot 100 \approx 1$ o $n \approx -\log_{\frac{K}{M+K}}100$ y el precio es $\approx -2 \cdot\log_{\frac{K}{M+K}}100$, (porque $x=0$) que asciende nuevamente por $y=\frac{K}{M+K}$ en $(0,1)$. Es decir, tendemos a reducir K e incrementar M, para acertar "no" en subconjuntos más grandes.

Terminamos con este "aumentar-reducir" el $K$ e "incrementar-reducir" el $M$ al mismo tiempo, lo cual indica (en mi humilde opinión) que 50:50 podría ser la mejor opción.