orl wrote: The lock of a safe consists of 3 wheels, each of which may be set in 8 different ways 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 which must be tried if one is to guarantee being able to open the safe (assuming the "right combination" is not known)? Someone who knows the solution of this?

The problem belongs to the chapter of Combinatorics called "Packings and Coverings". A typical question would be: given a set $X$ of $n$ elements, what is the minimal number of triplets in a family $\mathcal{F}$ of subsets of $X$ of cardinality $3$, such that any pair of elements of $X$ is contained in at least one triplet of $\mathcal{F}$ (triplets covering doubletons)? This question has been fully answered, sometimes towards the end of the XX century - but I lack a reference. In the problem at hand, the situation is complicated by needing also that the pair be in the right position (in both doubletons and triplets, position matters).

The answer is $32$ Lower Bound Assume there exists a set $S$ of $31$ triplets that cover all combinations. Let $S_i$ be the triplets in $S$ with first component equal to $i$, for $i=1,2,...,8$. There must exist some $i$ such that $|S_i| \le \textstyle\lfloor\frac{31}{8} \rfloor = 3$. wlog $i=1$ Consider the second and third components in the triplets of $S_1$. Suppose $k_1\le 3$ numbers appear in some triplet as a second component and $k_2\le 3$ as a third component. Then there are $(8-k_1)(8-k_2)\ge 25$ triplets $(1,y,z)$ that don't share two components with any triplet in $S_1$. Let the set of triplets be $K$. So among the other sets $S_i$ there exists a triplet of the form $(i,y,z)$ that meets $(1,y,z)$ in the last two components for each $(1,y,z)\in K$. If each $S_i$ for $i\ge 2$ contained a triplet $(i,j,k)$ that doesn't meet a triplet in $K$ in two components then $|S| \ge |S_1| + |K| + 7 \ge 0 + 25 + 7 = 32$ contradiction. So there exists a set, say $S_2$, such that every triplet in $S_2$ meets an element of $K$ in two components (i.e. the last two). But now there are at least $k_1$ elelemts are that aren't a second component of a triplet in $S_2$ and at least $k_2$ elements that aren't a third component. So there are at least $k_1k_2$ triplets $(2,y,z)$ that don't meet any element of $S_2$ in two components. Call these triplets $K'$. No triplet can meet a triplet in both $K$ and $K'$ because triplets in $K$ and $K'$ have distinct components. Meaning that $|S| \ge |K| + |K'| = (8-k_1)(8-k_2) + k_1k_2 = 32 + 2(4-k_1)(4-k_2)$ where $k_1,k_2 \le 3$. This gives $|S| \ge 34$ and we have our contradiction. Upper Bound For all $0\le i,j \le 3$ take the triplets $(i,j,i+j \mod 4)$ and $(4+i,4+j,4 +(i+j \mod 4))$ (which is $2\cdot 4^2=32$ triplets in total). Now for any triplet $(a,b,c)$ one of the pairs $(a,b),(b,c)$ or $(c,a)$ will be in the same interval $\{1,2,3,4\}$ or $\{5,6,7,8\}$. So in one of $(i,j,i+j \mod 4)$ or $(4+i,4+j,4 + (i+j\mod 4))$ we will be able to select $i,j$ to get the desired result.