La mejor estrategia para escoger una cerradura que se abre si al menos dos de sus tres dígitos decimales ruedas están marcados correctamente?

Question

Supongamos que usted desea abrir una cerradura con tres dígitos de código, el bloqueo es un poco especial, ya que se puede abrir si usted tiene dos dígitos acertó. Para aclarar, si es la correcta, de tres dígitos es 123, guess 124 o 153 puede abrir la caja. El bloqueo se parece a esto:

La pregunta es: ¿cuál es la mejor estrategia para abrir el cuadro? La mejor estrategia es una estrategia que requiere menos intentos en promedio. Usted también debe encontrar a la media.

Las estrategias que se me ocurrió:

Primera estrategia: mantener el primer dígito, y cambian constantemente de segundo y tercer mientras se mantenga igual al cambio de las mismas. Por ejemplo, voy a intentar: 111, 122...199,211,222,...,299,....

Segunda estrategia: mantener segunda y la tercera igual, y cambian constantemente primera. Por ejemplo: 111, 211,...,911,122,222,...

No sé si estos dos son los mejores, ni sé si son equivalentes eficiente.

Editar

He aquí un programa para calcular el número promedio de senderos para una estrategia de un ardiente comentario. Para usarlo, reemplace la línea '// Entrada de su lista de aquí' con la prueba de la lista y pulse ejecutar.

Answer 1

Tengo una estrategia, en la mayoría de las $50$ intenta e $22449/1000=22.449$ espera que intenta.

$$ \begin{align} 443, 796, 869, 101, 230, 577, 314, 022, 965, 656, \\ 588, 757, 875, 213, 140, 331, 689, 998, 404, 410, \\ 134, 303, 241, 886, 555, 667, 779, 421, 599, 000, \\ 432, 202, 897, 768, 044, 033, 695, 342, 011, 976, \\ 678, 959, 112, 858, 987, 224, 123, 320, 566, 785\phantom{,} \end{align} $$

Esta se obtuvo a partir de la desordenada conjunto de estas palabras (por una cubierta de código) y, a continuación, ordenar mediante un codicioso equipo de búsqueda; más detalles a continuación.

---

En primer lugar, voy a obtener algunas ideas, por considerar otro problema, la optimización del número de intentos necesarios para el peor de los casos, donde se conoce la solución para este caso. Un cubriendo código de $C$ con el alfabeto de tamaño de $q=10$, la longitud de la $n=3$, y cubriendo radio de $R=1$ es un conjunto de $3$-tuplas (llamadas palabras) de longitud $3$ $\{0,1,\dots,9\}$ de manera tal que cada posible $3$-tupla difiere de uno en $C$ en más de una posición. Esto es exactamente lo que necesitamos.

El tamaño mínimo con estos parámetros es $50$ [1]. Contiene estas palabras: $$ \begin{array}{|ccccc|} \hline 000 & 011 & 022 & 033 & 044 \\ 101 & 112 & 123 & 134 & 140 \\ 202 & 213 & 224 & 230 & 241 \\ 303 & 314 & 320 & 331 & 342 \\ 404 & 410 & 421 & 432 & 443 \\ \hline 555 & 566 & 577 & 588 & 599 \\ 656 & 667 & 678 & 689 & 695 \\ 757 & 768 & 779 & 785 & 796 \\ 858 & 869 & 875 & 886 & 897 \\ 959 & 965 & 976 & 987 & 998 \\ \hline \end{array} $$

Para cualquiera de las dos columnas, la mitad superior contiene una palabra para todos los $25$ pares de símbolos en $\{0,1,2,3,4\}$ que puede producirse, y la mitad inferior contiene todos los $25$ pares de símbolos en $\{5,6,7,8,9\}$ que puede ocurrir allí. La combinación correcta tiene que contener al menos dos símbolos de establecer, por lo que se abre al entrar a una de estas palabras.

[1] Algunas fuentes se refieren a "J. G. Kalbfleisch y R. G. Stanton, Una combinatoria teorema de igualación, J. Londres Matemáticas. Soc. (1), 44 (1969), 60-64; y (2), 1 (1969), 398", pero no puedo encontrar el papel. Sin embargo, el valor aparece en el cuarto PDF aparece en la parte superior de esta página por Gerzson Kéri.

---

