10
$\begingroup$

Trapped in a dungeon, you have found five keys, labeled A, B, C, D, and E. You have five locked doors, one in front of the other, numbered 1, 2, 3, 4, and 5. To escape, you must open all five doors. Each key opens exactly one door. The keyholes are coated with glue, so once a key is inserted, it can never be removed. Therefore, you must determine which key should be used for each door.

There are seven guards, all of whom are sympathetic and will help you leave. Still, they are nervous about being caught enabling your escape. Each one will answer just one yes-or-no question. All of the guards know which key goes with each door, and will answer either yes or no to the best of their knowledge.

The guards are impatient. After each answer you receive, you must ask the next question within about five seconds. Furthermore, the questions should be fairly simple, such as "Is B's door even?" The guards are not expert logicians or mathematicians, and will give up (and run away) if a question takes more than a minute for them to answer.

What questions should you ask?

$\endgroup$
  • $\begingroup$ Do you just need to get 1 door-key combo right (the one that lets you out) or do you need all 5 door-key combinations or by "one in front of the other" do you mean that there are 5 sequential walls with a door in each? $\endgroup$ – JonTheMon Apr 30 '15 at 21:51
  • $\begingroup$ As stated, "you must determine which key should be used for each door." $\endgroup$ – Ypnypn Apr 30 '15 at 21:57
  • $\begingroup$ Do these questions need to be the same for every scenario, or can we determine which question to ask depending on the previous answer? I understand you said it had to be said within five seconds, but it's possible our prisoner is a genius. $\endgroup$ – Cubicon May 1 '15 at 3:59
  • $\begingroup$ Is it ok to spam all possible questions? Like does A fit in here, what about B, what about C... $\endgroup$ – the4seasons May 1 '15 at 14:56
  • $\begingroup$ @Cubicon Yes, the prisoner can be very intelligent (but he's still human). $\endgroup$ – Ypnypn May 1 '15 at 17:04
10
$\begingroup$

As @JonTheMon said, there are $5!=120$ possible combinations for the keys. The correct ordering must be in this list:

1: ABCDE
2: ABCED
3: ABDCE
4: ABDED
5: ABECD
6: ABEDC
...
115: EDABC
116: EDACB
117: EDBAC
118: EDBCA
119: EDCAB
120: EDCBA

So, before you start asking questions, create this list since it is probably too hard to do on the fly.

Then, go to the first guard and ask the following:

Is the correct order of keys alphabetically after [ordering for #60] in a dictionary?

The first guard will answer either yes or no. If yes, repeat the question with ordering #90. If no, then ask with ordering #30.

Each question will narrow the range half, unless the range is odd, in which case you might be left with half-plus-one.

The following is the worst case progression (answer of no each time)

Question 1: Ask #60 on [1-120] -> [1-60]
Question 2: Ask #30 on [1-60]  -> [1-30]
Question 3: Ask #15 on [1-30]  -> [1-15]
Question 4: Ask #8  on [1-15]  -> [1-8]
Question 5: Ask #4 on  [1-8]   -> [1-4]
Question 6: Ask #2 on  [1-4]   -> [1-2]
Question 7: Is #2 the correct order?

At the end, you will know the ordering (either #1 or #2 in this example), so simply use the keys in order and open the doors.

$\endgroup$
6
$\begingroup$

Trenin's answer simply lists all the permutations in alphabetical order and does a binary search. It works, with the only drawback that memorizing (or computing on the fly) the index of all the possibilities is difficult, and that it assumes that the guards can handle questions like "Is ABDCE alphabetically before ACDBE?"

Here's a method that asks only questions of the form "Is the door for key X < door for key Y"?

Start with:

  1. Is A < B?
  2. Is C < D?

You now know two lesser ones and two greater ones. Ask a comparison for the two lesser ones.

For example, if A < B and C < D, ask:

  1. Is A < C?

Whichever one is less must now be the least of the four. You now have an ordered chain of 3 keys, plus a fourth that you only know is not the first door. So if A < C, then you know A < C < D, or if C < A, then you know C < A < B.

For your fourth question, compare E to the middle one in the chain. For example:

  1. Is E < C?

Then compare E to the appropriate end of the chain. So if E < C, then:

  1. Is E < A?

So, after five questions you have identified a chain of four (e.g. AECD), and a fifth door that gets inserted somewhere not in the first position. That leaves four more possibilities, which is good, because you have two more questions.

Compare the extra key to the third key in your chain (e.g., for above example):

  1. Is B < C?

Then compare the extra to the second or fourth. For example, if A < E < C < D, and B < C, ask:

  1. Is B < E?

This path guarantees that you will get the correct ordering in seven questions. There are a few arrangements where the seventh question is unnecessary.

Remembering an ordered chain should be much easier than trying to memorize the indexing of 120 permutations.

Counting details: Questions 1, 2, and 3 are guaranteed to be independent and thus reduce the number of possibilities from 120 down to 15. Question 4 splits that evenly into 7 possibilities (for yes) or 8 possibilities (for no). The last three questions split the remaining possibilities evenly.

$\endgroup$
  • 1
    $\begingroup$ I'm not dissing Trenin's answer, which I think is clever and good. I just wanted to share a different answer, and acknowledge that they got theirs in first. $\endgroup$ – user3294068 May 1 '15 at 18:34
  • 1
    $\begingroup$ Hmm, so you do a pseudo-merge sort with the first 3 steps, then 2 consecutive 2-step binary sorts? $\endgroup$ – JonTheMon May 1 '15 at 18:49
  • $\begingroup$ @JonTheMon: The five-item sort case is interesting because 5! is just slightly below a power of 2, and no better number appears until a 22-item sort (using 70 questions). $\endgroup$ – supercat May 1 '15 at 22:36
  • $\begingroup$ I like this answer because unlike mine, you don't really have to write anything down. And even if you do, you are only writing a small amount. Very easy to memorize and do quickly with a bit of practice. +1 from me! $\endgroup$ – Trenin May 4 '15 at 17:48
2
$\begingroup$

Ask the first guard if the first door opens with keys A or B then ask the next guard if the next door opens with keys B or C and continue in that fashion (repeat after key E and/or door 5):

Doors: 1 to 5 | Keys: A to E | Guards/Questions: 8

Keys (made up combo): CBEAD

Ask is door:

  • 1 opened with either keys A or B - Answer: No
  • 2 opened with either keys B or C - Answer: Yes
  • 3 opened with either keys C or D - Answer: No
  • 4 opened with either keys D or E - Answer: No
  • 5 opened with either keys A or B - Answer: No
  • 1 opened with either keys B or C - Answer: Yes
  • 2 opened with either keys C or D - Answer: No
  • 3 opened with either keys D or E - Answer: Yes

Summary:

  • 1 must be C
  • 2 must be B
  • 3 must be E
  • 5 must be D
  • 4 must be A

Another Example (just for assurance, with new format):

Keys (made up combo): BDCEA

Ask is door (x) opened with two keys (k, k+1) for 8 questions:

  • x = 1, k = {A or B} - result:true
  • x = 2, k = {B or C} - result:false
  • x = 3, k = {C or D} - result:true
  • x = 4, k = {D or E} - result:true
  • x = 5, k = {A or B} - result:true
  • x = 1, k = {B or C} - result:true
  • x = 2, k = {C or D} - result:false
  • x = 3, k = {D or E} - result:false

Summary:

  • 1 = B
  • 3 = C
  • 5 = A
  • 2 = D
  • 4 = E
$\endgroup$
  • $\begingroup$ @Ian If my method is sound (which I believe it is, though there could be an unforeseeable limitation to it but I don't have a million years to test it) then is it the method that you had in mind? Did you have a method in mind? $\endgroup$ – Daedric Apr 30 '15 at 23:29
  • $\begingroup$ You have asked one too many questions, I think. $\endgroup$ – Ian MacDonald May 1 '15 at 0:39
  • $\begingroup$ Lol sorry I thought you said 8 guards, ill fix it as soon as I can $\endgroup$ – Daedric May 1 '15 at 10:49
  • $\begingroup$ @Daedric Even with 8 guards I don't think your method works for ECABD $\endgroup$ – Warlord 099 May 1 '15 at 14:20
  • $\begingroup$ True thx for that :) I'll think of something else. $\endgroup$ – Daedric May 1 '15 at 14:24
1
$\begingroup$

Assuming there are 5 doors in a row and you have to open 1 before you get to the next, and there are 5! combinations of keys and doors, just assign each order of keys a number (120 total) and do a binary mapping question to each guard.

That does mean you have to say "Is the combination 12345 or 12354 or...." for up to 64 guesses for each guard, so that might be too much for the guards. They only have to say if the hear the correct combo, so maybe it's fine?

$\endgroup$
  • 1
    $\begingroup$ Seems like you could speed up the initial portion by asking "From left to right, does 1 come before 2?" and "From left to right, does 3 come before 4?" Then, if 1 and 3 are the farther left of the two doors, you could ask "From left to right, does 1 come before 3?" or the equivalent. Each question must cut the total in half by symmetry, so you'd be down to 15 possibilities, and you'd only have to ask up to 8 guesses per guard from there. $\endgroup$ – Tyler Seacrest Apr 30 '15 at 22:16
  • $\begingroup$ @TylerSeacrest Can you formalize that in an answer? I'd like to see the decision tree for this one. $\endgroup$ – Trenin May 1 '15 at 11:46
  • $\begingroup$ What about question of this form: If the keys are in order, would the solution come before/after X in a dictionary? The keys are lettered. $\endgroup$ – Trenin May 1 '15 at 11:50
  • $\begingroup$ @Warlord099 Each guard just has to listen for the right combination out of your guess then say if it was in the group or not. $\endgroup$ – JonTheMon May 1 '15 at 13:14
  • $\begingroup$ @Trenin so, you have an ordered list of all combinations (at least in your head) and you essentially do a binary search? $\endgroup$ – JonTheMon May 1 '15 at 13:18
1
$\begingroup$
  1. Is $A$ even?
  2. Is $B$ even?
  3. Is $C$ even? (unnecessary if they answered "yes" twice)

Now at least one even key has been found (as either a "yes" answer, or as $D$ and $E$). Choose one $e_1$.

  1. Is $e_1 = 2$? ("yes" means $e_1=2$ and $e_2=4$, "no" is opposite)

Now we only have to find the odd doors. Choose a key $o_1$.

  1. Is $o_1 = 1$?
  2. Is $o_1 = 3$? (unnecessary if previous answer is "yes")
  3. Is $o_2 = 3$? (or $5$ if previous answer was yes)

This allows us to match up all of the keys.

Note: further proof is required for completeness, but I'm answering from my phone and it has a shattered screen at the moment.

$\endgroup$
  • 1
    $\begingroup$ I think you need to ask "Is X even?" at most 4 times. Otherwise you could get two 'no' and one 'yes' response, and not be able to figure out exactly which remaining key is the even one. Correct me if I'm wrong. $\endgroup$ – itriedacrab Apr 30 '15 at 22:24
  • $\begingroup$ If they say A is even, and then B and C are not, you don't know whether D or E is the other even. This means you're going to need an extra question along the way unless you get lucky and $o_1=1$. $\endgroup$ – Glen O May 1 '15 at 2:21
  • $\begingroup$ I know. I haven't had time to refine this yet. $\endgroup$ – Ian MacDonald May 1 '15 at 5:07
  • $\begingroup$ @Lawrence, hello. You have written the same thing that both itriedacrab and Glen O wrote. I responded to this already. $\endgroup$ – Ian MacDonald May 1 '15 at 13:38
1
$\begingroup$

As @JonTheMon and @Trennin said, there are 120 possibilities so we need to eliminate about half at each step. Here's a decision tree that allows you do that without having to either ask each guard about a whole bunch of possibilities or write down the full list of 120 options in advance:

  1. Pick two keys (1 and 2) and ask "Does key 1 go to a door to the left of key 2?" Label the left key "A" and the right key "B".
  2. Pick another two keys (3 and 4) and ask the same question about those keys. Call the left key "C" and the right key "D".
  3. Ask the same question about keys A and C. If C is to the left of A, swap the labels of the pairs (A,B) and (C,D).

At this point, we have four keys and we know A is to the left of B and C, and C is to the left of D. An easy way to keep track of this would be to place them on the ground in like this:

A -> B
|
V
C -> D
  1. Ask "Does either C or D go to the door in the middle?"

At this point the questions we need to ask (rather than which keys we need to ask about) change depending on the result. So rather than renaming/rearranging keys, we'll have the tree actually split.

If C or D is in the middle:

  1. Find where E is - ask if it goes to one of the first two doors to narrow it down to one of two doors.

  2. Ask about one of the two doors E could go to. You now know where E is.

  3. Ask if B is to the left of D.

You now have enough information to determine the order! If E goes door 1 or 2, then from left to right the doors are:

(A and E)C(B and D)

If E goes to door 4 or 5, then if B is to the left of D:

ABCED or ABCDE (ABCD with E inserted)

If B is to the right of D:

ACDEB or ACDBE (ACDB with E inserted)

If C and D are not in the middle:

  1. Ask if E is in the middle.

E is in the middle:

It's one of these three cases:

ABECD
ACEBD
ACEDB
  1. "Does B go to door 2?" - Yes = ABECD
  2. "Does B go to door 4?" - Yes = ACEBD, No = ACEDB

E's not in the middle either:

This means B is in the middle (A is to the left of too many doors to be in the middle). We've got these cases left:

ACBDE
ACBED
AEBCD
EABCD

Looks like we can identify the case by finding which door E goes to. As with the case of C or D being in the middle,

  1. Ask if E goes to door 1 or 2
  2. If yes, ask if it goes to door 1. If no, ask if it goes to door 3.

Here's how the cases correspond to the answers:

ACBDE - No, No
ACBED - No, Yes
AEBCD - Yes,No
EABCD - Yes,Yes
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.