## Task 4 - 281244

To open a safe, an unknown three-digit combination $\left(a_{1}, a_{2}, a_{3}\right)$ must be set, where the three numbers can be set independently of each other, and for each of the three numbers, exactly 8 values are possible.

Due to a defect, however, the safe opens whenever a set combination $\left(k_{1}, k_{2}, k_{3}\right)$ meets at least two of the three conditions $k_{i}=a_{i}(i=1,2,3)$.

Determine the smallest number $N$, for which there are $N$ combinations that, when tried, will always open the safe (i.e., for any unknown combination $\left.\left(a_{1}, a_{2}, a_{3}\right)\right$).
For a combination $k=\left(k_{1}, k_{2}, k_{3}\right)$, it is said to "cover" $\left(a_{1}, a_{2}, a_{3}\right)$ if and only if it satisfies at least two of the three conditions $k_{i}=a_{i}$. The eight possible values of the $a_{i}$ are, without loss of generality, the numbers $0,1, \ldots, 7$.

I. Let $S, T, U$ be the sets

$$
\begin{aligned}
& S=\{(0,0,1),(0,1,0),(1,0,0),(1,1,1)\} \\
& T=\{(0,0,2),(0,2,0),(2,0,0),(2,2,2)\} \\
& U=\{(0,0,0),(4,4,4)\}
\end{aligned}
$$

The 32 combinations $k=s+t+u(s \in S, t \in T, u \in U)$ form an example of combinations that cover all $8^{3}$ combinations $\left(a_{1}, a_{2}, a_{3}\right)$. To prove this, consider an arbitrary one of these combinations $\left(a_{1}, a_{2}, a_{3}\right)$. First, set

$$
u= \begin{cases}(0,0,0) & \text { if at least two } a_{m}, a_{n} \leq 3 \text { are }(m \neq n) \\ (4,4,4) & \text { otherwise }\end{cases}
$$

After this, there always exist two indices $m<n$ such that for $i=m$ and for $i=n$ the number $b_{i}=a_{i}-u_{i}$ satisfies $0 \leq b_{i} \leq 3$; thus, there exist

$$
s_{i} \in\{0 ; 1\}, \quad t_{i} \in\{0 ; 2\}
$$

such that $b_{i}=s_{i}+t_{i} \quad(4)$.

For each possibility of the index pair $(m ; n)=(1 ; 2),(1 ; 3),(2 ; 3)$ and for each possibility of the $s_{i}, t_{i}$ according to (3) and (4), one finds, by the definition of $S$ and $T$, an $s=\left(s_{1}, s_{2}, s_{3}\right) \in S$ and a $t=\left(t_{1}, t_{2}, t_{3}\right) \in T$, in which $s_{m}, s_{n}$ and $t_{m}, t_{n}$ are precisely the numbers from (3) and (4). The combination $k=\left(k_{1}, k_{2}, k_{3}\right)=s+t+u$ formed with this and with $u$ from (1) satisfies, according to (4) and (2), the two conditions

$$
k_{i}=s_{i}+t_{i}+u_{i}=b_{i}+u_{i}=a_{i} \quad(i=, m, n)
$$

q.e.d.

II. Suppose there exists a set $K$ of at most 31 combinations that cover all $8^{3}$ combinations $\left(a_{1}, a_{2}, a_{3}\right)$. A contradiction can be derived from this assumption, for example, as follows:

First, it follows that for at least one of the eight values $p=0,1, \ldots, 7$ the set $P$ of all $(p, y, z)$ $(y, z \in\{0,1, \ldots, 7\})$ contains at most three combinations from $K$. Therefore, there are at least three pairwise different numbers $c, d, e$ such that from $\left(k_{1}, k_{2}, k_{3}\right) \in K$ and $k_{1}=p$ it always follows that $k_{2} \in\{c, d, e\}$, and there are (not necessarily different) numbers $f, g, h$ such that from $\left(k_{1}, k_{2}, k_{3}\right) \in K$ and $k_{1}=p$ it always follows that $k_{3} \in\{f, g, h\}$.

Let $Y=\{0, \ldots, 7\} \backslash\{c, d, e\}$ and $Z=\{0, \ldots, 7\} \backslash\{f, g, h\}$.

The set of all $(p, y, z) \quad(y \in Y, z \in Z) \quad$ (5) contains at least $(8-3) \cdot(8-3)=25$ combinations. Each of them is covered by a $\left(k_{1}, k_{2}, k_{3}\right) \in K$ according to the assumption.

By the choice of $c, \ldots, f$, this is only possible with $k_{1} \neq p$ and thus only with $k_{2} \in Y$ and $k_{3} \in Z$; therefore, for any two different combinations (5), there must also be two different covering combinations from $K$. This shows that there must be at least 25 combinations $\left(k_{1}, k_{2}, k_{3}\right) \in K$ with $k_{2} \notin\{c, d, e\}$ and thus at most $31-25=6$ with $k_{2} \in\{c, d, e\}$.

Due to the pairwise distinctness of the $c, d, e$, it follows that for at least one of the three values $a=c, d, e$ the set $Q$ of all $(x, q, z)(x, z \in\{0, \ldots, 7\})$ contains at most two combinations from $K$.

Analogously to $P$, this results in $(8-2) \cdot(8-2)=36$ combinations in $K$ and thus a contradiction. With I. and II., the smallest number N032 is proven.