Número mínimo de intentos para adivinar un código PIN, dadas las restricciones

Question

Estoy jugando un juego de video por el momento se llama Sleeping Dogs, en el que algunos de los mini-misiones son para 'hackear' una cámara de seguridad, por adivinar un código PIN de cuatro dígitos.

Aquí están las reglas:

1) se Le permite 6 intentos para introducir un código PIN de cuatro dígitos. Después de 6 intentos, el código PIN se reinicia al azar a una (otra).

2) dígitos Repetidos no están permitidos (por ejemplo, $9981, 1131, 5555,$ etc. no están permitidos).

3) Si el dígito correcto está en el lugar correcto, el dígito será verde.

Si el dígito correcto (es decir, un dígito que aparece en el PIN) es incorrecta lugar, el dígito será de color ámbar.

Si un dígito incorrecto, es introducida (es decir, un dígito que es no en el real PIN), el dígito será de color rojo.

por ejemplo, Supongamos que el código real es de $\boxed{1234}.$

Si entré a $1427$, sería una muestra de como

$$\color{green}1\color{orange}4\color{orange}2\color{red}7.$$

Mi pregunta es la siguiente:

¿Cuál es el mínimo número de intentos con el fin de garantizar la entrada al sistema, (puede ser logrado con certeza, en menos de seis intentos)?

Parece ser que hay muchos factores que no puede venir para arriba con una solución rápida. Consejos/sugerencias serán bienvenidas.

---

(Información de fondo-estoy familiarizado con los elementales de la probabilidad y de la estadística).

Answer 1

Una vez que sepa los números correctos, le llevará más de 3 conjeturas más para encontrar sus posiciones (ya que cualquier número en una posición incorrecta se puede corregir en 3 conjeturas como máximo).

También puedes encontrar los cuatro números correctos adivinando 1234; 5678; 9012.

Por lo tanto, este algoritmo quizás no sea el más eficiente, pero siempre da la respuesta dentro de 6 intentos.

Answer 2

A continuación algoritmo garantiza que no importa que el código dado, se puede hackear la cámara de seguridad de un máximo de 5 movimientos:

Se requiere algo de planificación inteligente y, aproximadamente, como sigue:

1. Comprueba tu conjetura. Si la solución de parada, de lo contrario continúe.
2. Si no son de color ámbar (fuera de lugar) dígitos, a continuación, tratar de encontrar (si es posible) precisamente estos dígitos lugares en secuencia. Por ejemplo, si el dígito en el 4º lugar es de color ámbar, y a esta cifra ya fue tratado en el 1er y 3er lugar (o tal vez sabemos dígitos en 3er lugar), entonces sabemos precisamente que su lugar es 2º en la secuencia. Compruebe si tiene solución. Si no, intente #2 otra vez hasta que usted los encontró a todos los posibles dígitos que sólo puede llegar a un lugar. Si no hay ambers ir a la #4.
3. Pruebe estos ámbar dígitos en el nuevo (que previamente no tratado).
4. Inténtelo de nuevo (que previamente no tratado) dígitos en los lugares vacíos. A continuación, vaya al #1 de nuevo.

Hay algunas sutilezas en este algoritmo, el cual he señalado en la final.

Aquí están algunos ejemplos:

• Código: $6435$. $$\color{red}{012}\color{orange}{3}\\ \color{orange}{3}\color{verde}{4}\color{orange}{56}$$ Ahora, el dígito 3, fue juzgado en el 1er y 4to lugar, también sabemos que el dígito en el 2do lugar es de 4. Por lo tanto, el dígito 3 pertenece a la 3ª plaza. Y sabemos que los dígitos en el 2do y 3er lugar se $43$, por lo tanto dígito 6 pertenece al 1er lugar. Sólo hay un lugar a la izquierda en los dígitos 5 y es el 4to lugar. $$\color{green}{6435}$$ Que en repetidas ocasiones el uso de #2, para encontrar una solución.
• Código: $9123$. $$\color{red}{0}\color{green}{123}$$ No hay ambers así que trate de nuevos dígitos. $$\color{red}{4567}\\ \color{red}{8}\color{orange}{9}**$$ No importa qué dígito intenta en 3º y 4º lugares. Ahora aplica el #2 de nuevo para obtener: $$\color{green}{9123}$$
• Aparentemente, uno de los peor de los escenarios es el código (Siempre, si empezamos con los $1234$): $8790$ $$\color{red}{1234}\\\color{red}{56}\color{orange}{78}$$ A partir de este punto, podemos encontrar en tercer y cuarto lugar en el plazo máximo de tres intentos. También podemos encontrar la posición de los dígitos 7 y 8, en el plazo máximo de tres intentos. Con el fin de obtener la mayor información de los dígitos 9 y 0, se debe colocar 87 tercer y cuarto lugar*, por lo tanto, si 0 y 9 pertenecen a tercero y cuarto lugar (el peor caso), podemos encontrarlos en dos intentos. $$\color{orange}{0987}$$ Ahora sabemos que los dígitos 7 y 8 pertenecen al primer y segundo lugar, así dígitos 0 y 9 pertenecen a tercero y cuarto lugar. Por lo tanto, es tomar un máximo de dos intentos para encontrar el código: $$\color{orange}{7809}\\ \color{verde}{8790}$$

