IMO 1988 SL 11

Origin: GDR

Problem

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)?

Solution

The answer is 32. Write the combinations as triples k = (x, y, z), 0 \leq x, y, z \leq7. Define the sets K1 = {(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 1)}, K2 = {(2, 0, 0), (0, 2, 0), (0, 0, 2), (2, 2, 2)}, K3 = {(0, 0, 0), (4, 4, 4)}, and K = {k = k1 + k2 + k3 | ki \inKi, i = 1, 2, 3}. 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 k3 = (0, 0, 0) if at least two of a, b, c are less than 4, and k3 = (4, 4, 4) otherwise. In either case, the difference t −k3 contains two nonnegative elements not greater than 3. Choosing a suitable k2 we can achieve that t −k3 −k2 contains two elements that are 0, 1. So, there exists k1 such that t−k3 −k2 −k1 = t−k contains two zeros, for k \inK. This proves that 32 is sufficient. Suppose that K is a set of at most 31 combinations. We say that k \inK covers the combination k1 if k and k1 differ in at most one position. One of the eight sets Mi = {(i, y, z) | 0 \leqy, z \leq7}, i = 0, 1, . . . , 7, contains at most three elements of K. Suppose w.l.o.g. that this is M0. Further, among the eight sets Nj = {(0, j, z) | 0 \leqz \leq7}, j = 0, . . . , 7, there are at least five, say w.l.o.g. N0, . . . , N4, not containing any of the combinations from K. Of the 40 elements of the set N = {(0, y, z) | 0 \leqy \leq4, 0 \leqz \leq7}, at most 5\cdot3 = 15 are covered by K\capM0, and at least 25 aren’t. Consequently, the intersection of K with L = {(x, y, z) | 1 \leqx \leq7, 0 \leqy \leq4, 0 \leqz \leq7} contains at least 25 elements. So K has at most 31 −25 = 6 elements in the set P = {(x, y, z) | 0 \leqx \leq7, 5 \leqy \leq7, 0 \leqz \leq7}. This implies that for some j \in{5, 6, 7}, say w.l.o.g. j = 7, K contains at most two elements in Qj = {(x, y, z) | 0 \leqx, z \leq7, y = j}; denote them by l1, l2. Of the 64 elements of Q7, at most 30 are covered by l1 and l2. But then there remain 34 uncovered elements, which must be covered by different elements of K ∖Q7, having itself less at most 29 elements. Contradiction.