¿Cuánto estás dispuesto a pagar por este juego de cofres del tesoro?

Question

Me dio un problema interesante que viene en dos partes.

Delante de usted es un cofre del tesoro que contiene \$1000 con una de 6 dígitos cerradura de combinación. Usted tiene que pagar una cantidad constante cada vez que se el cambio de un dígito. ¿Cuál es la cantidad máxima que estás dispuesto a pagar por turno?

No estoy seguro si mi enfoque aquí es correcta: si el valor esperado del juego es $E$ y la cantidad que pago por turno es $x$, luego $$E=\frac{1}{10^6}(1000-x)+\frac{10^6-1}{10^6}(E-x)$$ $$=E\left(1-\frac{1}{10^6}\right)+\frac{1000}{10^6}-x.$$ $$\Rightarrow E=1000-10^6x.$$ Para el positivo de la rentabilidad, se requieren $x<1000/10^6$, es decir, queremos pagar menos de \$0.001.

Mi principal problema es con la siguiente subproblem.

Cuando dos o menos dígitos son correctos, un LED en el pecho se ilumina de color rojo. Cuando tres o más (pero no de seis) dígitos son correctos, el LED se ilumina en amarillo. Cuando todos los dígitos son correctos, el LED se ilumina en verde y el pecho se abre. Existe una estrategia óptima? ¿Cuánto están dispuestos a pagar por turno ahora?

¿Cómo es exactamente lo que nos forma una estrategia? No estoy seguro de la forma más eficiente para mantener el seguimiento de la correcta dígitos, y cómo volver a la pista si un LED amarillo cambia a rojo. También estoy seguro de cómo esto afecta a la ecuación de la expectativa. Podría alguien que me guíe en esto, por favor? Gracias!

Answer 1

• $\bf{\color{red}{\text{RED}}}$ es $0, 1, 2$ dígitos a la derecha
• $\bf{\color{orange}{\text{YELLOW}}}$ es de $3, 4, 5$ dígitos a la derecha
• $\bf{\color{green}{\text{GREEN}}}$ para el mismo número
• $n = \overline{d_6d_5d_4d_3d_2d_1}$

Pues nada, a priori, cualquiera de primer supongo que funcionará de la misma manera, supongo

$0-0-0-0-0-0$

Pocos casos son posibles (no sabemos cuál es el caso, excepto para el color),

• $3$ a $5$ dígitos se acertó. A continuación, para cada dígito $d_1, \ldots, d_6$ probarlo(el dígito) de $1$ a $9$, por ejemplo, para $d_1$

  $0-0-0-0-0-1$ a $0-0-0-0-0-9$ se trató de

  si el color cambia (en el primer intento) a ROJO, hemos inicialmente adivinado $3$ dígitos a la derecha, incl. $d_1=0$

  si el color cambia a VERDE (durante los 9 ensayos), hemos terminado

  de lo contrario, no concluyentes. A continuación, proceder de la misma manera con otras ubicaciones $d_2$ hasta $d_6$. Si no se $3$ o $5$ correcto de dígitos inicialmente, este será el establecido en los ensayos. Vamos a necesitar en el peor de todas las $54$ ensayos en caso de $5$ (pero vamos a aprender el número), para $3$ después de que en la mayoría de las $28$ ensayos sabremos que es $3$ y que los dígitos de la derecha (una vez que sabes es $3$ - $1$ el juicio es suficiente para comprobar cada dígito si es correcto o no, todavía dentro de la $28$).

  después de $1 + 54$ ensayos, hemos establecido, no se $4$ dígitos a la derecha en $0-0-0-0-0-0$ adivinar. Ahora, elige un par de dígitos, por ejemplo, $d_1$ e $d_2$, y el cambio a $1-1$ (si el color cambia a ROJO - esos fueron los dígitos a la derecha, si a VERDE - hecho). En $3$ ensayos encontrará $2$ ceros a la derecha, en otras $3$ el otro par derecho. En $18$ ensayos usted puede encontrar el valor de faltan dos dígitos (de desactivar dos de la derecha, y se ejecuta desde $1$ a $9$ independiente)

  en el mismo espíritu puede establecer en $27$ ensayos, todos los dígitos, en caso de $3$.

  echa un vistazo, que la prueba inicial, se podría hacer el trillizos de dígitos [no creo que este caso de optimalidad].

• El más difícil es el caso de la luz ROJA en $0-0-0-0-0-0$ juicio.

  en $1000$ ensayos, tratando todos los trillizos de $d_1, d_2, d_3$, podemos establecer su verdadero valor, y desde ese punto de proceder como anteriormente [más $27$] - este es el límite superior en el número de ensayos

La cobertura de la idea

es tratar de números, como en el juego de niños [no tienen ni idea de su nombre en inglés]. Cada número de intentar y conseguir ROJA - que básicamente caída de los números, que de lo contrario daría usted AMARILLO o VERDE.

Ejemplo:

