There are 5 locks and 5 keys and each of the 5 keys matches each of the 5 locks. What is the minimum and the maximum trial numbers of attempts needed to confirm that each of the 5 keys matches each of the 5 locks?
A. 5,15
B. 4,15
C. 5,10
D. 4,10
E. 5,20
OA: D
Source: Math Revolution
here are 5 locks and 5 keys and each of the 5 keys matches
This topic has expert replies
GMAT/MBA Expert
- Ian Stewart
- GMAT Instructor
- Posts: 2621
- Joined: Mon Jun 02, 2008 3:17 am
- Location: Montreal
- Thanked: 1090 times
- Followed by:355 members
- GMAT Score:780
This should be an SC question. They don't mean "each key matches each lock" (which would mean every key works in any lock you choose). Instead they mean each key matches a different one of the locks. Nor is it clear what a "trial number of attempts" means - is a trial inserting a single key in a single lock, or inserting the set of five keys in the set of five locks?NandishSS wrote:There are 5 locks and 5 keys and each of the 5 keys matches each of the 5 locks. What is the minimum and the maximum trial numbers of attempts needed to confirm that each of the 5 keys matches each of the 5 locks?
A. 5,15
B. 4,15
C. 5,10
D. 4,10
E. 5,20
OA: D
Source: Math Revolution
The question also doesn't make logical sense, or at least the 'official answer' doesn't make sense. If we're assuming from the beginning that each key matches a lock, it's not clear why we need to do any tests at all. So if we're supposed to take that as a fact, the number of tests we need to do is zero. If we're not taking that as a fact, then surely we need to do at least five tests (try all five of the keys once), because how do you know if the fifth key works in the fifth lock without trying it? If I give someone a random key and a random lock, most of the time the key won't open the lock at all.
So I don't think this is a good question.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com
ianstewartgmat.com
ianstewartgmat.com
- DavidG@VeritasPrep
- Legendary Member
- Posts: 2663
- Joined: Wed Jan 14, 2015 8:25 am
- Location: Boston, MA
- Thanked: 1153 times
- Followed by:128 members
- GMAT Score:770
Well, clearly if the first 4 keys are all correctly matched with the appropriate lock, we already know that the last key will be paired with the remaining lock. So we know that the minimum number of attempts is 4. That leaves B and D.NandishSS wrote:There are 5 locks and 5 keys and each of the 5 keys matches each of the 5 locks. What is the minimum and the maximum trial numbers of attempts needed to confirm that each of the 5 keys matches each of the 5 locks?
A. 5,15
B. 4,15
C. 5,10
D. 4,10
E. 5,20
OA: D
Source: Math Revolution
So let's consider a worst case scenario to determine what the maximum number of attempts should be: Say we start with Key A. At most, it will take four tries to determine which lock this key should be paired with. (We try Lock B, C, D, and E before we realize it will only work with A.) So that's 4 attempts.
Now we're left with four keys and four locks. If we hit more bad luck, when we try to pair key B with the right lock, it will take us an additional three attempts. (We try lock C, D, and E, before seeing what the right match is.) That's 3 more attempts.
Now we have three keys and three locks. If we repeat this process with key C, the worst case scenario is that we attempt Lock D and E first, or 2 more attempts.
Now we have two keys and two locks. Worst case, we have one unsuccessful attempt with key D. At this point we'll have only one lock remaining.
Max attempts: 4 + 3 + 2 + 1 = 10.
The answer is D
- DavidG@VeritasPrep
- Legendary Member
- Posts: 2663
- Joined: Wed Jan 14, 2015 8:25 am
- Location: Boston, MA
- Thanked: 1153 times
- Followed by:128 members
- GMAT Score:770
Oh, that moment when you complete your response to a question only to see that Ian has demolished the logic of the problemIan Stewart wrote:This should be an SC question. They don't mean "each key matches each lock" (which would mean every key works in any lock you choose). Instead they mean each key matches a different one of the locks. Nor is it clear what a "trial number of attempts" means - is a trial inserting a single key in a single lock, or inserting the set of five keys in the set of five locks?NandishSS wrote:There are 5 locks and 5 keys and each of the 5 keys matches each of the 5 locks. What is the minimum and the maximum trial numbers of attempts needed to confirm that each of the 5 keys matches each of the 5 locks?
A. 5,15
B. 4,15
C. 5,10
D. 4,10
E. 5,20
OA: D
Source: Math Revolution
The question also doesn't make logical sense, or at least the 'official answer' doesn't make sense. If we're assuming from the beginning that each key matches a lock, it's not clear why we need to do any tests at all. So if we're supposed to take that as a fact, the number of tests we need to do is zero. If we're not taking that as a fact, then surely we need to do at least five tests (try all five of the keys once), because how do you know if the fifth key works in the fifth lock without trying it? If I give someone a random key and a random lock, most of the time the key won't open the lock at all.
So I don't think this is a good question.
GMAT/MBA Expert
- [email protected]
- Elite Legendary Member
- Posts: 10392
- Joined: Sun Jun 23, 2013 6:38 pm
- Location: Palo Alto, CA
- Thanked: 2867 times
- Followed by:511 members
- GMAT Score:800
Hi NandishSS,
This is a poorly-worded question, so you might want to consider studying with practice materials that are better "designed'.' That having been said, the 'intent' of this question is probably that there are 5 locks and 5 keys - and each of the keys opens exactly one of the 5 locks. We're asked for the least/most number of attempts that it would take to determine the proper 'pairing' of each key to each lock.
To start, you should notice that the answer choices are all relatively small, so you can probably 'brute force' the solution - just 'map out' how the attempts would have to go (without need of any complex math).
Let's call the locks: A, B, C, D and E
Let's call the (matching) keys: a, b, c, d and e
IF.... we 'luck out' and manage to place each key with each lock on the first try, there would be...
a in A = 1st attempt
b in B = 2nd attempt
c in C = 3rd attempt
d in D = 4th attempt
Based on what we're told, with just one lock and one key left, there'd be no reason to make an attempt - that key would have to fit that lock. Thus, the LEAST number of attempts would be 4. Eliminate Answers A, C and E.
In that same way, we can now determine what would happen if we were 'unlucky' and took the maximum number of tries to open each lock.....
a in B/C/D/E = 4 attempts... and then we'd know that a would have to 'match' A.
b in C/D/E = 3 attempts... and then we'd know that b would have 'match' B.
c in D/E = 2 attempts... and then we'd know that c would have to 'match' C.
d in E = 1 attempt... and then we'd know that d would have to 'match' D.
That would leave just e in just E, which would not require an additional attempt.
Thus, the MOST number of attempts would be 10.
Final Answer: D
GMAT assassins aren't born, they're made,
Rich
This is a poorly-worded question, so you might want to consider studying with practice materials that are better "designed'.' That having been said, the 'intent' of this question is probably that there are 5 locks and 5 keys - and each of the keys opens exactly one of the 5 locks. We're asked for the least/most number of attempts that it would take to determine the proper 'pairing' of each key to each lock.
To start, you should notice that the answer choices are all relatively small, so you can probably 'brute force' the solution - just 'map out' how the attempts would have to go (without need of any complex math).
Let's call the locks: A, B, C, D and E
Let's call the (matching) keys: a, b, c, d and e
IF.... we 'luck out' and manage to place each key with each lock on the first try, there would be...
a in A = 1st attempt
b in B = 2nd attempt
c in C = 3rd attempt
d in D = 4th attempt
Based on what we're told, with just one lock and one key left, there'd be no reason to make an attempt - that key would have to fit that lock. Thus, the LEAST number of attempts would be 4. Eliminate Answers A, C and E.
In that same way, we can now determine what would happen if we were 'unlucky' and took the maximum number of tries to open each lock.....
a in B/C/D/E = 4 attempts... and then we'd know that a would have to 'match' A.
b in C/D/E = 3 attempts... and then we'd know that b would have 'match' B.
c in D/E = 2 attempts... and then we'd know that c would have to 'match' C.
d in E = 1 attempt... and then we'd know that d would have to 'match' D.
That would leave just e in just E, which would not require an additional attempt.
Thus, the MOST number of attempts would be 10.
Final Answer: D
GMAT assassins aren't born, they're made,
Rich
-
- GMAT Instructor
- Posts: 2630
- Joined: Wed Sep 12, 2012 3:32 pm
- Location: East Bay all the way
- Thanked: 625 times
- Followed by:119 members
- GMAT Score:780
I actually took the first interpretation: they do mean that each key is a skeleton key that works in any of the five locks. From there, I took the minimum as the fewest (cleverly chosen) trials we'd need to run to prove this to a skeptical observer and the maximum as the worst (= longest) scenario of all the scenarios in which we pick x random and distinct arrangements and are forced to run all x to see that the keys are all skeleton.Ian Stewart wrote:This should be an SC question. They don't mean "each key matches each lock" (which would mean every key works in any lock you choose). Instead they mean each key matches a different one of the locks.NandishSS wrote:There are 5 locks and 5 keys and each of the 5 keys matches each of the 5 locks. What is the minimum and the maximum trial numbers of attempts needed to confirm that each of the 5 keys matches each of the 5 locks?
A. 5,15
B. 4,15
C. 5,10
D. 4,10
E. 5,20
OA: D
Source: Math Revolution
(That wasn't well put, but you get the idea: we run x random and distinct arrangements, with x not determined beforehand, and only after running exactly x random and distinct arrangements do we see that the keys are skeleton, with the maximum being the greatest possible value of x. In other words, if the answer is, say, 15, then any 15 distinct random arrangements MUST force the conclusion that the keys are skeleton, and there is some set of 14 distinct random arrangements that does NOT force that conclusion.)
Taken that way, I thought it was a neat question, but probably one too difficult and time consuming for the GMAT. (Just the minimum seems fine to ask, though.)
- DavidG@VeritasPrep
- Legendary Member
- Posts: 2663
- Joined: Wed Jan 14, 2015 8:25 am
- Location: Boston, MA
- Thanked: 1153 times
- Followed by:128 members
- GMAT Score:770
That is a neat way of thinking about this question. I suspect that the problem was very loosely inspired by the following official problem: https://www.beatthegmat.com/gmat-prep-ps ... 10570.htmlMatt@VeritasPrep wrote:I actually took the first interpretation: they do mean that each key is a skeleton key that works in any of the five locks. From there, I took the minimum as the fewest (cleverly chosen) trials we'd need to run to prove this to a skeptical observer and the maximum as the worst (= longest) scenario of all the scenarios in which we pick x random and distinct arrangements and are forced to run all x to see that the keys are all skeleton.Ian Stewart wrote:This should be an SC question. They don't mean "each key matches each lock" (which would mean every key works in any lock you choose). Instead they mean each key matches a different one of the locks.NandishSS wrote:There are 5 locks and 5 keys and each of the 5 keys matches each of the 5 locks. What is the minimum and the maximum trial numbers of attempts needed to confirm that each of the 5 keys matches each of the 5 locks?
A. 5,15
B. 4,15
C. 5,10
D. 4,10
E. 5,20
OA: D
Source: Math Revolution
(That wasn't well put, but you get the idea: we run x random and distinct arrangements, with x not determined beforehand, and only after running exactly x random and distinct arrangements do we see that the keys are skeleton, with the maximum being the greatest possible value of x. In other words, if the answer is, say, 15, then any 15 distinct random arrangements MUST force the conclusion that the keys are skeleton, and there is some set of 14 distinct random arrangements that does NOT force that conclusion.)
Taken that way, I thought it was a neat question, but probably one too difficult and time consuming for the GMAT. (Just the minimum seems fine to ask, though.)
GMAT/MBA Expert
- Ian Stewart
- GMAT Instructor
- Posts: 2621
- Joined: Mon Jun 02, 2008 3:17 am
- Location: Montreal
- Thanked: 1090 times
- Followed by:355 members
- GMAT Score:780
As Matt says, this won't be relevant to GMAT test takers, so no need to worry about any of this if you're preparing for the test, but I find it fun to sometimes talk about math problems that are beyond the scope of the test:
The answer to that question should be 97. There are 5! = 120 ways to match the keys to the locks in general. In 1/5 of those ways, we match the first key to the first lock. So in 4/5 of those ways, or 96 ways, we do not try the first key in the first lock. We need to do that to prove our keys are skeleton keys, so if by bad luck we don't do that in the first 96 trials, we will surely do it on the 97th. But if we do 97 trials, every key must have been tried in every lock at some point, essentially by the pigeonhole principle (once we've tested more than 4/5 of possible arrangements, everything must have been tried everywhere at some point).
David (sorry to 'demolish' the problem ) - you're probably familiar with this already, but that GMATPrep problem is a simple example of a class of combinatorics problems known as 'derangement' problems, where you're interested in how many ways you can rearrange, say, the letters in ABCD where no letter remains in its original place. These get complicated quickly - with even just five letters, it would be well beyond GMAT-level math to ask a derangement question, so the GMAT version of the question, with only 4 letters, is really the only version you could ever see on the test (with fewer letters the question isn't that interesting). The question in the OP above isn't really a derangement problem, but it may have been inspired by one.
That is an interesting question, though it does have a fast solution, if I'm understanding it correctly: we have 5 keys, and 5 locks, and we want to prove that each key opens every single lock. We're going to randomly try five keys in five locks in each trial, and once we've done a trial, we will never repeat it. If we keep doing trials, what is the maximum number of trials we might need to do before we have tried every key in ever lock?Matt@VeritasPrep wrote: I actually took the first interpretation: they do mean that each key is a skeleton key that works in any of the five locks. From there, I took the minimum as the fewest (cleverly chosen) trials we'd need to run to prove this to a skeptical observer and the maximum as the worst (= longest) scenario of all the scenarios in which we pick x random and distinct arrangements and are forced to run all x to see that the keys are all skeleton.
(That wasn't well put, but you get the idea: we run x random and distinct arrangements, with x not determined beforehand, and only after running exactly x random and distinct arrangements do we see that the keys are skeleton, with the maximum being the greatest possible value of x. In other words, if the answer is, say, 15, then any 15 distinct random arrangements MUST force the conclusion that the keys are skeleton, and there is some set of 14 distinct random arrangements that does NOT force that conclusion.)
Taken that way, I thought it was a neat question, but probably one too difficult and time consuming for the GMAT. (Just the minimum seems fine to ask, though.)
The answer to that question should be 97. There are 5! = 120 ways to match the keys to the locks in general. In 1/5 of those ways, we match the first key to the first lock. So in 4/5 of those ways, or 96 ways, we do not try the first key in the first lock. We need to do that to prove our keys are skeleton keys, so if by bad luck we don't do that in the first 96 trials, we will surely do it on the 97th. But if we do 97 trials, every key must have been tried in every lock at some point, essentially by the pigeonhole principle (once we've tested more than 4/5 of possible arrangements, everything must have been tried everywhere at some point).
David (sorry to 'demolish' the problem ) - you're probably familiar with this already, but that GMATPrep problem is a simple example of a class of combinatorics problems known as 'derangement' problems, where you're interested in how many ways you can rearrange, say, the letters in ABCD where no letter remains in its original place. These get complicated quickly - with even just five letters, it would be well beyond GMAT-level math to ask a derangement question, so the GMAT version of the question, with only 4 letters, is really the only version you could ever see on the test (with fewer letters the question isn't that interesting). The question in the OP above isn't really a derangement problem, but it may have been inspired by one.
For online GMAT math tutoring, or to buy my higher-level Quant books and problem sets, contact me at ianstewartgmat at gmail.com
ianstewartgmat.com
ianstewartgmat.com
- DavidG@VeritasPrep
- Legendary Member
- Posts: 2663
- Joined: Wed Jan 14, 2015 8:25 am
- Location: Boston, MA
- Thanked: 1153 times
- Followed by:128 members
- GMAT Score:770
I'm ashamed to admit that I wasn't familiar with the term, but you sent me down a delightfully enlightening Wikipedia wormhole.David (sorry to 'demolish' the problem Smile ) - you're probably familiar with this already, but that GMATPrep problem is a simple example of a class of combinatorics problems known as 'derangement' problems, where you're interested in how many ways you can rearrange, say, the letters in ABCD where no letter remains in its original place. These get complicated quickly - with even just five letters, it would be well beyond GMAT-level math to ask a derangement question, so the GMAT version of the question, with only 4 letters, is really the only version you could ever see on the test (with fewer letters the question isn't that interesting). The question in the OP above isn't really a derangement problem, but it may have been inspired by one.