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

11–20 of 81 posts

Re: Prison Switcharoo

#11

Post by linux_devil »

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

"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

Re: Prison Switcharoo

#12

Post by jaltekruse »

linux_devil wrote: post #11
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.…

"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

The person tallying keeps a count in their head.

Re: Prison Switcharoo

#13

Post by sirsar »

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

Re: Prison Switcharoo

#14

Post by robinhouston »

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

Re: Prison Switcharoo

#15

Post by colanderman »

no_wave wrote: post #10
lisper wrote: post #2

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

It should be 43 instead of 44, right?

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.

Re: Prison Switcharoo

#17

Post by kordless »

Semiphore wrote: post #8

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.

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

Re: Prison Switcharoo

#20

Post by thatthatis »

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.

Post reply on HN