Tuesday, August 28, 2007

23 prisoners problem, brutal solution and analysis

Problem abstract

23 prisoners are going to be sent to isolated 23 cells and in each day, the guard will randomly pick one of them and have him change the status(either on or off) of one of two switches(switch A and B). The guard promises that if one day the prisoner he picks looks at the two switch, confidently tells that all 23 prisoners have been picked in past and it's truth, then all prisoners are set free. If the prisoner is wrong, game is over and they stay in prison for ever. Before the game begins, 23 prisoners have one chance to sit together and figure out a strategy to go free. (Detailed version)

Quick analysis

1. Since each prison HAS TO change one of the switch, his decision is not "which combination to change to", but "which switch to turn". Therefore his decision is only one out of two: changing switch A vs. changing switch B.
2. The information that two switches can contribute is 2 bit a time. At any given moment, for a prisoner to tell if everyone has been picked(one special case out of 2^22 cases), the minimal input is a 22 bit binary sequence. Therefore the prisoner has to have be picked for 11 time at least before he can tell. And this is for the very ideal case without any noise whatsoever, in theory.

The brutal force solution

The first solution came to my mind was brutal force.

1 prisoner is elected to be the Mr. Counter and other 22 report themselves. Take switch A as counting switch. Every time Mr. Counter is picked, if he sees A is on(someone has reported), he turns off A(reset counting switch) and increase the number in his mind. If A is off he changes B and doesn't do anything. For the other 22 people, if A is off(nobody has reported yet) and he hasn't reported before, he turns A on to report himself. Otherwise changes B.

In this solution, the counter has to have been picked for at least 22 times before he can draw the conclusion. The efficiency sounds really low.

Analyze the efficiency

Nothing happens for sure. From now on, the estimate time is always "the time it takes before happening 80% for sure).
At any given moment, if it takes N days before Mr. Counter is picked,
1.0 - (22/23)^N = 0.8
N = log5 / (log23 - log22) = 36
This means Mr. Counter is 80% likely going to be picked in next 36 days at any given moment. And of course, the average life cycle is 23 days, for which I'll talk about in the end.

At the very beginning of the game, before Mr. Counter is called, chance is 100% for one of the other 22 to report himself. After Mr. Counter reset counting switch for the first time, there's 1 - (1/22)^36 chance for the second prisoner to report. After counter switch is reset for N times, chance for next person to report is 1 - (N/22)^36. Even for the last person, the chance for him to miss is about 18%.

So the conclusion for brutal force approach is, it takes a little more time for Mr. Counter to be picked for 22 times before Mr. Counter confidently know all other 22 prisoners have been picked before. How much more than that? It is 80% likely

((1/22)^36 + (2/22)^36 + (3/22)^36 + ... (21/22)^36) * 36 (days)
~= ((21/22)^36 + (20/22)^36) * 36(days) ~= 8 (days)
X = 36(days) * 22 + 8 = 800 (days) totally
It 80% likely takes 800 days for Mr. Counter to figure out. By average, it takes 23 days rather than 36 days for a person to be picked. If I replace all 36(days) with 23(days) and start over again, the average result is actually 514 days. The most magical solution based on prior analysis is 11*36 = 396 (days) for 80% and 11*23 = 253 (days) as average. Considering the noise, the brutal force solution isn't bad at all.

BenVitale said...

This almost works. The only problem is that we don't know the initial condition of the switches... it's plausible that they were both in the on position first

Jiaqi Guo said...

If they don't know the initial states ... this won't work, the counter can miscount by up to 1 person.

I'm sure there's better solution out there. Any suggestions?

BenVitale said...

Because there are two bits, the switches can represent the numbers 0,1,2,3 in binary, and it is possible for each person to flip a switch and either change the parity of the number, or leave it unchanged. For instance one flip will take 0 to 2, or 0 to 1; 1 to 0 or 1 to 3; 2 to 0 or 2 to 3, etc.

Try working out a protocol where each prisoner knows what to do when he finds a given parity for the first, second, third,.... time he enters the room.

BenVitale said...

Hmm... unfortunately the parity of the initial conditions the switches can be in is random. This solution is very similar to the idea you had before - flip the first switch and change the parity on the first time you enter the room, flip the second switch and leave the parity constant otherwise.