Después hemos intentado $0-0-0-0-0-0$, sabemos que $n$ podría no ser $0, 1, 2, 10, 11, 999$, etc. De hecho, cualquier primer intento de eliminar $15850$ posibilidades. Curiosamente, adivinando la próxima $1-1-1-1-1-1$ eliminará $15830$, etc. Mientras, yo aún tengo que establecer que existen en la mayoría de las $100$ conjeturas, que eventualmente resultar en una luz AMARILLA, creo que este número $100+27$ es el límite superior.

mi actual (probablemente, no-óptimo) lista de las primeras conjeturas que cubren aprox $400, 000$ números.

$000000$ cubre $15850$. Cubierta Total $15850$

$111111$ cubre $15830$. Cubierta Total $31680$

$222222$ cubre $15810$. Cubierta Total $47490$

$333333$ cubre $15790$. Cubierta Total $63280$

$444444$ cubre $15770$. Cubierta Total $79050$

$555555$ cubre $15750$. Cubierta Total $94800$

$666666$ cubre $15730$. Cubierta Total $110530$

$777777$ cubre $15710$. Cubierta Total $126240$

$888888$ cubre $15690$. Cubierta Total $141930$

$999999$ cubre $15670$. Cubierta Total $157600$

$012345$ cubre $14210$. Cubierta Total $171810$

$123456$ cubre $14190$. Cubierta Total $186000$

$234567$ cubre $14170$. Cubierta Total $200170$

$345678$ cubre $14150$. Cubierta Total $214320$

$456789$ cubre $14130$. Cubierta Total $228450$

$567890$ cubre $14110$. Cubierta Total $242560$

$678901$ cubre $14090$. Cubierta Total $256650$

$789012$ cubre $14070$. Cubierta Total $270720$

$890123$ cubre $14050$. Cubierta Total $284770$

$901234$ cubre $14030$. Cubierta Total $298800$

$021593$ cubre $12684$. Cubierta Total $311484$

$104328$ cubre $12664$. Cubierta Total $324148$

$210439$ cubre $12644$. Cubierta Total $336792$

$357964$ cubre $12624$. Cubierta Total $349416$

$432650$ cubre $12604$. Cubierta Total $362020$

$548716$ cubre $12584$. Cubierta Total $374604$

$796805$ cubre $12564$. Cubierta Total $387168$

Answer 2

Para la segunda parte $140$ pruebas son suficientes para establecer la combinación adecuada.

Comienza por establecer la secuencia correcta de las dos más a la derecha de los dígitos [esto requiere en la mayoría de las $100$ ensayos].

El de la 3ª a la derecha dígito de más a usted sólo necesita $10$ ensayos para cambiar la luz de rojo a amarillo.

Proceda de la misma manera con 3 dígitos restantes.

ACTUALIZACIÓN:

Deje que la combinación se $d_6d_5d_4d_3d_2d_1$

Puedes empezar con un $000000$ probar. Yo reclamo que el más difícil [decidir] resultado sería ninguna luz en absoluto después de la primera prueba. Luego nos pase por encima de todos los valores de $d_1$ de $1$ a $9$.

Hay dos posibles resultados:

