Friday Puzzler -- Find the Trustee

Re: Friday Puzzler -- Find the Trustee

Larry Barrett

Consider a simpler problem, with just 3 doors.

Case 1: In this case the prisoner's strategy will be to open door 2. If the key is there he leaves. If the key is not there, then it was in room 1 or 3, and in this case the warden will move it to an adjacent room, which will be room 2. So the prisoner should go back to open door 2 the second time, and he will find the key and leave.

Case 2:If he opens door 1 (or 3) the first time and the key is not there, then it must be in room 2 or 3. If in room 2, the warden will move it to room 1 (prob=1/2) or to room 3 (prob=1/2). If the key was in room 3 the warden will move it to room 2, the only available adjacent room. So the prisoner's best strategy is to open door 2 on his second try. If he finds it he leaves, else he is in the same situation as case 1.

So his best strategy is to first open door 2, and then open it again if the first try fails.

I suspect that a similar strategy will work for the case of 7 doors - start with the middle door, door 4, but have not thought it through. If the first try fails, then he could move to door 2 or door 6, the middle doors on either side of door 4.

Re: Friday Puzzler -- Find the Key

Alex Y

Correct analysis for the three-door version.

Hint -- Find the Key

Alex Y

The procedure for finding the key in the minimum number of days works for any number of doors.

And the number of days it takes is a linear function of the number of doors.

Re: Hint -- Find the Key

Larry Barrett

Two door problem:

Open door 1. If not there, then it was behind door 2 and will be moved behind door 1. So open door 1 again. Two tries.

Three door problem:

Open door 2. If not there, it will be behind door 1 or 3, and will be moved behind door 2. So open door 2 again. Total of two tries.

Four door problem:

Open door 2. If not there, it will be behind door 1,3, or 4. If behind door 1, it will be moved behind door 2. If behind door 3 it will be moved behind door 2 (p=1/2) or door 4 (p= 1/2). If behind door 4 it will be moved behind door 3.

Open door 2 again. If not there it will be behind door 3 or door 4. If behind door 3, it will be moved behind door 2 (p=1/2) or door 4 (p=1/2). If behind door 4 it will be moved behind door 3.

Open door 3. If not there it will be behind door 2 or door 4. If behind door 2, it will be moved to behind door 1 (p=1/2) or behind door 3 (p=1/2). If behind door 4 it will be moved behind door 3.

Open door 3 again. If not there it will be behind door 1, and will be moved behind door 2.

Open door 2. Total of 5 tries.

I don't see the 'key' yet, and not sure that the answer for the 4 door problem is minimum.

Suggested notation

Alex Y

It might be easier to see proposed solutions by using a string of characters for the state of the doors each day, with"?" for a door that may or may not have the key, "0" for a door that we know does not have the key, and "X" for the door chosen that day.

Your proposed solution for four doors can then be represented as:

????

?X??

0X??

0?X?

?0X0

0X00

The fifth X reveals the key if no earlier one did. You can do better.

Your solution for the case of two doors shows that I should have said that the number of tries is a linear function of the number of doors, FOR THREE OR MORE DOORS.

Re: Suggested notation

Larry Barrett

New attempt for the 4 door problem, using Alex notation:

????

?X??

O???

O?X?

?O?O

?OXO

OXOO

4 tries for 4 doors. And 2 tries for 3 doors. This might suggest 2(N-2) as a formula for minimum number of tries for N doors.

Re: Suggested notation - 5 door problem

Larry Barrett

Here is a solution for the 5 door problem:

1 2 3 4 5

? ? ? ? ?

? X ? ? ?

O ? ? ? ?

O ? X ? ?

? O ? ? ?

? O ? X ?

O ? O ? O

O ? O X O

? O ? O O

? O X O O

O X O O O

Six tries, so 2(N-2) looks like a good formula. Should take 10 tries for the 7 door problem.

Correct!

Alex Y

Six tries, so 2(N-2) looks like a good formula. Should take 10 tries for the 7 door problem.

And the pattern should be obvious at this point.