11. (GDR 3) The lock on a safe consists of three wheels, each of which may be set in eight different positions. Due to a defect in the safe mechanism the door will open if any two of the three wheels are in the correct position. What is the smallest number of combinations that must be tried if one is to guarantee being able to open the safe (assuming that the "right combination" is not known)?
11. The answer is 32 . Write the combinations as triples $k=(x, y, z), 0 \leq$ $x, y, z \leq 7$. Define the sets $K_{1}=\{(1,0,0),(0,1,0),(0,0,1),(1,1,1)\}$. $K_{2}=\{(2,0,0),(0,2,0),(0,0,2),(2,2,2)\}, K_{3}=\{(0,0,0),(4,4,4)\}$, and $K=\left\{k=k_{1}+k_{2}+k_{3} \mid k_{i} \in K_{i}, i=1,2,3\right\}$. There are 32 combinations in $K$. We shall prove that these combinations will open the safe in every case.
Let $t=(a, b, c)$ be the right combination. Set $k_{3}=(0,0,0)$ if at least two of $a, b, c$ are less than 4 , and $k_{3}=(4,4,4)$ otherwise. In either case, the difference $t-k$ contains two nonnegative elements not greater than 3. Choosing a suitable $k_{2}$ we can achieve that $t-k_{3}-k_{2}$ contains two elements that are 0,1 . So, there exists $k_{1}$ such that $t-k_{3}-k_{2}-k_{1}=t-k$. contains two zeros, for $k \in K$. This proves that 32 is sufficient.
Suppose that $K$ is a set of at most 31 combinations. We say that $k \in K$ covers the combination $k_{1}$ if $k$ and $k_{1}$ differ in at most one position. One of the eight sets $M_{i}=\{(i, y, z) \mid 0 \leq y, z \leq 7\}, i=0,1, \ldots, 7$, contains at most three elements of $K$. Suppose w.l.o.g. that this is $M_{0}$. Further, among the eight sets $N_{j}=\{(0, j, z) \mid 0 \leq z \leq 7\}, j=0, \ldots, 7$, there are at least five, say w.l.o.g. $N_{0}, \ldots, N_{4}$, not containing any of the combinations from $K$.
Of the 40 elements of the set $N=\{(0, y, z) \mid 0 \leq y \leq 4,0 \leq z \leq 7\}$, at most $5 \cdot 3=15$ are covered by $K \cap M_{0}$, and at least 25 aren't. Consequently, the intersection of $K$ with $L=\{(x, y, z) \mid 1 \leq x \leq 7,0 \leq y \leq 4,0 \leq z \leq 7\}$ contains at least 25 elements. So $K$ has at most $31-25=6$ elements in the set $P=\{(x, y, z) \mid 0 \leq x \leq 7,5 \leq y \leq 7,0 \leq z \leq 7\}$. This implies that for some $j \in\{5,6,7\}$, say w.lo.g. $j=7, K$ contains at most two elements in $Q_{j}=\{(x, y, z) \mid 0 \leq x, z \leq 7, y=j\}$; denote them by $l_{1}, l_{2}$. Of the 64 elements of $Q_{7}$, at most 30 are covered by $l_{1}$ and $l_{2}$. But then there remain 34 uncovered elements, which must be covered by different elements of $K>Q_{7}$, having itself less at most 29 elements. Contradiction.