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

1–10 of 81 posts

Re: Prison Switcharoo

#3

Post by sfenu »

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.

Re: Prison Switcharoo

#4

Post by jamessun »

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?

Re: Prison Switcharoo

#6

Post by callahad »

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

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

Re: Prison Switcharoo

#7

Post by numlocked »

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!

Re: Prison Switcharoo

#8

Post by Semiphore »

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.

Re: Prison Switcharoo

#9

Post by salmonellaeater »

jamessun wrote: post #4

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?

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/

Post reply on HN