January Problem to Ponder: Under Lock and Key
In medieval times, the inhabitants of a remote village decided to
lock the village valuables in a giant chest to protect them from
marauding thieves. They placed a number of locks on the chest, with each
lock needing its own distinct key. For additional security, the
villagers made sure that any three people from the village would always
have among them the keys needed to open the locks, but no two people
would have the keys to do it.
January Problem to Ponder— Some Ponderings
Under Lock and Key
Recall that January’s Problem to Ponder was as follows:
In medieval times, the inhabitants of a remote village decided to
lock the village valuables in a giant chest to protect them from
marauding thieves. They placed a number of locks on the chest, with each
lock needing its own distinct key. For additional security, the
villagers made sure that any three people from the village would always
have among them the keys needed to open the locks, but no two people
would have the keys to do it.
How many locks were required, and how many keys?
Students’ first reaction to this problem may be to wonder whether we
have enough information, since we don’t know how many people are in the
village. The solution to the problem will depend on the number of people
in the village. There must be at least three people in the village,
because no two people would have the keys to open the lock.
If there are three people in the village, we can solve the problem
with three distinct locks, with each of the three villagers possessing
one of the distinct keys to open a lock.
The table below represents the situation for three villagers—A,
B, and C—and three locks—1, 2, and 3. An “X” indicates that a villager
has a key to a particular lock; an “O” indicates that he or she does
not. There are three possible pairs of villagers—AB, AC, and BC—and each
pair has to be missing at least one key. Pair AB is missing key 1, AC
is missing key 2, and BC is missing key 3. However, ABC together can
open the chest, since among them they have keys for all three locks.
| 3 Villagers/ 3 Locks
|
1
|
2
|
3
|
| A
|
O
|
O
|
X
|
| B
|
O
|
X
|
O
|
| C
|
X
|
O
|
O
|
O indicates a villager is missing a key to that lock. X indicates that a villager has a key to that lock.
What if there are exactly four villagers? Again, for each pair, there
must be at least one lock for which they are missing a key—one lock
that they can’t open. Four villagers, A, B, C, and D, can form six
different pairs—AB, AC, AD, BC, BD, and CD—who can’t open the locks by
themselves. This suggests that we will need at least six distinct locks
for a village of four people, and that at least some of the villagers
will need more than one key.
| 4 Villagers/6 locks
|
1
|
2
|
3
|
4
|
5
|
6
|
| A
|
O
|
O
|
O
|
|
|
|
| B
|
O
|
|
|
O
|
O
|
|
| C
|
|
O
|
|
O
|
|
O
|
| D
|
|
|
O
|
|
O
|
O
|
In the table above, each of the six pairs of villagers is missing a
key to a different lock. The remaining cells must have an X; otherwise,
there would be a triple of villagers who would be missing a key for that
lock. If we distribute keys—represented by Xs—to the remaining cells,
we obtain this table:
| 4 Villagers/6 locks
|
1
|
2
|
3
|
4
|
5
|
6
|
| A
|
O
|
O
|
O
|
X
|
X
|
X
|
| B
|
O
|
X
|
X
|
O
|
O
|
X
|
| C
|
X
|
O
|
X
|
O
|
X
|
O
|
| D
|
X
|
X
|
O
|
X
|
O
|
O
|
O indicates a villager is missing a key to that lock. X indicates that a villager has a key to that lock.
A village of four people will need to put six different locks
on the chest and distribute keys so that each of the villagers will
individually have three different keys. No pair represented in the table
above has keys for all six locks, but every triple of villagers does
have keys among them for all six locks. So, a village with four people
will need six locks and twelve keys—three keys for each of the four
villagers.
If there are exactly five villagers—A, B, C, D, and E—there will be ten pairs of villagers—
AB, AC, AD, AE, BC, BD, BE, CD, CE, and DE—and we will need ten different locks on the chest.
Ponder some more on Under Lock and Key, and we’ll return to it next month.