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.
On the other hand, the harder one is really considerably harder! Here it is, _The Two-Bulb Room_:
“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.
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.”
There are two differences. The first is a minor difference in the way it's formulated: in the OP’s version, the prisoner is obliged to flick one switch or the other when he’s sent into the room, whereas in this version he has the option of doing nothing.
The second difference is the one that makes this problem genuinely difficult, though: “Ah, but this time, every prisoner must follow the same set of rules.” In other words, the agreed strategy has to be the SAME for every prisoner.
Depending on whether the prisoners are able to determine the passage of time, this can either take relatively little time or a lot of time.
Easy: If the warden grabs a prisoner once a night, then the prisoners set up a system according to the passage of days.
Each prisoner starts with four "tokens." This means that in a prison population of 23 prisoners, there are 92 tokens in total for the prisoners.
We'll call the switches A and B. Starting off, A signifies 1 token. When you turn the switch on, you are putting a token into the switch. When you turn it off, you are taking one. B signifies 2 tokens.
When a prisoner visits the office, he looks to see if he can grab some tokens. If neither are on, then he puts in some tokens of his own. He will try to put as many tokens as possible in. So, for example, if he has 4 tokens, he will put in two.
Of course, if he has insufficient tokens, he does nothing.
After a predetermined period of time, the switches double in "worth." Switch A is now worth 2 tokens, and Switch B is worth 4. This will double again to 8 and 4, then 16 and 8, and so on, until they reach 64 and 32. If someone is able to accumulate 92 tokens, then it's apparent that everyone has visited the room at least once. Otherwise, it then starts over at 1 and 2.
We need four tokens for every prisoner because of a few possible extra tokens. If A and B are both on, then there are three extra tokens in the system. If you have fewer than four tokens per prisoner, it becomes possible to accumulate the required number without having everyone be in the room. You also can't have fewer tokens, because it would require that a prisoner collect tokens that might not actually be there.
Hard: If no one can figure out the passage of time, then they have to stay at 1 and 2. This will take much longer for someone to eventually accumulate all of the tokens, especially since all of them are trying to accumulate.
Edit: Here's a horribly written Python program that shows this process in action: http://codepad.org/iY121Ui3
What a fun puzzle! The "ah-ha" 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'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'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.
I'm a bit sleepy, but I can't get this to work. For 3 prisoners, what if the sequence is (P1 T P1 T P1 T P1 T P2 P2 P2 P2)? Where T is the tally keeper. They've all gone the same number of times (given enough time), but the tally keeper would declare that they had all flipped a switch before P2 had gone in at all. Thus, alligators.
Doesn't this solution make the assumption that the guard will continue to pick prisoners to enter the switchroom indefinitely? If he picked P1, P2, P1, P2, Counter, Counter, <end> would the solution still work?
This assumption is part of the original puzzle: "After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room."
I'm not seeing why they need to turn the switch ON twice. Couldn't they flip the switch only once and have the counter wait for <number of prisoners> ONs (N - 1 + 1)?
Because the switches start in an unknown state. So the first time the counter enters the room and sees switch A on he has no way to know if that's because another prisoner turned it on, or because he's the first one in the room and it started in the on position.
No, then he could have only counted 21 prisoners (43 = 1 initial + 21 * 2). The system will "stabilize" at either 44 or 45 "offs", depending on the initial state.
If switch A starts out in the ON position it would equal one 'fake' prisoner. If the counter just counts one extra (which equals p - 1 (himself) + 1 (fake prisoner) = p) it should be enough, no?
The issue is that the counter doesn't know the state of the first switch at the start. If it's on at the start, then sure your solution will work. But if it's off at the start and they all agree to only flip on the switch once, then the counter will sit around forever waiting for p flips, when only p - 1 will ever happen. They need a solution that will work no matter what state the switch is in at the start.
I don't see this working, if the prisoner who flipped the switch on is brought back into the room immediately after the counter turns it off, then that one prisoner will be assumed to be two different people.
> '"Now I want each of you to flick Switch A to the "On" position twice, and only twice. So if you go in there and Switch A is already on, that doesn't count. I want each of you to actually flick it "On" two times. You got that?"'
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't think it's quite that much of a valid interview problem.
Puzzles during the interview -- show others how smart you are by giving clever puzzles. Watch them struggle, make them feel bad for not figuring it out under pressure. Also accept lots of people who can google puzzle answers, or just are really good at solving puzzles. Which, works great if they are running a plumbing company and have to figure out good shapes for your manhole covers, a prison, or are just evil and like to shrink people and throw them into blenders.
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:
When a prisoner is lead to the room, if the designated switch is off and it is the prisoner'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.
"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the on or the off position. I am not telling you their present positions. The switches are not connected to anything.
The switches are not connected to anything, correct me if I am wrong but how will you find out light is on sufficient number of times
I love puzzles like the ones that Click and Clack showcase on Car Talk (NPR). The Sunday Puzzle (http://www.npr.org/series/4473090/sunday-puzzle) by Will Shortz is also another source of challenging word puzzles. Games Magazine and Martin Gardner's columns in Scientific American are/were also fantastic reads for games and puzzles.
What other sources of word/math/logic puzzles are out there?
Although the supplied answer guarantees that no prisoner will die from alligators, it does not guarantee their freedom.
The answer includes a major (and I believe flawed) assumption, which is that the visits will be uniformly distributed. However, the puzzle states that "I may choose the same guy three times in a row".
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 "given enough time, everyone will eventually visit the switch room as many times as everyone else"), the Counter will be no closer to knowing the truth.
Of course, it is true that the greater the number of visits the greater the probability that the Counter's final visit will fall after everyone has visited, but there is no guarantee.
Regardless of how many visits you assume for each prisoner, there will always remain a probability that the Counter's visits will be clustered early in the visitations. In such a scenario, the Counter's role becomes useless and all prisoners will die in prison.
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.
That case only requires flipping switch a off 22 times after the first day.
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're giving these puzzles to your kids.
I think you missed the part where he said "In the version where one prisoner is taken in per day", in which case it _is_ possible to know if you are the first to go into the switch room.
Ah, f*ck, thank you. I should sleep more. I still don't get how it works if Prisoner 2 is never at the switch at all before the Counter gets to his magic number, but I'm going to defer this to superior puzzle-solving minds :)
Because there's no limit to the amount of time they can play. Not just if P2 is never at the switch, but imagine even if the "counter" player is never at the switch too. Statistically, when talking about an infinite run-time, there's no such thing as "never". Even if it takes a million years, they'll eventually all get turns in the switch room.
Or, if you want to look at it more realistically, the run-time is limited by their lifespans I suppose. But given that they're prisoners who all presumably have life sentences, then they'll just play until they die, since the alternative is to simply be in prison until then anyway.
I knew why I always hated these games, because there are some rules which apparently aren't a big deal, while others seem to matter a lot.
In this case, the problem asked for a precise solution, which was given in the resolution example, with no thought at all to that nagging little probability problem. So in order to "solve" this, I would have to know that everybody is basically supposed to disregard certain aspects of the problem. That's gotcha-type stuff that I always get wrong.
What aspect is being disregarded? Previously you asked " Prisoner 2 is never at the switch at all before the Counter gets to his magic number" Except that if Prisoner 2 is never at the switch, the counter can never reach the magic number.
Assume there are 3 prisoners (1,2,C), the magic number is 4. But if the sequence is 1,C,1,C,1,C.... The count will never be greater than 3 (2 is the switch starts as off) The warden said everyone will eventually visit the room. The one thing that was assumed (but not spelled out explicitly) is the game goes on forever. Which means at some point 2 visits the room a bunch of times, and then C will visit again, and will meet the magic number.
Nothing to do with probability. And there is no guessing, 44 is a precise number.
By the "fairness rule" from the warden ("given enough time, everyone will eventually visit the switch room as many times as everyone else"), eventually every normal prisoner has to visit the switches.
I thought the fairness rule was basically just dice roll-equivalence. Which makes this whole "precisely 44 times" thing basically just a guess. It's a probabilities game but they pretend it has an exact solution.
It's not a probabilities issue. What's being counted is state changes---after 44, the counter knows that the condition has been satisfied. Fairness just guarantees that those state changes will happen.
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'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?
You are missing the cooperation of the other prisoners, they have agreed to only give information to the counter once no matter how many times they are sent into the room by the guard.
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't think the difference is useful, though; the set of solutions is probably the same as the solution set for 23C2.
Since there's a password article on the front page too...
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'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:
1. All the prisoners have perfect memory (for this problem)
2. All the prisoners actually want to live.
3. The warden is telling the truth
4. The guards are all honest.
These are all the type of assumption that gets websites hacked. So what is the attack surface here?
* One of the prisoners decides this is a fun way to suicide
* 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.
* A guard has decided that this is a great way to off some "scum"
* A prisoner forgets the algorithm, or hits the wrong switch, or other form of human error.
* As if_by_whisky points out: someone dies before the full run.
* The warden just wants to mess with people before feeding them to alligators, and just states "wrong" whenever someone declares all have visited.
* A prisoner can't handle the stakes, and cracks and makes the declaration early.
* The leader messes up the count.
There are probably a lot more.
Further, the warden is making assumptions that we can'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?
I don't know a way around all of these. In fact I'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.
I ask, because I'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've broken plenty of "awesome solutions" 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 don't think games are stupid. I just like them to be a bit in depth. Why would I spend time looking at a more interesting version of the game, how to cheat it, and how to add twists otherwise?
Also, if you want to take a game theory approach, you're wrong about the warden. If the warden is just playing a sadistic mind game, and wants to fuck with the players before feeding them to the alligators, the correct "solution" to the game for the players (should they catch on to the warden), is to never declare, thus extending the game infinitely, or barring that maximally, before the warden bores of the game and offs them.
Pretty much you've failed this on an intelligence level.
Give current society and the normal constraints on these popular games the answer to all the above are incredibly obvious, the answers you ask can be deducted. (No prisoner can die, if they could it would have been hinted at)
It's like claiming you can't do cryptic crosswords because the questions are not clear or don't follow proper English.
Although I imagine you are just trying to be difficult :)
Or maybe, since this is used as a "hire a programmer" question often, and has been for years, perhaps I just like discussing the very real difference between toy algorithm problems and the fact that algorithms don't exist in toy environments ever. In fact, I literally acknowledged the constraints and toy environment you're talking about in my post. Perhaps you should take a try at actually reading it, rather than insulting me because you think you're a clever person.
Oh almost forgot the smiley to indicate something or another sarcastic... :)
Since this problem comes around a lot as a programmer interview question, it seems like a good idea to discuss actual systems stuff associated with it. I mean, if I'm hiring a programmer I want them to be good at useful software, not at perfect condition algorithms.
The solution could take years, even decades to solve - all depending on how often the warden brings in a prisoner. I'd rather wait out my prison term, hope to be released early for good behavior.
Yes it does. It tells you that a randomly selected prisoner will be taken to the switch room and allowed to turn one of the switches on or off...and will then be led back to his cell.
There's no option for the prisoners to go to the switch room at the outset; they've just arrived at the prison and don't know where it is. So it would not be possible to meet up there, they have to wait for the prison guards to take them there individually.
Yes. The solution assumes that they can agree beforehand about what to call the states of at least 1 switch. I don't think there is a way to come to that agreement beginning the process.
On the other hand, the harder one is really considerably harder! Here it is, _The Two-Bulb Room_:
“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.
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.”