Ahora, volviendo al problema original, la optimización de la previsión del número de intentos necesarios. Mi idea es tratar de tomar estas palabras y optimizar el fin de alguna manera. Por supuesto, esto no es garantía de que tenemos una solución óptima.

He intentado un codicioso método aleatorio: Elegir las palabras una por una. En cada paso, para cada uno de los posibles nuevos palabra $c$, encuentra el número que había descubierto las palabras que pudieran ser cubiertos por $c$. A continuación, entre los que cubren la mayoría, elegir uno al azar. Después de algún tiempo, la mejor que pude encontrar fue la orden dada en la parte superior de esta respuesta, con $22449/1000$ como el número esperado.

Answer 2

OK, así que la idea básica de la que tengo es la siguiente:

Queremos cubrir el mayor número posible de combinaciones posibles para cada intento. Así, por ejemplo, el OP de la estrategia de hacer 111,122,..., seguido por 211,222, ... parece menor que el óptimo, ya que los primeros 10 intentos, ya cubrir cualesquiera combinaciones con los dos últimos dígitos de ser el mismo. Por lo tanto, sería mejor hacer 111,122, ... seguido por algo como 223,234,245, de manera que no solo intenta conseguir un éxito entre el primer dígito y cualquiera de los otros dos, pero que también están tratando de otras opciones para obtener un éxito entre el 2 y 3 dígitos.

De hecho, incluso 111,122,... es menor que el óptimo, ya que tanto la cubierta 121, por lo que superponerse. Así, es probablemente lo mejor sea comenzar con algo como 111,222,333,... ya que cada uno de estos cubre 28 combinaciones sin solapamiento.

Después de eso, me imagino que se debería mantener asegurarse de que cada nuevo intento que hacemos tiene como unos dígitos en común con cualquiera de las combinaciones ya hemos intentado hasta ese punto... básicamente intentar hacer cada combinación difieren en 2 dígitos de cualquiera de las probado antes. La siguiente secuencia va a hacer exactamente eso (cada secuencia de 10 tiene una única diferencia entre el 1er y 2do dígito, entre la 2ª y la 3ª, y entre 1 y 3):

000, 111, 222, 333, ..., 999, (en este punto hemos cubierto 10*28=280 combinaciones)

012, 123, 234, 345, ..., 901, (otro 10 * 22 (por ejemplo, 012 cubre y 3*7) = 220)

(así que con tan solo 20 intenta cubrimos la mitad de todas las combinaciones posibles!)

024, 135, 246, 357, ..., 913, (otro 10 * 18 (esto toma algo de la escritura) = 180)

036, 147, 258, 369, ..., 925, (otro 10 * 12 = 120)

048, 159, 260, 371, ..., 937, (otro 10 * 8 = 80)

(en este punto, no siga con 050,... ya que tiene dos dígitos en común con las anteriores 000)

051, 162, 273, 384, ..., 940, (otro 10 * 5 = 50)

063, 174, 285, 396, ..., 952, (otro 10 * 4 = 40)

075, 186, 297, 308, ..., 964, (otro 10 * 2 = 20)

087, 198, 209, 310, ... ,976 (el pasado 10)

En una versión anterior de mi respuesta me dijo que hacer otros 10 después de estos:

099, 100, 211, 322, ... , 988

la idea de que esto iba a cubrir todos los posibles pares de 1er y 2do dígito, y cubriendo así todas las combinaciones posibles (y así, podemos tener un peor caso de 100). Sin embargo, resulta que cualquiera de ellos estos adicional de 10 cubriría se han cubierto ya por el anterior 90. Así, en el peor caso de este método es de 90 trata, no de 100.

El método anterior da un promedio de 0,28*5.5 (los primeros 10 intentos, cada cubierta de 28 casos, por lo que es de 280 casos por 1000 es de 28%, que en promedio toma (1 + 10)/2 = 5.5 intenta) + 0.22*15.5 + 0.18*25.5 + 0.12*35.5 + 0.08*45.5 + 0.05*55.5 + 0.04*65.5 + 0.02*75.5 + 0.01*85.5 = 25.2 intenta abrir la caja.

Realmente creo que este método no puede ser mejorado en términos de promedio de número de intentos, pero no tengo ninguna prueba.

