|
Question 1201214: Allison has 6 keys and 4 locks. Each lock can be locked by only one of the 6 keys, and each key can only open one of the 4 locks. What is the minimum number of times she must try to open a lock to guarantee that all 4 locks are opened?
Found 2 solutions by ikleyn, greenestamps:
Answer by ikleyn(52790)   (Show Source):
Answer by greenestamps(13200)  (Show Source):
You can put this solution on YOUR website!
Consider the worst case scenarios with two different strategies:
Strategy 1: Pick a lock and find which key opens it
Strategy 2: Pick a key and find which lock it opens
Strategy 1....
With lock #1, the worst case is it takes tries with all 6 keys to open it: 6 tries
With lock #2, the worst case is it takes tries with all 5 remaining keys to open it: 5 tries
With lock #3, the worst case is it takes tries with all 4 remaining keys to open it: 4 tries
With lock #4, the worst case is it takes tries with all 3 remaining keys to open it: 3 tries
Total number of tries to open all 4 locks with strategy 1: 6+5+4+3 = 18
Strategy 2....
With key 1, the worst case is that it doesn't open any of the 4 locks: 4 tries
With key 2, the worst case is that it doesn't open any of the 4 locks: 4 tries
With key 3, there are 4 locks still locked; the worst case is that it takes 4 tries to open one of the locks: 4 tries
With key 4, there are 3 locks still locked; the worst case is that it takes 3 tries to open one of the locks: 3 tries
With key 5, there are 2 locks still locked; the worst case is that it takes 2 tries to open one of the locks: 2 tries
With key 6, there is only 1 lock still locked; the worst case (the only possibility) is that it takes 1 try to open the lock: 1 try
Total number of tries to open all 4 locks with strategy 2: 4+4+4+3+2+1 = 18
So with both strategies, the worst case is that it takes 18 tries to make sure all 4 locks are open.
You can experiment with mixtures of these two strategies; you will find that in all cases the worst case is still that it takes 18 tries to make sure all 4 locks are open.
ANSWER: A minimum of 18 tries is required to make sure all 4 locks are open.
|
|
|
| |
