Five keys, five doors, seven guards, and only seven questions

Question

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?

Answer 1

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.

Answer 2

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:

3. 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:

4. Is E < C?

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

5. 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):

6. Is B < C?

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

7. 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.

Answer 3

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?

Answer 4

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$.

4. 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$.

5. Is $o_1 = 1$?
6. Is $o_1 = 3$? (unnecessary if previous answer is "yes")
7. 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.

Answer 5

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

Answer 6

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

4. 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:

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

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

7. 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:

5. Ask if E is in the middle.

E is in the middle:

It's one of these three cases:

ABECD
ACEBD
ACEDB

6. "Does B go to door 2?" - Yes = ABECD
7. "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,

6. Ask if E goes to door 1 or 2
7. 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