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

41–50 of 81 posts

Re: Prison Switcharoo

#41

Post by maxerickson »

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…

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.

Re: Prison Switcharoo

#42

Post by jessedhillon »

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?

Re: Prison Switcharoo

#43

Post by mcguire »

Udo wrote: post #38
jdoliner wrote: post #33

Earlier quoted context omitted.

Prisoners only flip the switch twice. You have p1 flipping it 4 times.

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

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.

Re: Prison Switcharoo

#44

Post by evanb »

gberger wrote: post #21
callahad wrote: post #6

Earlier quoted context omitted.

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

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

It's actually 2(n-1), because the designated switch can start in either state.

Re: Prison Switcharoo

#45

Post by JangoSteve »

Udo wrote: post #38
jdoliner wrote: post #33

Earlier quoted context omitted.

Prisoners only flip the switch twice. You have p1 flipping it 4 times.

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.

Re: Prison Switcharoo

#46

Post by stefan_kendall »

gberger wrote: post #21
callahad wrote: post #6

Earlier quoted context omitted.

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

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

n. You have to account for the case that the light is on and the tallyer is the first to enter the room.

Re: Prison Switcharoo

#48

Post by rokhayakebe »

sfenu wrote: post #3

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

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

Re: Prison Switcharoo

#49

Post by Udo »

mcguire wrote: post #43
Udo wrote: post #38

Earlier quoted context omitted.

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

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.

Re: Prison Switcharoo

#50

Post by Udo »

JangoSteve wrote: post #45
Udo wrote: post #38

Earlier quoted context omitted.

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…

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.

Post reply on HN