23 Prisoners

[Arjun Shastry]

Appeared recently in one newspaper Those who know the solution,wait till week end and then post your solution)
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.'
"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."
There exists a strategy such that, if the prisoners adopt it, they are guaranteed to be set free (given enough time). What is the strategy?

[HS Thomas]

A- on B- off
I think the switches are not relevant. Given enough time each prisoner will have visited the switch room. The strategy would be to calculate how much time is enough time.
23 x 23 = 529
After 529 days may be enough time ?
OR
23 x 23 x 23 days ?

[fred rosenberger]

The problem doesn't say anything about how many times each will visit, or how many days inbetween visits. It just says "from time to time". maybe the warden goes for 2 years and never lets anyone in the switch room.
at least, that's how i'm reading the problem (somebody let me know if i'm wrong). So, i don't see how you can just say 23 X 23 days, or 23 ^ 3 days.
i have no idea what the answer is, but i'm curious now.

[HS Thomas]

I was thinking along the lines :
Max no of days between calls for each prisoner = 23 days x 23 prisoners.= 529 days seemed reasonable.For each day that the prisoner does get called between the 23 days add another 23 days. The warden should tire of this game and the alligators would die of hunger anyway.
I forget what the logic behind 23 ^ 3 was - but that's just over 33 years and I doubt the prisoners would accept that.
No I think they'll need some cunning strategy to get out quicker.
Two false parts to a statement make the statement true.Perhaps they can play around with the statement - 'We have all visited the switch room.'
something the warden CANNOT refute
'It's false that we have all visited the switch room'
'Isn't it true that not all visited the switch room ?'
C'mon Cap. True or false ?
[ December 10, 2003: Message edited by: HS Thomas ]

[Joel McNary]

For those truly interested but don't want to wait for the answer, this was posted in this forum in August
The solution is really pretty neat, though, so try to solve it before reading that thread (which doesn't actually contain the solution, anyway, although it does link to it).

[HS Thomas]

Originally posted by Joel McNary:
For those truly interested but don't want to wait for the answer

No harm in trying different approaches though, IMHO.
While truly impressed with the answer ( like to meet a sixth-grader who could come up with that solution) I couldn't help thinking : what if a prisoner like,you know, died...or couldn't count over long periods of interruptions or became withdrawn.
[ December 11, 2003: Message edited by: HS Thomas ]