Shasha del safecracking problema

Question

Supongamos que usted desea abrir una caja fuerte con 10 interruptores. Para cada interruptor hay 3 opciones, digamos, 1,2,3. Hay 2 interruptores de llave. El seguro se desbloquea una vez establecido el par de claves correctamente, pero no se puede distingush la clave de los otros. La pregunta es, ¿cuántos intenta hacer que usted necesita para asegurarse de que abriera la caja fuerte, y ¿cómo se debe elegir las combinaciones (un althorithm)? (Por ejemplo, si la caja tiene sólo 2 interruptores en lugar de 10, usted necesita $3\times3=9$ intenta) el número de intentos a crecer menos que linealmente a medida que el número de interruptores aumenta? Podría ser una fórmula para un problema general de la $n$ interruptores, $m$ $k$ llaves?

Answer 1

Lo que buscan es un cubrimiento de la matriz (ref.), denota CA(t,k,v), con los parámetros:

• la fuerza t=2
• número de columnas de k=10
• el número de posibles valores de v=3

El más pequeño tal cubrimiento de la matriz aparece aquí como tener 14 filas (es decir, ensayos), después de haber sido encontrado por el recocido simulado por Cohen.

Jose Torres-Jiménez página web tiene un applet que puede dar un ejemplo:

C SA-JTJ
14 10 3^10 2
0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
2 2 2 1 1 0 2 2 2 2
1 1 2 0 2 2 0 1 2 0
1 0 0 2 0 1 2 2 1 1
0 1 0 1 2 2 1 2 0 0
0 2 1 2 0 2 1 0 2 1
0 2 0 0 1 1 2 1 0 0
0 1 2 2 0 0 1 1 1 2
2 0 2 1 0 1 0 0 0 1
1 0 1 2 1 2 0 0 0 2
2 0 0 0 2 1 1 1 2 2
1 2 1 0 2 0 0 2 1 1
2 1 1 2 2 2 2 0 1 0

Encontrar el mínimo para general $t,k,v$ (conocida como el que cubre número de matriz) es un tema de investigación, uno de los más destacados investigadores es el Prof. Charlie Colbourn.

Answer 2

Supongamos que el número de interruptores es $N = 2^n$. Aquí es una construcción con $6n+3$ configuración. En primer lugar, tomamos los tres constante de configuración de $0^N,1^N,2^N$. Siguiente, para dos diferentes valores de $a,b \in \{0,1,2\}$$i \in \{0,\ldots,n-1\}$, tenemos la configuración tal que el interruptor de la $k$ obtiene el valor de $a$ o $b$ dependiendo del valor de la $i$th bits de $k$. Ahora supongamos $s,t$, son los dos corregir los interruptores, y su correcta configuración se $a,b$. Si $a = b$, a continuación, una de las constantes de configuración abre la caja fuerte. De lo contrario, supongamos $s$ $t$ difieren en poco $i$. A continuación, el ajuste de $(a,b,i)$ o $(b,a,i)$ desbloquea la caja fuerte.

Aquí está un ejemplo con $n = 2$, que es sin duda inferior a la de Gerry de la solución: $$ \begin{align*} & 0000 && 1111 && 2222 \\ 0011 && 1100 && 0101 && 1010 \\ 0022 && 2200 && 0202 && 2020 \\ 1122 && 2211 && 1212 && 2121 \end{align*} $$

Por otro lado, supongamos $\{s_1,\ldots,s_n\}$ es un conjunto de ajustes de $N$ interruptores tal que para todos los pares de $i,j \in [N]$, hay un escenario en el que el interruptor de $i$ $0$ y el interruptor de $j$$1$. A continuación,$N \geq 2^n$. Esto demuestra que nuestra construcción es óptima hasta un multiplicativo constante.

Para la prueba, se define una secuencia $S_0 = [N] \supset S_2 \supset \cdots \supset S_n$ tal que $\{s_{i+1},\ldots,s_n\}$ es una solución para $S_i$. Dado $S_i$, considerar el establecimiento $s_{i+1}$ restringido a $S_i$. Hay en la mayoría de los $|S_i|/2$ conjunto de modificadores a $0$ o $|S_i|/2$ conjunto de modificadores a $1$. Sin pérdida de generalidad, supongamos que existen en la mayoría de las $|S_i|/2$ conjunto de modificadores a $0$, y deje $S_{i+1}$ consta de los interruptores no se establece a $0$. El establecimiento $s_{i+1}$ no es útil para los pares de interruptores de $S_{i+1}$ (ya que estos se ajustan a $1$ o $2$), por lo tanto $\{s_{i+1},\ldots,s_n\}$ debe ser una solución para $S_{i+1}$. Tenga en cuenta que $|S_{i+1}| \geq |S_i|/2$, por lo tanto $|S_n| \geq N/2^n$. Por otro lado, claramente $|S_n| \leq 1$. Llegamos a la conclusión de que $N \geq 2^n$.