# The 6 generals problem

6 generals propose locking a safe containing secret stuff with a number of different locks. Each general will get a certain set of keys to these locks. How many locks are required and how many keys must each general have so that, unless 4 generals are present, the safe can't be opened. Generalize to $n$ generals and $m$ minimum number of generals required.

Here's where I've gotten to so far. Define a function $$f(n,m)=k$$ where $n$ and $m$ are as defined above and $k$ is the number of locks required. I've figured out $f(1,1)$, $f(2,1)$, $f(2,2)$ and so on until $f(4,4)$. I've noticed that if I arrange these values in a Pascal-like triangle, I can get the values in the lower row by summing the 2 numbers above it (I can't figure out how to display it using LaTeX). Doing this, I get the number of locks required as $24$ but I'm still working on the key distribution.

My question is whether I'm on the right track, and if so, how do I go about proving my solution. Thanks for your help.

[EDIT] To make it clear, the arrangement must be such that the safe can be opened when any $4$ generals are present and not if the number of generals is $3$ or less.

Sorry not to post this as a comment, but I don't have enough points.

Are they supposed to be able to open the safe if and only if at least four generals are present?

Edit: Here is the outline of a solution for the case of four out of six generals, but it generalizes easily.

Let the locks be numbered $1, \ldots, p$, and the generals $1, \ldots, 6$. For each $i = 1, \ldots, p$, let $K_i$ be the set of generals with key number $i$. Thus $K_i$ is a subset of $\{1, \ldots, 6\}$.

The condition that four generals should always be able to open the safe amounts to saying that:

(1): Each $K_i$ should have at least three elements. (6 - 4 + 1 = 3.)

The condition that three generals should never be able to open the safe amounts to saying that:

(2): For each set S = $\{ a, b, c \}$ of three generals, at least one of the sets $K_i$ should be disjoint from $S$.

If we want to minimize the number of sets $K_i$ necessary, we should make the $K_i$'s as small as possible, because of point 2. However, because of point 1, they should have at least three elements. Thus they should all have three elements.

By point 2, the $K_i$'s should in fact constitute all subsets of $\{1, \ldots, 6\}$ with three elements.

Since we obviously wish to avoid repetition of $K_i$'s, the minimal number of $K_i$'s is the number of subsets of $\{1, \ldots, 6\}$ with three elements, which is $\binom{6}{3} = 20$.

• Certainly. Otherwise, the answer would be zero locks, zero keys and an unopenable door. – Tomas Jan 5 '14 at 12:05
• It seemed conceivable to me that some other unarticulated condition would also be imposed, making the problem nontrivial. – user119191 Jan 5 '14 at 12:07