• $\color{red}{\text{no light}}$ emitidos, es decir, ningún otro dígito es el conjunto! Este caso es manejado por mi respuesta inicial [de proceder para todas las opciones de $d_2d_1$ y después de exactamente $100$ ensayos [peor] se conocen los valores de $d_1$ e $d_2$, y que todos los otros dígitos no están establecidos. A continuación, para $9$ ensayos cada uno puede establecer los valores de los otros dígitos, es decir, por el color rojo de la luz en amarillo. Total: $\bf 136$ ensayos.
• $\color{red}{\text{red}}$ de la luz emitida [y nos detuvimos, el establecimiento $d_1$], es decir, exactamente un dígito entre el $d_2$ e $d_6$ es $0$. El cambio en cada una de las $d_2$ a $d_6$ una vez para establecer su valor como $0$ o el cambio de uno. En ese momento, después de más $5$ pruebas saber en menos de dos dígitos, y el no valor de otros $4$. El uso más $36$ ensayos como en la viñeta anterior para establecer el valor exacto de cada dígito. En total, en la mayoría, $\bf 51$ ensayos.

Otro primer juicio resultados, al igual que las luces emitidas es más fácil, en el sentido de que mediante la ejecución en la mayoría de las $3$ otros ensayos se puede reducir el problema a resolver arriba. Ejecutar ensayos en $111111$, $222222$ e $333333$, entonces al menos uno no va a producir luces en todo. Así, el límite superior de $140$ ensayos sostiene.

De hecho, la luz, en el primer juicio ayudará enormemente. Por ejemplo, supongamos que tienes una luz amarilla en $000000$ e $111111$. Por lo tanto, hay tres $0$'s y tres $1$'s en el número. Usted probar suerte en el $2222xx$ para $x \in \{0, 1\}$. Y en $4$ ensayos que he aprendido dos dígitos. En otro de los cuatro puede aprender próximo par, entonces usted necesita en la mayoría de los dos ensayos para establecer el número.

Answer 3

Yo creo que lo tengo ahora - voy a usar una versión más simple de semidiós de la estrategia. Si esto es incorrecto, por favor hágamelo saber!

Teniendo en cuenta una combinación de dígitos $d_6d_5d_4d_3d_2d_1$, nos centramos en $d_3d_2d_1$ hasta que el LED cambia de rojo a amarillo. El intermedio valor esperado es $$E_1 = \frac{10^3-1}{10^3}(E_1-x)+\frac1{10^3}(1000-x)$$ $$\Rightarrow E_1=10^3(1-x).$$

A continuación, vamos a continuar con $d_6d_5d_4$ hasta que el pecho se abre. Podemos imaginar que se trata de otro cofre con tres dígitos (combinación de la cerradura, con un premio de $\$E_1$ en el interior. El último valor esperado es $$E=E_1-10^3x=10^3-2\cdot 10^3x.$$

Para el positivo de la rentabilidad, exigimos que $$x<\frac{10^3}{2\cdot 10^3}.$$

Esto implica que el máximo que estamos dispuestos a pagar es \$0.50.

(Otro equivalente escenario es un cofre del tesoro con tres dígitos (combinación de la cerradura, con un premio de \$1000 inside, and a tariff of \$2x cada vez que cambio de un dígito.)

Answer 4

Esta respuesta se limita a la primera parte del problema, porque no parece haber un error en la OP del enfoque de allí.

El OP de respuesta, $x\lt1000/10^6$ es correcta sólo si hay un único intento de desbloquear el pecho, o si por "dispuesto a pagar" lo que quiere decir es "dispuesto a pagar sin riesgo alguno de perder dinero." Si "dispuesto a pagar", tiene su más significado típico de "dispuestos a correr el riesgo con el fin de obtener un positivo retorno esperado," y si tienes ilimitado de intentos (y si usted puede mantener un seguimiento de todos los intentos, por lo que no se trate de la misma combinación de dos veces), entonces la respuesta correcta es $x\lt2000/10^6$ (o $1000/500{,}000$).

Es decir, si usted explorar de forma sistemática todos los $10^6=1{,}000{,}000$ diferentes combinaciones sin repetición de sí mismo (lo cual es posible de hacer, mientras que el solo hecho de cambiar un dígito a la vez), que va a tomar, en promedio, $500{,}000$ intentos para encontrar la combinación que abre el pecho, por lo que el retorno esperado es $E=1000-500{,}000x$, y esto es positivo si $x\lt1000/500{,}000=\$0.002$ (es decir, dos décimas de centavo de dólar por cada intento).

Answer 5

(Sólo la segunda parte de la pregunta. La primera parte parece trivial)

Breve resumen: parece que un enfoque ingenuo puede encontrar la combinación en 200 intenta (en promedio).

Este problema puede ser considerado como una variante de la clásica "toros y vacas" del juego, con la restricción adicional de que una conjetura puede diferir por un sólo dígito de la anterior conjetura.

La estrategia óptima no es evidente, pero aquí es una observación y los resultados de las simulaciones por ordenador.

Observación 1: después de que el LED se ilumina de amarillo por primera vez, conoces a una posición determinada (el último ha cambiado), y usted puede conseguir las otras dos por el giro de los otros cinco posiciones una vez o dos veces. Si, después de cambiar un dígito, el LED permanece amarilla a mantener el cambio. Si sale rojo se conoce el número para que la posición y volver a cambiarlo. Después de determinar los 3 cambio de uno de ellos para activar el led rojo, y el uso de más del 30 intenta usted puede determinar los valores de los otros 3.

Cada vez que realice un cambio y el LED permanece de color rojo a ganar algo de información. Por ejemplo, si intenta 1,2,3,4,5,6 y obtener el rojo, 1,2,3,X,X,X no es posible, 1,2,X,4,X,X no es posible, etc. En la mayoría se eliminan $15850 = 20 \cdot 9^3 + 15 \cdot 9^2 + 6 \cdot 9 + 1$ (primer intento, por ejemplo), pero en general algunas combinaciones pueden ser las reglas ya, y en la práctica a eliminar 4.000 a 6.000 combinaciones en los primeros 50 se mueve más o menos.

Escribí el código que toma una adivinar por mantener un seguimiento de todos válidos resto de combinaciones, toma una posición en una combinación válida que es diferente a la de adivinar, y los cambios de adivinar para que coincida con este valor. Obviamente, esto no es óptimo, pero puede dar una idea acerca de los límites superiores. Parece que este método puede ajustar la combinación en alrededor de 200 mueve (en promedio).

El código no es rápido, así que me quede solo de 20 a 30 veces, pero creo que en algún lugar entre 150 y 250 (para el promedio) es razonable.

Encontrar una mejor estrategia parece muy interesante, pero no trivial.