Prison Switcharoo

http://www.cartalk.com/content/prison-switcharoo-0?question

by jamessun • 12 years ago

89 63 12 years ago

cartalk.com

lisper2• 12 years ago

The answer: http://www.cartalk.com/content/prison-switcharoo-0?answer

no_wave• 12 years ago

It should be 43 instead of 44, right?

colanderman• 12 years ago

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.

delinka• 12 years ago

The answer explains this. The number should be (p - 1) x 2 where p is the number of prisoners. (23-1) = 22 * 2 = 44

michael_h2• 12 years ago

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.

Did I miss something?

TobbenTM2• 12 years ago

The prisoners will only turn on switch A twice. After that they will leave it, and rather toggle the B switch.

daeken• 12 years ago

Each person will only toggle A to the 'on' state twice.

ironmagma• 12 years ago

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?

vanschelven• 12 years ago

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."

mischanix• 12 years ago

And here's the answer in Go: http://play.golang.org/p/m_biT7Dfmo

joenathan• 12 years ago

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.

christiangenco3• 12 years ago

'"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?"'

codyps• 12 years ago

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)?

lisper2• 12 years ago

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.

sfenu• 12 years ago

Here's the best solution I've heard for this:

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.

callahad• 12 years ago

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.

Ah, but what's a sufficient number of times? The unknown initial state is what tripped me for a bit. :)

gberger• 12 years ago

n-1, where n is the number of prisoners. -1 to account for the leader.

linux_devil• 12 years ago

"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

jaltekruse• 12 years ago

The person tallying keeps a count in their head.

rokhayakebe2• 12 years ago

Good luck if the leader is the 22nd person to go in.

jamessun• 12 years ago

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?

salmonellaeater• 12 years ago

Presh Talwalkar posts weekly logic puzzles[1]. His blog is a good source of interesting applications of economics and game theory to the real world.

[1] http://mindyourdecisions.com/blog/

numlocked• 12 years ago

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!

Semiphore• 12 years ago

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.

kordless• 12 years ago

If it's common knowledge, there's no point in asking it other to gauge if you have common knowledge.

rdtsc• 12 years ago

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.

sirsar• 12 years ago

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.

http://www.segerman.org/prisoners.pdf

robinhouston2• 12 years ago

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.”

christiangenco3• 12 years ago

Is this two-bulb room problem not identical to the OP's Prison Switcharoo problem?

ColinWright• 12 years ago

The clue to the difference is here:

    ... but this time, every prisoner must follow
        the same set of rules.

robinhouston2• 12 years ago

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.

if_by_whisky• 12 years ago

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

christiangenco3• 12 years ago

You could solve this by creating an order of succession for the designated counter in your original meeting.

If no announcement is made when someone dies, however, you've got a problem.

ars• 12 years ago

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

anonymoushn2• 12 years ago

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.

thatthatis• 12 years ago

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.

didsomeonesay2• 12 years ago

You cannot know if you are the first to go into the switch room. Prisoners are taken to the room at arbitrary times.

Zarel• 12 years ago

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.

sophacles4• 12 years ago

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 :)

garrettgrimsley• 12 years ago

You are really overthinking this. The Car Talk puzzlers are straight forward and should be taken at face value.

sophacles4• 12 years ago

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.

maxerickson• 12 years ago

The warden lying is in the same category as the universe exploding (I.e., the universe might explode next week, should I still get a coffee?).

It's fine if you think games are stupid, maybe try to get to the point a little quicker though.

sophacles4• 12 years ago

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.

vacri• 12 years ago

trivially broken by not assuming everything will play nicely in the environment.

"In theory, there is no difference between theory and practice. In practice, there is"

aaron695• 12 years ago

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 :)

sophacles4• 12 years ago

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... :)

miguelrochefort3• 12 years ago

Can't they all meet in the switch room?

rokhayakebe2• 12 years ago

Every now and then you find someone who thinks differently from everyone else. In this case, you.

miguelrochefort3• 12 years ago

I might also be thinking wrong. But as far as I know, the puzzle doesn't explicitly prohibit this.

sixQuarks• 12 years ago

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.

jessedhillon• 12 years ago

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?

freshhawk• 12 years ago

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.

anonymoushn2• 12 years ago

This is mostly an instance of a class of problem discussed in more depth here: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board...

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.

calebclark• 12 years ago

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.

aaronsnoswell• 12 years ago

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?

[1] http://pastebin.com/n0vHSdzm

Prison Switcharoo

Related Stories