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

71–80 of 81 posts

Re: Prison Switcharoo

#71

Post by sophacles »

aaron695 wrote: post #66
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…

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…

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

Re: Prison Switcharoo

#72

Post by anigbrowl »

miguelrochefort wrote: post #68
rokhayakebe wrote: post #47

Earlier quoted context omitted.

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

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

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.

Re: Prison Switcharoo

#73

Post by sophacles »

maxerickson wrote: post #41
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.

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.

Re: Prison Switcharoo

#74

Post by michael_h »

daeken wrote: post #30
michael_h wrote: post #26

Earlier quoted context omitted.

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?

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

ah, yes. It even says it right there in the article. Thanks!

Re: Prison Switcharoo

#75

Post by omegaham »

robinhouston wrote: post #60
christiangenco wrote: post #57

Earlier quoted context omitted.

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…

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

Re: Prison Switcharoo

#77

Post by didsomeonesay »

Zarel wrote: post #52
didsomeonesay wrote: post #27

Earlier quoted context omitted.

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.

Right...

Re: Prison Switcharoo

#78

Post by codyps »

lisper wrote: post #2

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

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 ONs (N - 1 + 1)?

Re: Prison Switcharoo

#79

Post by lisper »

codyps wrote: post #78
lisper wrote: post #2

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

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

Re: Prison Switcharoo

#80

Post by mcguire »

Udo wrote: post #49
mcguire wrote: post #43

Earlier quoted context omitted.

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.
Post reply on HN