Skip to main content

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.

Comments

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
10:21 PM
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?
10:30 PM
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.
8:06 PM
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.
10:55 PM
Post a Comment

Popular posts from this blog

Spring, Angular and other reasons I like and hate Bazel at the same time

For several weeks I've been trying to put together an Angular application served Java Spring MVC web server in Bazel. I've seen the Java, Angular combination works well in Google, and given the popularity of Java, I want get it to work with open source. How hard can it be to run arguably the best JS framework on a server in probably the most popular server-side language with  the mono-repo of planet-scale ? The rest of this post walks through the headaches and nightmares I had to get things to work but if you are just here to look for a working example, github/jiaqi/angular-on-java is all you need. https://github.com/jiaqi/angular-on-java Java web application with Appengine rule Surprisingly there isn't an official way of building Java web application in Bazel, the closest thing is the Appengine rule  and Spring MVC seems to work well with it. 3 Java classes, a JSP and an appengine.xml was all I need. At this point, the server starts well but I got "No ...
Post a Comment
Read more

Customize IdGenerator in JPA, gap between Hibernate and JPA annotations

JPA annotation is like a subset of Hibernate annotation, this means people will find something available in Hibernate missing in JPA. One of the important missing features in JPA is customized ID generator. JPA doesn't provide an approach for developer to plug in their own IdGenerator. For example, if you want the primary key of a table to be BigInteger coming from sequence, JPA will be out of solution. Assume you don't mind the mixture of Hibernate and JPA Annotation and your JPA provider is Hibernate, which is mostly the case, a solution before JPA starts introducing new Annotation is, to replace JPA @SequenceGenerator with Hibernate @GenericGenerator. Now, let the code talk. /** * Ordinary JPA sequence. * If the Long is changed into BigInteger, * there will be runtime error complaining about the type of primary key */ @Id @Column(name = "id", precision = 12) @GeneratedValue(strategy = GenerationType.SEQUENCE, generator = "XyzIdGenerator") @SequenceGe...
4 comments
Read more

Project Euler problem 220 - Heighway Dragon

This document goes through a Java solution for Project Euler problem 220 . If you want to achieve the pleasure of solving the unfamiliarity and you don't have a solution yet, PLEASE STOP READING UNTIL YOU FIND A SOLUTION. Problem 220 is to tell the coordinate after a given large number of steps in a Dragon Curve . The first thing came to my mind, is to DFS traverse a 50 level tree by 10^12 steps, during which it keeps track of a direction and a coordinate. Roughly estimate, this solution takes a 50 level recursion, which isn't horrible, and 10^12 switch/case calls. Written by a lazy and irresponsible Java engineer, this solution vaguely looks like: Traveler traveler = new Traveler(new Coordinate(0, 0), Direction.UP); void main() { try { traverse("Fa", 0); } catch (TerminationSignal signal) { print signal; } } void traverse(String plan, int level) { foreach(char c:plan) { switch(c) { case 'F': traveler.stepForward(); break; ca...
Post a Comment
Read more