Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Prison Switcharoo

cartalk.com

Post reply on HN
Print view View original

51–60 of 81 posts

Re: Prison Switcharoo

#51

Post by freshhawk »

jessedhillon wrote: post #42

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.

Re: Prison Switcharoo

#52

Post by Zarel »

didsomeonesay wrote: post #27
thatthatis wrote: post #20

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 i…

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

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.

Re: Prison Switcharoo

#53

Post by ironmagma »

lisper wrote: post #2

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

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, would the solution still work?

Re: Prison Switcharoo

#55

Post by joenathan »

lisper wrote: post #2

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

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.

Re: Prison Switcharoo

#56

Post by vacri »

sophacles wrote: post #24

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…

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"

Re: Prison Switcharoo

#57

Post by christiangenco »

robinhouston wrote: post #14

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 r…

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

Re: Prison Switcharoo

#58

Post by ColinWright »

christiangenco wrote: post #57
robinhouston wrote: post #14

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 r…

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

The clue to the difference is here:

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

Re: Prison Switcharoo

#59

Post by christiangenco »

joenathan wrote: post #55
lisper wrote: post #2

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

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

Re: Prison Switcharoo

#60

Post by robinhouston »

christiangenco wrote: post #57
robinhouston wrote: post #14

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 r…

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

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.

Post reply on HN