2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.