Edit ok, así que esto es no es la estrategia más eficiente: ver JiK la respuesta! Tiempo para comer humildes! ... Bueno, espero que al menos fue capaz de expresar algunas de las ideas de por qué algunas estrategias pueden ser mejores que otros.

Answer 3

Este es un problema con la entropía, en cada intento desea máximo lowerize la entropía.

Ya me olvidé de las fórmulas para la entropía voy a ir por este camino... Maximizar la probabilidad de desbloquear en cada intento.(es un poco lo mismo)

Vamos a n ser el fin de la prueba y p(n) probabilidad de desbloquear y, a continuación:

$p(1)=\frac{3*9+1}{1000}=\frac{28}{1000}$

Después de la primera prueba discrimina 28 de combinaciones, por lo que si usted no pudo con 111, usted también sabe que 112,113,...,121,... no son la combinación

Vamos a intentar su segunda estrategia para el próximo intento, si usted escoge 211, que se discriminan otro de 18 combinaciones (212,213,...210,221,231,...230 pero las combinaciones 311,411... ya discriminados, por lo que p(2) con la 2ª estrategia es $p(2)=\frac{18}{972}$

Vamos a tratar 1ª estrategia, de modo que la segunda elegir para ser 122, de esta manera se discrimina otro 26 combinaciones de cos 121 y 112 ya estaban disco.

Así que me decidiría por la estrategia de cambio de todos tres dígitos, para discriminar otro 28 combinaciones, por lo $p(2)=\frac{28}{972}$

Eso es lo que haría usted para los primeros 10 intentos, y para el resto... intente por su cuenta :)

Answer 4

Así, lo que si se reduce la cuestión a sólo 3 números posibles permitido para cada dígito?

De $000$ $222$

En ese caso, usted puede cubrir cualquiera de los 27 permutaciones con tan sólo 6 conjeturas $$000$$ $$111$$ $$222$$ $$010$$ $$020$$ $$101$$

Así que el 6 de conjeturas para obtener $3^3$. No estoy seguro de cómo esto podría generalizar, aunque.

Es $n^2\frac{n-1}{n}=n(n-1)$ de los que serían 90 en su problema? (Esta generalización también funciona para la cerca-ejemplo trivial de sólo 2 números 0 y 1, en cuyo caso, 000 y 111 cubre cualquier permutación)

Además, este método está tratando de minimizar el peor de los casos, un exhaustivo método, no el promedio de número de intentos.

Edit: Confirmado $n(n-1)$ también cubre todas las opciones en base 4 (de 000 a 333).

000, 111, 222, 333,

012, 013, 021,

102, 103, 120,

210,

301

Y de lo que deduzco de la fuerza bruta de los métodos, en tu pregunta original, el ciclismo a través de la 000, 111, 222, 333....999 se llevará a cabo el 28 de permutaciones de cada uno, para 280. Después de eso, usted será capaz de hacer 80 conjeturas que se llevará a cabo el 9 de permutaciones de cada uno, para un total de 90 conjeturas que cubren todos los 1000 permutaciones.

También, después del 29 de conjeturas, ha llevado a cabo más de 500 de las permutaciones.

Answer 5

1) 000: Reglas más de 1 cero

2-4) 011;101;110: Normas de uno y cero y más de un 1

25-28) 022;202;220;....099;909;990: las Normas de 0 y más de 1 de cada número.

29-34) 123,213,231,132,312,321: Reglas de dos de 1,2,3

35-52)145...167...189: Reglas de cualquier 1s; y cualquier par de (4,5)(6,7),(89)

53-58)246....642: las Normas de 2s con 4or 6 y cualquier par de 4 o 6.

59-64) 257....752: las Normas de 2s con 5 o 7; tan sólo 2 con 8 o 9 son de la izquierda. Pero el 8 y el 9 no puede par así que esto es imposible, así que, las normas de 2s.

65 - 70)347...743: Normas 3s con nada menos que el 5s.

71-76) 356..653: Normas 3s con otra cosa que el 8 y el 9, que es imposible, así que las reglas de 3.

4s sólo son posibles con 8 y 9, así que eso es imposible.

6s sólo son posibles con 8 y 9. 7 sólo es posible con 8 o 9.

Por lo que cualquier combinación que nos hubiera adivinado en 76 conjeturas.

No estoy seguro de cómo generalizar.