# Shasha's safecracking problem

Suppose you want to open a safe with 10 switches. For each switch there're 3 settings, say, 1,2,3. There're 2 key switches. The safe is unlocked once you set the key pair correctly, but you can't distingush the key ones from the others. The question is, how many tries do you need to be sure to open the safe, and how should you choose the combinations (an althorithm)? (For example, if the safe has only 2 switches instead of 10, you need $3\times3=9$ tries) Will the number of tries grow less than linearly as the number of switches increases? Could there be a formula for a general problem of $n$ switches, $m$ settings and $k$ keys?

-
Curiously, you only need 9 tries even if there are 4 switches (0000, 0111, 0222, 1012, 1120, 1201, 2021, 2102, 2210), but you need more if there are 5 (or more) switches. –  Gerry Myerson Sep 4 '12 at 2:54
Gerry's 9 tries form a code in which the next codeword is the first which differs from each of the previous codewords in exactly three places. –  Mark Bennet Sep 4 '12 at 3:59

What you seek is a covering array (ref.), denoted CA(t,k,v), with parameters:

• strength t=2
• number of columns k=10
• number of possible values v=3

The smallest such covering array is listed here as having 14 rows (i.e. trials), having been found by simulated annealing by Cohen.

Jose Torres-Jimenez's webpage has an applet which can give you an example:

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


Finding the minimum for general $t,k,v$ (known as the covering array number) is a hot research topic, one of the most prominent researchers is Prof. Charlie Colbourn.

-

Suppose the number of switches is $N = 2^n$. Here is a construction using $6n+3$ settings. First, we take the three constant settings $0^N,1^N,2^N$. Next, for any two different values $a,b \in \{0,1,2\}$ and $i \in \{0,\ldots,n-1\}$, we have the setting such that switch $k$ gets value $a$ or $b$ depending on the value of the $i$th bit of $k$. Now suppose $s,t$ are the two correct switches, and their correct settings are $a,b$. If $a = b$ then one of the constant settings unlocks the safe. Otherwise, suppose $s$ and $t$ differ on bit $i$. Then either the setting $(a,b,i)$ or the setting $(b,a,i)$ unlocks the safe.

Here is an example with $n = 2$, which is admittedly inferior to Gerry's solution: \begin{align*} & 0000 && 1111 && 2222 \\ 0011 && 1100 && 0101 && 1010 \\ 0022 && 2200 && 0202 && 2020 \\ 1122 && 2211 && 1212 && 2121 \end{align*}

On the other hand, suppose $\{s_1,\ldots,s_n\}$ is a set of settings of $N$ switches such that for all pairs $i,j \in [N]$, there is a setting in which switch $i$ is set to $0$ and switch $j$ is set to $1$. Then $N \geq 2^n$. This shows that our construction is optimal up to a multiplicative constant.

For the proof, we define a sequence $S_0 = [N] \supset S_2 \supset \cdots \supset S_n$ such that $\{s_{i+1},\ldots,s_n\}$ is a solution for $S_i$. Given $S_i$, consider the setting $s_{i+1}$ restricted to $S_i$. There are either at most $|S_i|/2$ switches set to $0$ or at most $|S_i|/2$ switches set to $1$. Without loss of generality, suppose that there are at most $|S_i|/2$ switches set to $0$, and let $S_{i+1}$ consist of those switches not set to $0$. The setting $s_{i+1}$ is not helpful for pairs of switches from $S_{i+1}$ (since these are all set to $1$ or $2$), hence $\{s_{i+1},\ldots,s_n\}$ must be a solution for $S_{i+1}$. Note that $|S_{i+1}| \geq |S_i|/2$, hence $|S_n| \geq N/2^n$. On the other hand, clearly $|S_n| \leq 1$. We conclude that $N \geq 2^n$.

-