4. In a company managed by several directors, there is a safe locked with six keyholes. Each director has three keys, with which they can unlock three different keyholes. Each key can unlock exactly one keyhole.

No two directors can unlock the same three keyholes, and no two directors together can open the safe. What is the maximum number of directors who manage this company?

## dMFA

## 59th Mathematical Competition for High School Students in Slovenia  Kranj, April 18, 2015

## Solutions to the problems and scoring system
IV /4. 1. method. The company employs at most 10 directors.

Let's denote the keys or corresponding keychains with numbers from 1 to 6. Each director has a set of 3 keys from 3 different keychains, and no two directors have the same sets. Therefore, let's first count how many different sets of 3 keys exist. For a specific set of keys, we have 6 keychains to choose from, and we need to select 3. This is a combination problem, where we choose 3 out of 6 elements. The number of such combinations is $\binom{6}{3}=20$ (we can also count them by listing all possibilities). Each set of 3 keys has a complementary set of 3 keys, which is the set of the remaining 3 keychains. For example, the set of keys $\{2,3,5\}$ has the complementary set of keys $\{1,4,6\}$. We can divide the set of all different sets of keys into 10 pairs of complementary sets of keys. Since each such pair of keys can open the safe together, no two directors can have complementary sets of keys. Therefore, there can be at most 10 directors, as from each pair of complementary sets of keys, at most one set can belong to a director.

Let's show that the company can indeed employ 10 directors, meaning that there exist 10 sets of keys that meet the conditions of the problem. All we need to do is choose one set from each pair of complementary sets of keys (for example, the one that contains key 1). Thus, 10 directors can have, for example, the following sets of keys: $\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,2,6\},\{1,3,4\}$, $\{1,3,5\},\{1,3,6\},\{1,4,5\},\{1,4,6\},\{1,5,6\}$.

2. method. Let's denote the keychains or corresponding keys with numbers from 1 to 6. Let's write down all possible different combinations of three keys in pairs:

- $\{1,2,3\}$ and $\{4,5,6\}$,
- $\{1,2,4\}$ and $\{3,5,6\}$,
- $\{1,2,5\}$ and $\{3,4,6\}$,
- $\{3,4,5\}$ and $\{1,2,6\}$,
- $\{1,3,4\}$ and $\{2,5,6\}$,
- $\{1,3,5\}$ and $\{2,4,6\}$,
- $\{2,4,5\}$ and $\{1,3,6\}$,
- $\{1,4,5\}$ and $\{2,3,6\}$,
- $\{2,3,5\}$ and $\{1,4,6\}$,
- $\{2,3,4\}$ and $\{1,5,6\}$.

We observe that each of these pairs of key combinations contains all 6 keys, so at most one combination from each pair can belong to a director. Since there are 10 such pairs, the company can employ at most 10 directors.

We also see that 10 directors can indeed be employed by the company, as these directors can have, for example, the first combination of keys from each pair. No two combinations from this selection contain all six keys, as each of them is missing key 6.

3. method. Let $\mathcal{K}=\{1,2,3,4,5,6\}$ represent the set of all keys. Each director has 3 different keys, i.e., a subset of $\mathcal{K}$ with exactly 3 elements. Let's denote all such subsets by $\binom{\mathcal{K}}{3}$. Since no two directors have the same set of keys, each element of $\binom{\mathcal{K}}{3}$ represents a set of keys for one potential director. Let $A, B \subset\binom{\mathcal{K}}{3}$ be the sets of keys for two different directors. If $A \cup B=\mathcal{K}$, then these two directors can open the safe together. Let $G$ be a graph where

$$
V(G)=\binom{\mathcal{K}}{3} \quad \text { and } \quad\{A, B\} \in E(G) \Longleftrightarrow A \cup B=\mathcal{K}
$$

Each independent set of this graph corresponds to a group of directors that meet the conditions of the problem. We are interested in the largest independent set. Let $\alpha(G)$ denote the size of the largest independent set in the graph $G$. The graph $G$ is shown in the following table (for clarity, the vertices are labeled with numbers whose digits are the elements of the sets corresponding to the vertices of the graph):

| 123 | 124 | 125 | 126 | 134 | 135 | 136 | 145 | 146 | 156 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| 0 | 0 | 9 | 9 | 9 | 0 | 9 | 0 | 9 | 0 |
| 456 | 356 | 346 | 345 | 256 | 246 | 245 | 236 | 235 | 234 |

If $G=G_{1}+G_{2}$, i.e., the disjoint union of two graphs, then $\alpha(G)=\alpha\left(G_{1}\right)+\alpha\left(G_{2}\right)$. Since $\alpha\left(K_{2}\right)=1$, we have $\alpha(G)=10$, as $G \cong \underbrace{K_{2}+K_{2}+\cdots+K_{2}}_{10}$.[^0]

[^0]:    The correct answer is 10

    1 point

    Determining that $\binom{6}{2}=20$ sets of 3 keys 1 point

    Determining that for each set of keys there is exactly 1 complementary set 1 point

    Justifying that complementary pairs do not appear simultaneously in the solution 1 point

    Justifying that there can be at most 10 directors 1 point

    Justifying that there can indeed be 10 directors 1 point