Prison Switcharoo

If you enjoy non-trivial puzzles such as this, I strongly recommend Peter Winkler’s book _Mathematical Puzzles: A Connoisseur’s Collection_. It contains two variants of this problem. The easier of the two, _The One-Bulb Room_, has essentially the same solution as this one.<p>On the other hand, the harder one is really considerably harder! Here it is, _The Two-Bulb Room_:<p>“Each of n prisoners will be sent alone into a room, infinitely often, but in some arbitrary order determined by their jailer. There are two lights in the room, each with its own binary switch. There will be no means of communication other than these switches, whose initial states are not known. The prisoners again have a chance to confer in advance.<p>Again, we want to ensure that some prisoner will eventually be able to deduce that everyone has visited the room. What, you did it before with only _one_ switch? Ah, but this time, every prisoner must follow the same set of rules.”

What a fun puzzle! The &quot;ah-ha&quot; moment is realizing that the brains of the prisoners can be be used to store the state, and not just the panel of switches. My initial reaction was to think about the storage capacity of the switch panel, and immediately hit a wall because clearly you can&#x27;t store 26 bits in 2 switches. So you have to go hunting for another place to maintain state - and of course in the head of one of the prisoners is a great place!

There is a very interesting paper which solves the problem when there are 100 prisoners, and there is only one lightswitch and one light bulb. It&#x27;s like an exercise in communication over the lowest bandwidth channel imaginable. Some of the schemes get fairly complicated, and there are some difficult probability analyses on time-to-escape.<p><a href="http://www.segerman.org/prisoners.pdf" rel="nofollow">http:&#x2F;&#x2F;www.segerman.org&#x2F;prisoners.pdf</a>

The answer: <a href="http://www.cartalk.com/content/prison-switcharoo-0?answer" rel="nofollow">http:&#x2F;&#x2F;www.cartalk.com&#x2F;content&#x2F;prison-switcharoo-0?answer</a>

This was a fun problem. On the other hand, I felt cheated when Vidit Drolia of Yammer gave this problem and expected it to be common knowledge enough to be solved in 3 minutes. Don&#x27;t think it&#x27;s quite that much of a valid interview problem.

Here&#x27;s the best solution I&#x27;ve heard for this:<p>The prisoners meet together and designate a leader. The leader will maintain a tally. They also designate one of the switches to not matter. The prisoners then use the following strategy:<p>When a prisoner is lead to the room, if the designated switch is off and it is the prisoner&#x27;s first time flipping the relevant switch, it is turned on. Else, flip the irrelevant switch. If the prisoner is the designated leader, and the relevant switch is on, he adds a count to his tally and turns the relevant switch off. Otherwise he just flips the irrelevant switch. This way, once the leader has seen the light be on a sufficient number of times he can definitively say that they have all been in the room.

