Here's an old puzzle I found in a book once.
A box has some number of locks on it. It is guarded by a Grand Vizier and four slaves, each of which hold keys to the locks.
The Grand Vizier and slaves each hold a different set of keys to the locks, and each key they hold opens a different lock.
The keys they hold are in a certain combination such that as long as the Grand Vizier is with one slave, or if any three slaves are together, they will have all the keys to open the box; but if less than that are together, they cannot. How many locks did this box have at minimum?
Answer
The best solution I've found has 7 locks.
The Grand Vizier has keys 1, 2, 3, 4, 5, 6.
Slave 1 has keys 1, 2, 3, 7.
Slave 2 has keys 1, 4, 5, 7.
Slave 3 has keys 2, 4, 6, 7.
Slave 4 has keys 3, 5, 6, 7.
A couple of things simplify the deduction of this puzzle:
If the Grand Vizier has every key but one, and every slave has the missing key, that reduces the problem to 4 slaves and one less lock.
Every key must be held by at least two slaves.
The rest I just brute forced with a (digital) pencil and paper.
No comments:
Post a Comment