"Mastermind"-esque seguro de apertura problema.

Question

He leído esta pregunta de la entrevista para un trading de trabajo y me parece muy difícil. ¿Cuál es la técnica para resolverlo?

Usted tiene una caja fuerte con seis dígitos y una luz. Usted puede introducir un código, si tiene entre 0 y 3 de los 6 dígitos correcto, la luz se pondrá rojo. Si tienes entre 4 y 5 de los 6 dígitos correctos, que a su vez amarillo y si tiene todos los 6 dígitos correcto, se abrirá. Hay $10, 000 dentro de la caja fuerte, usted puede adivinar el código tantas veces como usted quiere, pero necesita pagar cada vez que adivinar, ¿cuánto estaría usted dispuesto a pagar por cada adivinar?

Gracias

Answer 1

No es muy claro en la pregunta, pero esto es lo que he leído: La luz ilumina cuando el número de la derecha(s) están en el lugar correcto, es decir, la permutación debe ser el correcto, y no sólo de la combinación.

Digamos, por ejemplo, que están dispuestos a pagar, en la mayoría de los 5000$as total fees for guessing. So, if you cracked the code in 1000 guess, that's 5$ una conjetura. Pero, si usted tomó 10000 conjeturas, que es de 0,5\$ a adivinar. Por lo tanto, el objetivo es ser capaz de romper la caja fuerte en el menor tiempo posible en conjeturas.

El seguro puede aceptar cualquiera de las $10^6$ permutaciones. El simple método de la fuerza bruta implicaría la ejecución a través de ese conjunto y con la esperanza de que se encuentra una solución. Pero, que deja las cosas al azar y es posible que uno tiene que ejecutar a través de todos los $10^6$ opciones.

Desde la caja de seguridad-código de la necesidad de no poseer ningún patrón, sólo tenemos la iluminación para ayudar con nuestras adivinanzas. Un límite máximo en el número de conjeturas pueden ser establecidas por el método. El número real de conjeturas ($N_g$) será menor o igual a él. Inicialmente, la caja fuerte se lee $$x_0 = [x(1),x(2),\ldots x(6)]$$ and let us assume only the red light is lit (for anywhere between $0$ to $4$ correct numbers). For convenience, let this number be $000000$, pero podría ser cualquier cosa.

1. Ejecute$x(1),x(2),x(3),x(4)$$0001$$9999$. En algún momento, la luz cambiará de rojo a amarillo. Por lo tanto $\textsf{max} \; N_g = 9999$.
2. Restablecer $x(4)$ $0$(que se encienda la luz de vuelta a rojo) y ejecute$x(5)$$1$$9$. En algún momento, la luz se vuelve amarillo de nuevo. Por lo tanto $\textsf{max} \; N_g = 9999 + 9$.
3. Ahora, establezca $x(4)$ $x(5)$ a los valores correctos y ejecute$x(6)$$1$$9$. La caja fuerte se abre en algún momento. Por lo tanto $\textsf{max} \; N_g = 9999 + 9 + 9 = 10017$.

Este es el número máximo de adivina usted tendrá que ir a través de descifrar el código. Establecer ahora una adivinanza tarifa basada en la cantidad total que están dispuestos a gastar.

Answer 2

Supongamos una base de $10$ número de sistema. A continuación, podemos conseguir que la luz amarilla en la mayoría de los $10^4 = 10, 000$ pasos por la simple fuerza bruta de la primera $4$ dígitos. Si la caja se desbloquea, entonces hemos terminado. De lo contrario, hay o $4$ o $5$ dígitos correctos. A continuación, cambiamos exactamente un dígito a la vez, para todos los $6$ dígitos. Si la luz permanece amarilla para cada uno supongo, entonces sabemos que hay $5$ dígitos correctos. De lo contrario, no se $4$ dígitos. Vamos a hacer el caso para $5$ primer:

• Caso de $5$: queremos saber qué dígito es no correcto. Podemos encontrar esto en $6$ más gueses. Lo que hacemos es cambiar los dígitos $1$$2$, $1$ $3$ etc. Si la luz permanece amarilla para cada supongo que, luego de dos dígitos$1$, más el dígito para que los cambios de luz. En cualquier caso, podemos resolver todo el asunto en otro $9$ conjeturas máximo.Así que el total de conjeturas aquí es en la mayoría de las $10,000 + 6 + 6 + 9$.
• Caso de $4$: En este caso, recordamos la $4$ dígitos para que la luz cambia de color cuando hemos cambiado antes. Estos son los correctos. Así que los otros dos debe ser cambiado. Hay $99$ más de combinaciones a probar, de modo que obtenemos un total máximo de $10,000 + 6 + 99$. Este es el peor caso posible.

Así, con este enfoque, se necesitarían en el peor de los casos $10,000 + 6 + 99$. Suponiendo que un conservador jugador que quiere un beneficio, la cantidad que estaría dispuesto a pagar menos de un dólar por adivinar.

Answer 3

Mi enfoque es un nuevo método que utiliza la Cadena de Markov del proceso. Esencialmente, este pin-agrietamiento problema es muy similar a la de Mastermind con k colores y n posiciones. En este problema, hay seis posiciones de la creación de seis dígitos de la secuencia. Cualquier secuencia que representa a los seis dígitos de código es elegido a partir de (0-9) diez dígitos y todos son igualmente probables. Sin embargo, sólo hay dos luces,a saber, el rojo y el amarillo vez en cuando (0-3) dígitos coinciden con el código secreto por dígitos y posición.

Voy a explorar este problema, incluso, más generalmente, por la relajación de los dos colores a seis colores y que para cada conjunto de dígitos que corresponden a un conjunto correspondiente en el código secreto por el número y la posición, la luz adecuada se va a encender. Las luces brillantes para diferente número de respuestas correctas es similar a la del codificador dar pistas en un juego de Mastermind. En última instancia, la luz que corresponde a seis dígitos son correctos, es el estado deseado.

El resto de las respuestas correctas tendrán las respectivas luces de la señal de su corrección. Por lo tanto, hay siete estados. Usted podría no tener una luz de brillo de 0 correcto de dígitos, una luz de 1 dígito correcto, otra luz para 2 correcto de dígitos y de ahora en adelante una luz para la correcta 6 dígitos. En el inicio del juego, el codebreaker presenta una secuencia de 6 dígitos. Él podría llegar a cualquier lugar de 0 a 6, siendo la correcta. Las luces (encoder) será señal de que el número correcto de dígitos en el número y posición. En cualquiera de las conjeturas, si el codebreaker grietas de 1 dígito, el juego se reduce a codebreaker adivinar los otros dígitos mediante la presentación de secuencias de 5. Esto imita una Cadena de Markov proceso con siete estados y la probabilidad de movimiento de un estado a otro se da en el diagrama de abajo. Todos los estados son transitorios, excepto el último estado 6, que es absorbente y el juego llega a su fin.

En este problema, se supone que para encontrar el número esperado de conjeturas.

El costo de la apuesta podría ser visto como el costo de transacción "c". Por lo tanto el promedio de la máxima rentabilidad $= 10000-23.75349\times c$

Entrar en Jane Street, y desearos mucha suerte.

Gracias

Satish