I love puzzles like the ones that Click and Clack showcase on Car Talk (NPR). The Sunday Puzzle (<a href="http://www.npr.org/series/4473090/sunday-puzzle" rel="nofollow">http:&#x2F;&#x2F;www.npr.org&#x2F;series&#x2F;4473090&#x2F;sunday-puzzle</a>) by Will Shortz is also another source of challenging word puzzles. Games Magazine and Martin Gardner&#x27;s columns in Scientific American are&#x2F;were also fantastic reads for games and puzzles.<p>What other sources of word&#x2F;math&#x2F;logic puzzles are out there?

Although the supplied answer guarantees that no prisoner will die from alligators, it does not guarantee their freedom.<p>The answer includes a major (and I believe flawed) assumption, which is that the visits will be uniformly distributed. However, the puzzle states that &quot;I may choose the same guy three times in a row&quot;.<p>The Counter could visit the switch room 44 times without flipping the switch if such visits were the first 44 chosen. After everyone visits (which would be 1,012 visits since &quot;given enough time, everyone will eventually visit the switch room as many times as everyone else&quot;), the Counter will be no closer to knowing the truth.<p>Of course, it is true that the greater the number of visits the greater the probability that the Counter&#x27;s final visit will fall after everyone has visited, but there is no guarantee.<p>Regardless of how many visits you assume for each prisoner, there will always remain a probability that the Counter&#x27;s visits will be clustered early in the visitations. In such a scenario, the Counter&#x27;s role becomes useless and all prisoners will die in prison.

The solution assumes no prisoners die before they flip A twice. No fault tolerance : p

In the version where one prisoner is taken in per day, the solution can be drastically simplified if it is agreed that the prisoner who is taken into the first day is the counter.<p>That case only requires flipping switch a off 22 times after the first day.<p>Obviously, removing that single bit of information makes the solution much harder to find, but adding then later removing it makes discovering the solution a more iterative thing. Which is desirable if, for example, you&#x27;re giving these puzzles to your kids.

Is it me or does this solution rely on the belief in a certain order to the random picking of prisoners? If the counter switches to an off state 44 times, that doesn&#x27;t tell him that all 22 other prisoners gave toured through the room. A guard (random algorithm) could have just selected the same two prisoners -- the counter and another guy -- 22 times. Am I missing something?

This is mostly an instance of a class of problem discussed in more depth here: <a href="http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1177584051" rel="nofollow">http:&#x2F;&#x2F;www.ocf.berkeley.edu&#x2F;~wwu&#x2F;cgi-bin&#x2F;yabb&#x2F;YaBB.cgi?board...</a><p>I say mostly because the bit where one switch must be toggled and there are 2 switches makes it a bit different from 23C2. I don&#x27;t think the difference is useful, though; the set of solutions is probably the same as the solution set for 23C2.

Since there&#x27;s a password article on the front page too...<p>This problem is very clever, and there is a very clever way to solve this, assuming everyone plays nice. However, that solution assumes perfect collusion. These are prisoners we&#x27;re talking about, so at least in some cases, we have to assume there may be bad actors involved. I mean this is a cute problem assuming the following:<p>1. All the prisoners have perfect memory (for this problem)<p>2. All the prisoners actually want to live.<p>3. The warden is telling the truth<p>4. The guards are all honest.<p>These are all the type of assumption that gets websites hacked. So what is the attack surface here?<p>* One of the prisoners decides this is a fun way to suicide<p>* One of the prisoners is in gang A, and one is in gang B. They value gang honor above their own life, and need to take out the other.<p>* A guard has decided that this is a great way to off some &quot;scum&quot;<p>* A prisoner forgets the algorithm, or hits the wrong switch, or other form of human error.<p>* As if_by_whisky points out: someone dies before the full run.<p>* The warden just wants to mess with people before feeding them to alligators, and just states &quot;wrong&quot; whenever someone declares all have visited.<p>* A prisoner can&#x27;t handle the stakes, and cracks and makes the declaration early.<p>* The leader messes up the count.<p>There are probably a lot more.<p>Further, the warden is making assumptions that we can&#x27;t be sure are true. Prisons are notorious for being bad at doing the actual security thing. Are there ways for prisoners to collude and do extra error checking on their end? Can a guard be bribed to help share state? Is there a way to get other prisoners involved in message passing, even if they manage to prevent direct collusion between the selected 23?<p>I don&#x27;t know a way around all of these. In fact I&#x27;m pretty sure there a some combinations where everyone is just fucked. But, what can be done to add robustness to this problem? It seems pretty silly for prisoners (likely malicious actors as a generalization) will follow the rules and stay within the constraints the warden sets out.<p>I ask, because I&#x27;ve solved plenty of things in a nice elegant way, that were trivially broken by not assuming everything will play nicely in the environment. Similarly I&#x27;ve broken plenty of &quot;awesome solutions&quot; by asking questions about assumptions. The difference between the algorithmic solution and the real world is sometimes surprisingly large. Just some food for thought :)

I had fun solving this today and wrote a dinky ruby program [1] to test my solution. Is there a better way to do this?<p>[1] <a href="http://pastebin.com/n0vHSdzm" rel="nofollow">http:&#x2F;&#x2F;pastebin.com&#x2F;n0vHSdzm</a>

The solution could take years, even decades to solve - all depending on how often the warden brings in a prisoner. I&#x27;d rather wait out my prison term, hope to be released early for good behavior.

Can&#x27;t they all meet in the switch room?

Can the prisoners tell if the switch is in the on or off position?