Home > General
| Open By Majority (Posted on 2004-03-03) |
 |
A group of five people want to put a set of locks on a chest and distribute keys to the locks amongst themselves in such a way that all the locks on the chest could be opened only when at least three of them were present to open it.
How many locks would be needed, and how many keys?
Solution to revised puzzle
|
 | Comment 29 of 45 | 
|
Here is a solution with 13 locks and 39 keys. It probably isn't the minimum number. After the latest revision to the terms of the puzzle, determining and proving the minimum has become just another sorry candidate for a software program solution.
:-(
Any two people must be unable to unlock one of the locks. But then the other three can open it; otherwise there would be three people who couldn't open it. As there are 10 distinct groups of 2 people out of 5, there are AT LEAST 10 locks.
Let the people be A,B,C,D,E.
Possible groups of 3 are:
5*4*3/(3!) = 60/6 = 10
A+B+C
A+B+D
A+B+E
A+C+D
A+C+E
A+D+E
B+C+D
B+C+E
B+D+E
C+D+E
Lets use integers to signify both the locks and the keys to open them.
We can distribute 30 keys to 10 locks among the 5 people as follows:
A[1,2,3,4,7]
B[1,3,4,5,6,7]
C[2,4,5,7,8,9,10]
D[1,5,6,8,9,10]
E[2,3,6,8,9,10]
But now A+D, B+C and B+E can open the chest !!!!!!
Add 3 more locks:
Give everyone but A and D a key to 11.
Given everyone but B and C a key to 12.
Given everyone but B and E a key to 13.
A[1,2,3,4,7,12,13]
B[1,3,4,5,6,7,11]
C[2,4,5,7,8,9,10,11,13]
D[1,5,6,8,9,10,12,13]
E[2,3,6,8,9,10,11,12]
This works.
Any three can open the chest.
A+B lack a key to 8.
A+C lack a key to 6.
A+D lack a key to 11.
A+E lack a key to 5.
B+C lack a key to 12.
B+D lack a key to 2.
B+E lack a key to 13.
C+D lack a key to 3.
C+E lack a key to 1.
D+E lack a key to 4.
Edited on March 4, 2004, 11:34 am
|
|
Posted by Penny
on 2004-03-04 11:32:23 |
|
|
Please log in:
Forums (1)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (16)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
