Fernando is a cautious person, and the gate of his house has 10 distinct padlocks, each of which can only be opened by its respective key, and each key opens only one padlock. To open the gate, he must have at least one key for each padlock. For security, Fernando has distributed exactly two different keys in the 45 drawers at his workplace, such that two keys in the same drawer open different padlocks, and there are no two drawers containing keys that open exactly the same padlocks.

a) How many possible pairs of keys can be formed with 10 distinct keys?

b) How many copies of each key does Fernando need to have to form all possible pairs of keys?

c) What is the minimum number of drawers that Fernando must open to ensure he has 10 distinct keys and can open the gate to his house?
Solution

a) Notice that the pair $\{a, b\}$ is the same as $\{b, a\}$, since they will open the same locks. Therefore, after choosing key $a$ in 10 ways and key $b$ in 9 ways, we must divide the result by 2, obtaining $\frac{10 \cdot 9}{2}=45$ pairs.

b) Since each key will pair with all the others exactly once, Fernando needs 9 copies of each of the keys.

c) From the previous item, each key is in 9 drawers. To remove all the drawers that do not contain a key $X$, Fernando would need to open $45-9=36$ drawers. Thus, opening 36 drawers does not guarantee the opening of the locks, as it is possible that he chooses exactly the drawers that do not contain the key $X$. On the other hand, if he opens 37 drawers, it is not possible for any key to be missing. Therefore, the minimum is 37.