## Sep 21, 2010

### 29 hostages and a terrorist

29 hostages are captured by a terrorist. They are told, "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."

"There is an isolated switch room here, which contains two light switches labelled 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 hostage at random and escort him to the switch room. This hostage will select one of the two switches and reverse its position. He must move one, and only one of the switches. He can't move both and he can't move none either. Then he'll be led back to his cell."

“I will then take the next hostage there, and he'll be instructed to do the same thing. I am going to choose hostages 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. "No one else will enter the switch room until I lead them."

"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?

Source: www.allinterview.com

1. i did not get a few things!
1st- " I may choose the same guy three times in a row, or I may jump around and come back"
what does this mean..

2nd- how will the terroist come to know whether the hostages are telling the truth about them being to the room atleast once..
will the terrorist be keeping track of who has been to the room..?

2. this is what i think the answer cud be..
now every hostage when first time goes to the cell, will notice the current position, and that will be like the reference position for each of them.now everyone will decide a sequence before hand..as in
11->10->00->01->11..the order in which the switches need to be changed.

now each time a hostage goes in he will follow the sequence and make the changes to the switch system and the next time he goes in,he will undo what he did the last time..
now if that person observes any change in the switch system,he will come to know how many more hostages have been to the room!(except him)
and if the system is the same, this might happen because either he has been chosen again or the cycle has been completed,but since the hostages have to be sure,he will take it as he has been chosen again only..
now since all the hostages will be keeping the track and counting,so the moment any hostage counts 28 he may declare that all of them has been to the place..

also since we cant determine the number of times the hostages be taken to the room and only the strategy has to be defined,.this might take some time but this is what i feel the strategy should be!

3. A friend told me a similar riddle a few days ago and it took me forever to figure out.
However, in that example you KNEW the beginning state. This is a bit tricky.

In that case, I designated one hostage to be the "guy who calls it."
Then, each person flips the right switch if they go once. Then the left switch all the times after that. But they only flip the right switch if it's down. If it's up, they flip the left one. That way, each one time the right switch is flipped serves as a "count" that one guy has been there.
Then, when the "guy who calls it" comes, he flips right down, indicating he "counted" it. Then the next guy, if they haven't been counted, flips right.
The "guy who calls it" will have to go 28 times.

Now, I'm just thinking how to do it in this case...
Oh, maybe you could just make everyone go twice. So, they need to indicate to the main guy TWO times. So, if the right switch begins in the ON position, the guy will mistakenly count it as a person. But that is OK. Just make everyone go twice. Then when the main guy counts to 59. Then he calls it.
The idea of the response above me is on the right track, but the problem in a repeating sequence is that if you see the same state, you don't know if 4, or 8, or 12 people have gone in between.
Sweet.

Designate one person as the counter. Designate one switch (A) as a junk switch, and one switch (B) as the count switch.

Because the initial state is unknown and because no hostage knows if he or she is the first person, everybody has to be counted twice.

The first time the counter enters the room, B is flipped down if it is up. This sets the initial state. If it is down, A is flipped. When anyone else enters the room, B is flipped up if B is down and if he or she has not flipped B twice. Otherwise, A is flipped.

Here are the algorithms for the counter and every one else.

# Every one (not the counter) #
if (! counted twice)
__if (!B)
____flip (B)
__else
____flip (A)
else
__flip (A)

# Designated counter #
if (isFirst) // First time entering the room
__if (B)
____flip (B) // Set initial state
__else
____flip (A) // Initial state already set
else
__if (B)
____increment count
____if (count >= 2 * 28)
______call it // Everybody counted twice!
____else
______flip (B) // Reset count switch
__else
____flip (A)