×

# Prisoner Warden Dilemma

The warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

"In the prison is a switch room, which contains two light switches labeled 1 and 2, each of which can be in either up or the down position. I am not telling you their present positions. The switches are not connected to anything.

"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must flip one switch when he visits the switch room, and may only flip one of the switches. Then he'll be led back to his cell.

"No one else will be allowed to alter the switches until I lead the next prisoner into the switch room. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back. I will not touch the switches, if I wanted you dead you would already be dead.

Given enough time, everyone will eventually visit the switch room the same number of times as everyone else. At any time, anyone may declare to me, 'We have all visited the switch room.'

"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will all die horribly. You will be carefully monitored, and any attempt to break any of these rules will result in instant death to all of you"

What is the strategy they come up with so that they can be free?

Note by Vishwathiga Jayasankar
2 years, 4 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

> This is a quote
This is a quote
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

This is a pretty common logic problem.

Set one of the prisoners as the captain. Here's the strategy:

Non-captains:

• Never declare completion.
• If switch 1 is in down position and you haven't flicked switch 1 twice, flick it up.
• Otherwise (either switch 1 is in up position, or you have flicked switch 1 twice), flick switch 2.

Captains:

• If switch 1 is in up position, flick it down.
• Otherwise, flick switch 2.
• If you have flicked switch 1 for 44 times, declare completion.

Proof of correctness: Note that each non-captain flicks switch 1 up for at most twice. Thus if there are 43 flicks, every non-captain has flicked switch 1 up at least once, and thus showing that all of them have visited the room. Since at the beginning switch 1 might be in up position, we give one extra flick to take care of this. (This also explains why non-captains only flicking once doesn't work; we need all 22 flicks to indicate completion, but we can't tell the state of the beginning; if the captain declares completion at 22 flicks, it's possible that switch 1 was up originally and thus somebody might haven't been in the room, but if the captain declares completion at 23 flicks, it's possible that switch 1 was down originally and so the captain will never declare completion.)

- 2 years, 4 months ago