Keys and Locks
Each of the four distinct keys below fits exactly one of the four locks. In the worst case scenario, how many times do you have to test a key in a lock in order to match up all the locks and keys?
Note : You do not need to open the locks. You only need to match the locks to their keys.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
8 solutions
How can you unlock the door without any tries? U have one lock and one key. Now try unlocking the door with 0 tries. The guy who wrote 4+3+2+1 is right.
Log in to reply
If you have one lock and one key, there is no problem to find proper pair. It is clear the key is for that lock. So i put that as zero.
This is because, as it says in the hint of the problem, you don't actually HAVE to unlock the door or whatever it is the lock is locking. You only have to match the keys to the locks.
Essentially, matching keys to locks takes 1 less try per lock than unlocking the same number of locks.
When the first key will not get the matching lock we will go for 4th trial which will be successful trial.Why here successful trials are not counted??
Log in to reply
The problem clearly stated "In the worst case scenario" so for the first key maximum trials of not matching is 3. If three are not matching we know the 4th one is the correct one.(no need to try on that)
Okay, for me, opening the lock you know is the right one for a given key also counted as a "try". Little bit unclear problem definition.
Log in to reply
The question is about "worst case scenario", If you open it will be less than the given count. So for each iteration you need to think what is the worst case. For example, in the first case, take one key and check with 3 locks which are not proper pair for that key in worst case. Then, it is clear the fourth lock is the pare for that key.(no need to check that). But in the best case while take the key first lock itself be a better pair. (question asked for worst case scenario so we take the count of 3)
why the successful try is not a try???
Edit: Ok, I see now that the problem says to match up the keys not to open the locks, sneaky.
I thought about the 4th try . But do you really have to try it on the fourth-if you knew the key didn't fit the other 3. But God help me .I don't understand the equation/algebra crap . Brain freeze
To the OP, it's probably worth explicitly saying that you don't need to try the last lock for each key. That same red herring has tripped up everyone commenting!
last line you can end up with 2 key and 2 locks that do not match at all. Wrong, very wrong logic. Please reconsider. Buy 4 lock and if you succeed (always) in 6 steps I will pay the cost. If you succeed in 9 or 10 you will pay ... It is not simple recursivity it is rather divide and conquer
Log in to reply
Remember that you don't need to open the locks! I might not be able to open all four locks in 6 tries or less, but if you give me six tries I can certainly tell you which keys will open up which locks.
Can you prove there is no better algorithm than the one you counted?
But this is the worst case scenario. You are showing the decent case scenario.
Log in to reply
It is worst case scenario only. If, it is the best case each iteration you will get the pair in the first trial itself.
This only proves that the given strategy will work in 6 tries. It might be possible that some other strategy has a worst case scenario of needing only 5 tries or less; you haven't ruled it out.
Well, not to be too pedantic, but the question does not specify that each lock only fits one of the four keys!
Log in to reply
That would follow under "worst case". Any key that fit more than one lock, or any lock that could be opened by more than one key, would not be worst case scenario.
Log in to reply
How do you work this out? ISTM this makes the worst case scenario 12 tries (try each key in 3 locks, and each time the lock you didn't try is the one it fits).
“Each of the four distinct keys below fits exactly one of the four locks.” Thus, each key is different, and is accepted by exactly one lock, therefore each lock is distinct. There may be “master keys” out there that open several locks, but the point of a lock is that only a key for that lock can open it, so by explicitly stating each key was unique, the problem established that each lock was unique.
I Thought it was 10 (4+3+2+1) too. Because the last try should be counted, but on a second thought (a long one, after reading your answer, looking at the problem picture and the note of the problem) it may be 6, because you do not need to open the lock, so you just know that the key didn´t FIT (and this is the key word: FIT) in the other locks, it must FIT in the last one, so there´s NO NEED TO TEST IT. But let´s be real guys, human nature would prompt us to test the last lock, hence 10. lol
Log in to reply
I agree with wholeheartedly with that last sentence. I also think that the Exact Sciences should take more of the Humanities into account and that, combining Mathematics with Psychology, the answer should be changed to 10 :D
Log in to reply
How you think the problem, it depends. Suppose in your home you have 4 locks and 4 keys and mixed up this worst case logic with 6 try will guarantee the result. Psychology your mind will also say OK. Since your mind will believe, definitely the last one will fit without trail. The problem statement gives the guaranty "Each of the four distinct keys below fits exactly one of the four locks.". So the answer 6 is correct.
What is this equation called?
This is just a bad question. Without trying the key to its matching lock, there's no way to know if it matches, which is what you asked. The answer is 10.
Log in to reply
This really is just a word game, and has nothing to do with mathematics or probability.
Log in to reply
There's a subtle difference here. The question didn't ask us to open the locks, they just asked us to match the keys to the locks.
6 is the worst scenario, 3 is the best one. There are many probabilities to chek if the locks match or not.
Log in to reply
But There is no rule to hoe you picknick right? So you could technically try lock 1 3 Times, then lock 2 3 Times, lock 3 3 Times, lock 4 3 Times and then complete Them. That would be 16.
((n)(n-1)) was a distant memory, for me... But my answer was 6... I accidently pressed 5 (whoops)...
I got to the answer six just mentally by starting with cancelling out 16 (4X4 =16), and then subtracting the combinations from that start...
16 (minus a key and lock match) leaves you with 3 locks and 4 keys... 12
Etcetera...
To determine the first lock, you need 3 tries. If none of them fits, then the last key fits. To determine the second lock, you need 2 tries, and so on. Equation:3+2+1=6.
Isn't that 4+3+2+1 ? Or just need to ensure the right key to the right lock?
Log in to reply
That would be to unlock all the locks, but not to figure out which lock goes with which key. I made the same mistake; I think the wording is a bit unclear and it almost feels like a trick question.
Log in to reply
Ya, he just said 'match up' which is a bit ambiguous .
Log in to reply
@Kelvin Hong – Yeah, we don't need unlock it
@Kelvin Hong – It's a "she" but never mind
Oh, ok I will edit it. Thanks!
I don't know how to though because there are so many solvers....what should I dooooo?
The difference is in the definition of "try" and it's ambiguous at best.
Technically the worst case scenario is infinity because the problem never said that you cannot retry locks. So that means that I can just try the same lock an infinite amount of times
Log in to reply
I think the problem didn't mean to state that.
sounds like Hypergeometric distribution and Geometric distribution
Worst case minimal scenario. The point is what’s the maximum number necessary to find each match. In redundant tries you’re not finding anything, so those don’t count. If we ignore rationality and logic, every question becomes pointless, because you could repeat any step infinitely.
There is no conditions "each lock accepts only one key" i.e. 2 keys could open the same lock. So the worst scenario is each key must be tested on all but one locks. So 4 keys probe 3 locks = 12 tests.
Log in to reply
“Each of the four distinct keys below fits exactly one of the four locks.” Thus, each key is different, and is accepted by exactly one lock, therefore each lock is distinct. There may be “master keys” out there that open several locks, but the point of a lock is that only a key for that lock can open it (because in setting a lock you know/control what kind of key can open it), so by explicitly stating each key was unique, the problem established that each lock was unique.
In the 4 keys and 4 locks, if we take one of the key and check the locks worst case 3 of the locks will not open. It is clear that the fourth lock is the pair of that key.
Now, in the remaining 3 keys and 3 locks, If we take one of the key and check the locks worst case 2 of the locks will not open. It is clear that the third lock is the pair of that key.
Now, in the remaining 2 keys and 2 locks, If we take one of the key and check the locks worst case 1 of the lock will not open. It is clear that the second lock is the pair of that key. At the same time the remaining lock and the key are the pairs. Hence the total trials in the worst case=3+2+1=6
In General, for 'n' locks and 'n' keys, the total trails required to find the correct pairs in the worst case is 1 + 2 + ... + (n-1) = .
For n=4, the solution is = = 6
Derangement of 4 yields a 9. Still, how did you get 6?
Log in to reply
Recognizing the last “test” is unnecessary since you’ve eliminated all other options. Since the question said each lock matches exactly one unique key, and the objective is to find the minimum worst-case scenario steps to know each match, you don’t need the last test for each key because you’ve proven by process of elimination it must match.
I'm not too sure what the number of derangement has to do with the number of tries. How are you doing a bijection between these 2?
I think it would be more logical if we count the last key that fits, cause it's a test too; so if we got it at the first try, then it should be counted as 1 test.
Log in to reply
It’s not an assumption if you know beforehand each key/lock has only one match. Testing what we know must match is redundant and not apart of the minimal step worst case.
This only proves that the given strategy (find the key for the first lock, find the key for the second lock, etc) will work in 6 tries. It might be possible that some other strategy has a worst case scenario of needing only 5 tries or less; you haven't ruled it out.
the answer is 10. you need to put the key in the last lock to know it fits otherwise you are just assuming.
Log in to reply
No, the problem states that each key matches exactly one of the locks.
More people would get this question right if the question asked how many tests will fail, not how many there are in general.
Most people agree that a test is still a test whether it fails or succeeds.
The "key" to this puzzle was the note that stated that the locks need not be opened, just to pair with the correct key.
it did not state that getting a key right did not count as a trial. If it did, 9 would be correct.
Log in to reply
thats the reason i quit school. its more about trick questions than actually learning. math became logic and psychology, science was physics and geometry, its like, wtf are we learning here? at most you need to know how to calculate, but being tested psychologically has no real value to education or appearing intelligent. you can trick any monkey into eating a banana, and believing it'll get another one.
Take any two locks and any two keys. Under worst case scenario, In 4 tries you will know that these don't match which means these two keys belong to the other two locks. In only 1 try you will know which key matches which lock. Now there remain only two keys and two locks. Again, in 1 try, you will know which matches which. So, 4+1+1 = 6 tries.
n-1 ( n) / 2 = 4-1 * 4 / 2 = 6
This only proves that the given strategy will work in 6 tries. It might be possible that some other strategy has a worst case scenario of needing only 5 tries or less; you haven't ruled it out.
Log in to reply
5 was my answer, too. I can't find my original post/message. But it was along the (n-1) method...
Start with 16 combinations possible; (4 multiplied by 4). Then take one lock away (since a key didn't work). Now it's 3X4... 12. Etcetera.
It's a part of my brain that I have trouble controlling.
Even ignoring Ivan's point, your solution is not complete. You still need to deal with the case where in the first 4 tries, you match a lock and a key.
It does turn out that in this scenario, you only need 2 more tries to match up the 3 pairs. But this isn't immediately obvious.
I thought you needed to find all of the different combination since it clearly says. "without having to open the lock." I don't understand what I did wrong. I would rate this problem a 6 because it was confusing. I don't really understand this problem because it says"without having to open the lock." in the instructions but then it seems like you have to open the lock because some keys only go with some locks.
I don't agree with this solution, It says to consider the worst case scenario. If I number both locks and keys form 1 to 4 (1, 2, 3, 4), use the first key with the first locker, the 2nd key with 2nd locks and on, if none of them worked and I chose to rotate the keys from left to right and I only get to open all locks after rotating the keys 4 times we get the following order (2,3,4,1). For each rotation we did 4 tries (one for each key) and they were 4 rotations meaning that we had to try 16 times in order to open each lock. Maybe I misunderstood the problem, but as I see it the problem is not clear...
Tricky question. this. The hint about one only needing to match the keys to the locks, instead of opening all the locks, is the key to the answer here. This factor means that once you've eliminated all but 1 key for a given lock, you don't actually have to put the last key in the lock to know that it fits, saving you 1 "test" for every lock.
So the first match requires 3 tests at most for 4 keys, the second -- seeing as there are only 3 keys remaining -- requires 2 tests and the final two matches require a single test between them. Making for a total of 6 tests.
The least possible is 3 out of 4. Thus 3!=1×2×3=6 .
There are 4 locks to assign a key and 4 keys to test. Since it is not required to open the lock, the test demands the following:
For the first lock of four, three tries are necessary, as if it fails in all three times, we don't have to test the last key to know it is right. By following the logic: Lock 1 = 3 tries Lock 2 = 2 tries Lock 3 = 1 try Lock 4 = the remaining key. So, The answer is the Array(k:l) 3k × 2k × 1k × 1k
You test the first key 3 times---It fits the fourth lock. The next key you test on 2 of the remaining 3 locks-- It fits the 3rd lock. Of the two remaining keys you test one on two locks---it fits the 2nd lock. Then, you have the last key for the last lock. Thus: 3+2+1=6 tests ☺☺☺☺
Far too terse.
Can you explain what these numbers mean? Thanks!
I made a ridiculous mistake. I did 4+3+2
In the 4 keys & 4 locks, if we take one of the key and check the locks worst case 3 of the locks will not open. It is clear that with out checking the fourth lock is the pair of that key.
Now, in the remaining 3 keys & 3 locks, If we take one of the key and check the locks worst case 2 of the locks will not open. It is clear that with out checking the third lock is the pair of that key.
Now, in the remaining 2 keys & 2 locks, If we take one of the key and check the locks worst case 1 of the lock will not open. It is clear that with out checking the second lock is the pair of that key. At the same time the remaining lock and the key are the pairs no need to check. Hence the total trials in the worst case=3+2+1=6
In General, for 'n' locks & 'n' keys, the total trails required to find the correct pairs in the worst case is 1 + 2 + ... + (n-1) = 2 ( n − 1 ) ( n ) .
For n=4, the solution is 2 ( 4 − 1 ) ( 4 ) = 2 ( 3 ) ( 4 ) = 6