I did not make up this
problem. I didn't even solve it. But I like it. So here it is.
23
Prisoners- Problem
23 prisoners are told they will be selected,
one-by-one by random drawing, to enter a room in the prison.In the room are two switches, side by side.Each switch can be up or down, with no intermediate position.The switches are not connected to anything.When the prisoner enters the room he must choose either the right or left switch and
change its position - up to down, or down to up.Then he goes back to his cell.At
any time of the prisoners choosing, any one of them can tell the warden that
each and every prisoner has been in the switch room at least once.If he is right they all go free, if hes wrong they are all killed
there are no second chances.
Rules:
The
drawing for the switch room is by random selection, and occurs at no
particular frequency.But it
occurs repeatedly until any one of the prisoners tells the warden that all
the prisoners have been in the switch room at least once.
At
every random drawing, each prisoner is equally likely to be selected,
whether or not he has ever been selected before so anyone may be
selected and re-selected any number of times.
The
original set of 23 prisoners never changes.
They
can meet just once at the start and make up a plan.After that, they will be in individual cells and will never see or
talk to each other again.
They
do not know the initial position of the switches.
Their
plan can take as long as needed there is no time limit.
There
is no penalty for not making the
announcement as soon as everyone has been in the room.The only penalty is for falsely stating that they have.
