Jul 19, 2007 -- posted by DarK
Puzzle 4: The Two Switches
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 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.”
Mail your answers to gurus [dot] comments [at] gmail [dot] com
Also comment if you have mailed the answer.
—————————————————————————————-
This problem is taken from a site which I will put up later, so that you don’t ruin the problem by looking at answer. Till then you brainstorm. It’s an awesome problem.
There are 4 possible combinations, UU DD UD and DU.
These can be changed as follows
UU to UD or DU
DD to UD or DU
UD to DD or UU
DU to DD or UU
The prisoners agree beforehand that if this is their first visit, they leave the switches in, say, DD or DU positions. If this is a subsequent visit, they leave them in UU or UD positions.
They each count how many times they find the switches in DD or DU positions, indicating that the person before them was on a first visit.
The first prisoner to reach a count of 23 (including himself) hollers “Freedom for All”.
Incidentally, you do need the sentence “…everyone will visit the switch room as many times as everyone else” to prevent the situation where one prisoner is only sent in a small number of times and his visit is not caught by the person after him that eventually reaches the 23 tally (think about it!).
See the solution here….
http://www.w-uh.com/articles/030530-the_two_switches.html
Owing to the random selection element, there will never be a highly efficient answer to the puzzle, as it will often result in repeat visits and hence wastage. The first prisoner remembers two things at all times: a running count and a switch state. Every time the first prisoner visits the cell, he arbitrarily flips Switch 1 (only because he has to), then if the state of Switch 2 is different to his previous visit, he increases his running count by one. Every time one of the other prisoners visits the cell, if they have not visited before, they flip Switch 2, otherwise they flip Switch 1. When the first prisoner’s running count equals the number of prisoners, he can confidently declare that everyone has visited.
The prisoner is selected at random, the only rule is that after a time, all will have been selected equally as often as each other. There is no rule on how many times in a row etc…
3 times
“I may choose the same guy three times in a row”
may he choose same prisoner two times, or four?
or is it 1 > 1 >1 >2 >3 >1 >1 >2 >3 ?