jods

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

"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 move one, but only one of the switches. He can't move both but he can't move none either. Then he'll be led back to his cell.

"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. 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.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.' and be 100% sure.

"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 be fed to the alligators."

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

KiwiGTI

One prisoner is designated as the "caller." He and only he will make
the determination of when everyone's been in the room. Whenever he
sees that the left-hand switch is "down," he will move it "up" and add
1 to his count; otherwise, he will flip the right-hand switch and not
think anything of it. When the other prisoners enter the room, they
have a different strategy. If the left-hand switch is "up," they will
switch it "down," but they will only do this the first two times they
encounter the left-hand switch "up." If they've moved the left switch
twice already, or if the left-hand switch is "down," they will flip
the right-hand switch.

When the caller's count is 44, each prisoner must have been in the
room at least once, regardless of the initial configuration of the
switches.

KiwiGTI

And the origin

http://domino.research.ibm.com/Comm/.../July2002.html

Markus

1. Appoint a "scorekeeper" and the other 22 prisoners as "transmitters".

2. When a transmitter enter the switch room for the first time, he will flick switch B ON if he sees it in an OFF position. Alternatively, he will flick switch A if he sees switch B is in the ON position and wait for his next visit. The transmitter's mission is to find ONE opportunity to flick switch B to ON position. After he completed his mission, he will flick switch A for all subsequent visits. In short, each transmitter's role is to send a signal to the scorekeeper that he has been to the switch room.

3. The scorekeeper's role is to flick off switch B whenever he sees it in ON position. Each time he flicked off switch B he adds 1 to his score. When he see switch B is already OFF, he flick switch A instead and do not add to the score. As soon as he accumulated 22 on the score, he reports to the Warden.

Jerome

I don't know if this is allowed, but they could "number off" so they all have a different number between 1 and 23. When they go in the switch room, they write their own number on the wall next to the light switch. Eventually the last prisoner to go in the switch room will see every number (except his own) and can announce everyone has been in there.

Edited to add:

After reading the solution, my head hurts. The answer relies on the fact that there is a mathematician amongst the prisoners, which is even more unlikely than them getting away with scribbling on the wall.

KiwiGTI

The correct IBM Solution

Elect a spokesman.

Each prisoner other than the spokesman maintains a counter with initial value 0. When he enters the switch room, if switch "A" is "off" and his counter is 0 or 1, then he switches "A" to "on" and increments his counter. Otherwise (switch "A" is already "on" or his counter is 2) he switches "B".

The spokesman also has a counter with initial value 0. When he enters the switch room, if switch "A" is "on", he switches "A" to "off" and increments his counter. Otherwise (switch "A" is already "off") he switches "B". When the spokesman's counter reaches 44, he declares to the warden "We have all visited the switch room."

He is safe in making this declaration: among the 44 times that the switch had been "on", at most once was because the switch might have started out in the "on" position at the beginning of time. At most two were due to each prisoner (other than the spokesman himself) turning it on. If not everyone had visited the switch room, then it could have been turned "on" at most 2*21=42 times, and his counter would not exceed 42+1=43.

Further, given enough time, each prisoner will have two opportunities to turn "on" the switch, so that the spokesman's counter will eventually reach or exceed 44.

Switch "B" is only used so that the prisoner has something to flip when the protocol says he should not flip switch "A".

The non-spokeman prisoners turn the switch on twice instead of just once, because of the uncertainty about its initial position.

jods

Hats off to those with the answer.
Must have brains the size of a planet


I'll let you know if I get the job

KiwiGTI

Actually it's quite simple once you understand it. It's simply a binary counting system.

Jerome

Maybe I'm being thick, but that doesn't appear to be simple. I understand binary very well, and this isn't counting in binary. To truly count in binary you would have to be able to flick 2 switches at once some of the time.

I still don't see how the spokesman knows that each prisoner has been in after his counter reaches 44. Surely his counter could reach 44 and there is still one prisoner who has never been to the switch room.

carl

No, because the other prisoners' behaviour changes once they've flipped the switch twice. His counter only gets to 44 when the switch has been switched 44 times. But the prisoners are under instructions to only flip it twice. So if somebody had visited four times, on the last two occasions they wouldn't flip the switch so the spokesman wouldn't increment the counter and wouldn't have got to 44.

KiwiGTI

Ok, the key is that the spokesman is the only person that can turn switch A off.

Imagine both switches off.

Prisoner 1 walks in, turns switch A on, increases his count to 1.
Prisoner 2 walks in, switch A on already, so he turns Swith B, but doesn't increase his count
Spokesman walks in sees Switch A on, turns A off and increases his counter to 1
etc etc

It has to be a count of 44 to take into account the initial position of, each prisoner also stops turning the A switch on after 2 tries. (then on only touching the B switch)

Sorry, might not be called binary countring, i think it's called a binary switch problem. (Switches can be represented as 11, 10, 01, 00)

DemonDave

iTrader: (13)

I'd really be worried if I got the job, what the hell would you be supporting !!!!

Jerome

Thank you sir! I was able to get my feeble mind around that explaination.

I also hope that all the prisoners are in for a long time, because it could take some time for the spokesman's counter to get to 44. Might screw the whole thing up if a prisoner who hasn't been in the switch room gets released.

ALi-B

iTrader: (1)

Why can't they just ask you count in hexidecimal

KiwiGTI

Sounds like a wild evening

BOB.T

jods

It's a multi-threaded multidimensional financial strategic tracking and forecasting system for a large financial player.

I like it.

jods

And I'm STILL there!

Not a switch in site though !!!

Sonic'

And here was me thinking you had gone/going to prison

I have tried to read the above posts, and well my head hurts now