Fog Creek Software
Discussion Board




Warden and Prisnors Puzzle | Solution

I was just looking at Warden and prisnors puzzle. Here is a solution:

The prisnors can come up with a strategy such that they will make both the switches in on position just once (11) and no more. If you think about each of the four cases (considering 0 as off and 1 as on), it can be avoided to make both the switches on after he has already done it once. The sample of four cases is as follows:

1) 00 -> 01  or 10
2) 01 -> 00
3) 10 -> 00
4) 11 -> 10 or 01

With this strategy, each of the prisnor will count the number of times he will encounter the switches in on position, i.e. 11. Considering that each prisnor is making that position just once and taking the allowance for the case that the wardener might have started with the first time in position 11, a prisnor can be damn sure that everyone has visited the prison at least once when the count is 24. (Allowing for the case when  the first time switches are in 11 position). Hence, any of the prisnor can declare to the wardener that everyone has visited the switchroom at least once when the count is 24.

Let me know what you think of this solution. Looking for feedback and comments,

Saurabh and Nidhi.

Saurabh and Nidhi
Monday, December 08, 2003

Does not work. If every prisoner switches to 11 just once, it cannot be assured that any of the prisoners will count to 24. One special prisoner would have to be selected to be allowed to enter after every other prisoner to observe _all_ their switching -- which is not possible.

I propose another solution which is based on the assurance that "everyone will eventually visit the switch room as many times as everyone else". Probability theorie suggests that after his 23rd time in the switch room a prisoner can not be sure that all other were in the same number of times but he could assume that most were there at least around 10 times.
After his 1000th time in the room he can be quite sure that every one has been there. He doesn't know for sure but its _very_ probable.

Given the time which passed since the imprisonment, they could say:
If after 2 weeks one of us is in the switch room for the 1000th time, he assumes all have been in there once.
If after 1 year one of us is in the switch room for the 100th time, he assumes all have been in there once.
If after 10 years one of us is in the switch room for the 10th time, he assumes all have been in there once.
If after 20 years one of us is in the switch room for the 5th time, he assumes all have been in there once.

So they weigh probability (and the risk of being wrong) against the time they already spent in jail (with heightend risk that one of them dies and is never able to get into the switch room for the first time).

Bernd Fondermann
Friday, December 12, 2003

The solution may be in assigning a dedicated person responsible for turning OFF one of the switches and anyone else can only turn it ON and only once during all visits. They will be playing with the second switch all other visits. So, the dedicated person may count the number of ONs of the first switch and say ‘let my people go’ when it reaches 22 (he does not have to turn it ON). The only issue is the initial position. I think it can be handled by agreeing that the first week anyone who sees the first switch must turn it OFF and counting/turning it ON starts only on the second week. It is a weak link though. May be ten minutes of thoughts I gave to the puzzle is not enough ;-)

Val Al
Friday, December 19, 2003

I think the key to this question is that it specifies that the two switches are light switches.  This indicates to me that all prisoners should be able to tell which one has been switched.  They can tell by seeing which lights are on and which are off.
I would suggest that the solution is simply that if you have never been in there flip switch A, if you have been in there before switch flip B.  When A has been flipped 23 times, then the prisoners will know that everyone was in there.

Bill Simpson
Monday, January 12, 2004

Well, I was reading the question again in the hope to pick up some hint and kind-of picked one.

A hint that leads to the solution, literally !! The author says that this problem was picked from Car Talk. So I looked at their site (got the link from FAQs) and voila! Found the solution.

Go and have a look. Its explained thoroughly.

http://cartalk.cars.com/Radio/Puzzler/Transcripts/200307/answer.html

But due credit must be given to Val Al- he almost got it.

VikasRana
Wednesday, January 14, 2004

That link was dead. But I think I know the answer.
Anyway...
Let's call the prisoners A, B, and C.
They can decide that A and B are only to move the first switch and C is only to move the second.
(They could decide that the "first" switch is the one positioned either above or to the left of the other "second" one.)

For my argument, only A or B can make the statement that all have visited the room.
How do they know?
Let's say B enters the room for the second (or later) time. He can look at the switches and notice if the switches are as he left them. If the first switch was not as he left it from his previous visit he knows that A has visited the room. If the second switch was not as he last saw it he knows that C has visited the room.
Prisoner A could make the same call. Prisoner C can not make the statement that all have visited because he can not distinguish between the moves of Prisoners A and B.

Marc Peabody
Thursday, January 29, 2004

Here's an updated link to the CarTalk solution to the puzzler:
http://cartalk.cars.com/content/puzzler/transcripts/200307/answer.htm     

The answer took me a minute to understand from the page, so here it is simplified...

First, read Val Al's answer above.  He's got the right idea.
He said (summarizing) you have one counter, and he's the only one who's allowed to ever turn switch A off.  The other prisoners will each turn A on once.  This way, the counter knows when he's counted 22 that one of these is true:
* If A was initially off: all 22 prisoners flipped it
* if A was initially on: only 21 prisoners flipped it

No good... as long as the number stays at 21, the counter can't tell if maybe there's just a single prisoner who just hasn't made it in (however improbably that is).

So how to fix the problem?

Well, follow the same plan, but tell each prisoner to flip switch A on TWICE.  When the counter reaches 44, his knows one of these is true:
* If A was initially off, 22 prisoners have flipped it twice.
* If A was initlally on, 21 prisoners have flipped it twice, and 1 guy has only flipped it once.

In short, he's 100% sure they've all been in there at least once.

jtheory
Thursday, January 29, 2004

Or you could forget the "counter" idea (which makes no sense) and read my solution.

Marc Peabody
Friday, January 30, 2004

I can see that answers by Val Al and "jtheory" are correct. But I am not so sure about Marc's solution. How is Marc's solution going to scale up for 23 prisoners- two switches can represent only 4 states.

Vishal Goopta
Saturday, January 31, 2004

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else"

This statement could be read to mean that no-one will visit the switch room after this point, as it makes no reference to continuation or repitition.

It is possible this may happen before the prisoners have all been counted. In which case the prisoners can at least avoid being eaten by the alligators, but have no garentee of escape.

Sam Hasler
Monday, February 02, 2004

Apologies for my spelling. (That's apologies with one "p" not the two I originally (oops two l's in originally ) used ;)

Sam Hasler
Monday, February 02, 2004

*  Recent Topics

*  Fog Creek Home