*No es una sutileza. No podemos dígitos al azar y probar suerte. Por ejemplo, si se administra en el código sería el $9087$, y tratamos: $$\color{red}{1234}\\ \color{red}{56}\color{orange}{78}\\ \color{orange}{7809}\\ \color{orange}{8790}\\ \color{orange}{09}\color{verde}{87}$$ Entonces no podemos obtener el resultado en cinco intentos. En orden a la negligencia de esto, podemos decir; "Si puedes adivinar dos de color rojo y dos de color ámbar dígitos, a continuación, permuta estos ámbar dígitos lugares si es posible." para el algoritmo.

Answer 3

Las limitaciones que se dan seis intentos, así que mientras que el siguiente algoritmo puede no producir la respuesta en tan sólo cinco intentos, todavía está garantizado para darle en no más de seis. (Hasta ahora sólo pude encontrar dos ejemplos de códigos que requieran de seis intentos, y creo que estas podrían ser sólo dos).

---

Para cada uno de los dígitos que definen su estatus como $u,r,a,g$ significado no ha sido probado, rojo, ámbar y verde. Inicialmente todos tienen la condición de $u$.

1. De entrada de $0123$.
2. Si los cuatro dígitos de estado de $g$ hemos terminado.
3. Eliminar los dígitos marcados como $r$, y añadir al menos dígitos marcados con $u$.

4. Reordenar los cuatro dígitos que usted tiene al menos el valor numérico tal que las dos restricciones siguientes:se

   • Ningún dígito marcado $a$ está en un lugar previamente localizados.
   • Cada dígito marcado $g$ permanece en su lugar desde la última vez.
5. De entrada el número, y repetir.

¿Por qué son seis mueve lo suficiente? Una vez que un dígito aparece ha estado $a$ va a tomar en la mayoría de los más de tres intentos para colocar en su lugar correcto (ya que sólo hay tres lugares para que se vaya). Lo que significa que por el quinto paso que han realizado al menos dos dígitos correctamente. Sólo tenemos una opción para continuar y supongo que, para cambiar las dos marcada $a$.

Hasta ahora todos los códigos que he tratado de adivinar con la excepción de $9876$ $8976$ se divide en cinco intentos, debido a que por la segunda adivinar el algoritmo garantizados para estar "cerca" de una solución. Aquí están algunos ejemplos:

$$\begin{array}{c|c|c|c} \begin{array}{c|c} \text{Code:}&1980\\\hline 0123&aarr\\ 1045&garr\\ 1607&grar\\ 1890&gaag\\ 1980&gggg \end{array} & \begin{array}{c|c} \text{Code:}&6837\\\hline 0123&rrra\\ 3456&arra\\ 6378&gaaa\\ 6837&gggg\\ \vphantom{1} \end{array} & \begin{array}{c|c} \text{Code:}&3672\\\hline 0123&rraa\\ 2345&aarr\\ 3267&gaaa\\ 3672&gggg\\ \vphantom{1} \end{array} & \begin{array}{c|c} \text{Code:}&6581\\\hline 0123&rarr\\ 1456&araa\\ 5617&aaar\\ 6581&gggg\\ \vphantom{0} \end{array} \end{array}$$

En última instancia, este algoritmo es bastante simple, y lo suficientemente rápido, como para merecer una revisión completa, la ejecución de todos los códigos posibles en contra de ella. Pero yo soy demasiado perezoso para escribir este código. Si alguien quiere, por favor, publicar los resultados en un comentario/separado respuesta!