A company has five directors. The regulations of the company require that any majority (three or more) of the directors should be able to open its strongroom, but any minority (two or less) should not be able to do so. The strongroom is equipped with ten locks, so that it can only be opened when keys to all ten locks are available. Find all positive integers $n$ such that it is possible to give each of the directors a set of keys to $n$ different locks, according to the requirements and regulations of the company.
Problem
Source: Pan African 2000
Tags: pigeonhole principle, combinatorics
Oni
04.10.2005 07:58
If n>4 (such as 5,6,7...) then two or lesser than two directors will be able to open the strongroom. And if n<4(such as 3,2,1,...)than three or more than three directors will not be able to open it. But if n=4 then two or less than two directors will not be able to open it and three or more then three directors will be able to open it . So n=4 [Please infom me if I am right or not]
daniel73
18.09.2007 20:32
Assume the company has $ 2n+1$ executives. a) What is the minimum number $ l$ of locks necessary such that each majority ($ n+1$ or more) may open the vault, but no minority ($ n$ or less) may open the vault? b) What are the possible numbers $ k$ of keys that each executive should be given in this case? (each executive should be given the same number of keys, otherwise those with less keys would be extremely jealous!!! ) Solution (hidden) below for part (a):
a) For each one of the $ \binom{2n+1}{n}$ minorities of exactly $ n$ executives, there is at least one lock that this minority cannot open. Assume that there are two distinct minorities of exactly $ n$ executives that cannot open the same lock. Thus, the majority formed by their union (since they are distinct minorities, they differ at least by one executive, so their union contains at least $ n+1$ executives) cannot open that lock. So the number of locks is at least equal to the number of minorities with exactly $ n$ executives, i.e., $ l\geq\binom{2n+1}{n}$. With exactly $ l =\binom{2n+1}{n}$, let us number both the minorities of exactly $ n$ executives, and the locks, from 1 to $ \binom{2n+1}{n}$, and let us give an executive a key to the $ i$-th lock iff he does not belong to the $ i$-th minority, so this lock (and hence the vault) will not be opened by the $ i$-th minority of $ n$ executives (and thus by any minorities contained therein). On the other hand, consider any majority of at least $ n+1$ executives that cannot open the vault, or there is at least one lock, the $ j$-th, that they cannot open. The majority is then contained in the minority of exactly $ n$ executives to which the $ j$-th key was not given, which is absurd. So the minimum number of locks is $ l =\binom{2n+1}{n}=\binom{2n+1}{n+1}$.
Solution (hidden) below for part (b):
b) So $ l =\binom{2n+1}{n}=\binom{2n+1}{n+1}$, which in the case $ n = 2$ yields $ l = 10$, as in the original problem. Assume that there is a key to which less than $ n+1$ copies are given to the executives. Therefore, there are at least $ n+1$ executives that do not have this key, and their majority cannot open the vault. So the minimum (total) number of keys is $ (n+1)l = (2n+1)\binom{2n}{n}$, and since each executive receives the same number and there are $ 2n+1$ executives, each one receives at least $ \binom{2n}{n}$ keys. Assume that each one of the $ 2n+1$ executives is given at least $ k =\binom{2n}{n}+1$ keys. The total number of keys divided by the number of locks is then $ \frac{(2n+1)k}{l}>\frac{(2n+1)\binom{2n}{n}}{\binom{2n+1}{n}}= n+1$, so there is at least one key given to at least $ n+2$ executives. This means that there is one key that any minority of $ n$ executives may open, since there are at most $ n-1$ executives that lack the key to it. Or, the number of locks that may not be opened by at least one of the $ l$ minorities of $ n$ executives is at most $ l-1$, and by Dirichlet's pigeonhole principle at least one lock is not opened by at least two distinct such minorities, or as above it is not opened by at least one majority. Contradiction, so the number of keys given to each executive is exactly $ \binom{2n}{n}$. In our case, each executive receives exactly $ k =\binom{4}{2}= 6$ keys.
huang
29.07.2009 21:12
This is a nice solution. I myself just did the brute force solution (considered all 10 possibilities of numbers of locks to give to each director and just went eliminating them one by one by considering the unions of the subsets of keys)
math_and_me
21.06.2019 03:29
Directors A and B cannot open all the locks together, so there is a lock (say number 1), which neither can open, but all other directors must have key number 1. The same reasoning applies to all 10 unordered pairs of directors; each pair will be missing a particular key, and all other directors will own that key. This tells us how the 10 keys must be distributed to have the desired effect (the only choice being the particular labelling of the keys). Each director is missing a different key for each of the 4 directors with whom he or she can form a pair, so n =6. Just pasted it :p
DiaaSaid
22.07.2024 05:46
For convention, denote the 5 directors by $D_i$ for $i=1$, $\dots$, $5$, and the 10 locks by $\ell_i$ for $i=1$, $\dots$, $10$. Also, let $\ell \in D$ means that director $D$ possesses the lock $\ell$, and let $D^\prime=\{\ell_1,\dots,\ell_{10}\}\setminus D$. Consider $n=7$, where $n$ refers to the number of different locks given to each $D$. Because $D_i$ and $D_j$ cannot proceed the doors by themselves, they both lack some lock $\ell$ for any $1\leq i\neq j \leq 5$. WLOG, consider $D_1$, it lacks 4 different $\ell$'s, one for each $D_i$, $i=1$, $\dots$, $4$. So $7=|D_1|\leq 6$ (Contradiction). The same logic holds for larger values of $n$. It's concluded that $n\leq 6$. Consider $n=5$. Then $D^\prime_i=10-5=5$ for each $i=1$, $\dots$, $5$. So there are $5\cdot5=25$ places for $\ell_i$ as elements in $D^\prime_j$ for $i=1$, $\dots$, $10$, and $j=1$, $\dots$, $5$. $\ell_i$ can be used as an element in the $D^\prime$ sets at most two times (if three, the 3 corresponding $D$ sets will disqualify for the regulations). But this means there are at most $2\cdot 10=20$ available places for $\ell_i$. By the Pigeonhole Principle, there exists some lock $\ell$ that will appear more than twice. The same logic holds for smaller values of $n$. It's concluded that $n\geq 6$. Because $n\leq 6$ and $n\geq 6$, it's a must that $n=6$. $\square$