Please comment your solutions, questions and remarks..
Consider a prison with several millions prisoners. The head of the prison arranges the following challenge to the prisoners. One prisoner at a time will be called to a room with a lamp. The lamp is always on or off and the prisoner may change the state of the lamp or leave it as it was. Every hour a randomly picked prisoner is called to the room. Whenever a prisoner is in the room, he or she may say “now everybody have been in this room”. If this prisoner is right, everybody get freedom. If not, the game stops immediately and everybody are hanged. What is the strategy for the prisoners to agree, before the challenge starts, so that they all get freedom with probability 1?
Level 3/5
What do you mean by “all get freedom with probability 1”?
What if the same person is chosen to go to the room over and over again? Also, you didn’t tell
* can the same person enter the room more than one time? (yes)
* do the prisoners know how many of them there are in the prison? (no, but a finite number)
* are the prisoners able to count days? (maybe)
* can the prisoners have different tasks in the strategy? (yes)
* is there a time limit? (maybe)
I have heard this problem before, so I won’t give a solution. E-mail me if you wan’t more info. There are different solutions depending on if the prisoners can count days or not. There were 100 prisoners in the version I heard and they all managed to get out before dying.
Thank you for commenting!
> What do you mean by “all get freedom with probability 1″?
> What if the same person is chosen to go to the room over and over again?
I mean that the strategy they agree on is such that it works with probability 1. It is written that the chair chooses the prisoners at random, meaning: he chooses them according to the uniform probability distribution. The probability that he calls the same person over and over again ad infinitum is hence zero.
* can the same person enter the room more than one time?
It is not specifyed, so why not?
* do the prisoners know how many of them there are in the prison? (no, but a finite number)
They could agree on the strategy in advance together, so yes they know.
* are the prisoners able to count days? (maybe)
They are human
* can the prisoners have different tasks in the strategy? (yes)
again, not specified, so why not?
* is there a time limit? (maybe)
not specified, so no, there is no limit; and cannot be, since we want to stick with probability 1.