Puzzles/100囚人/スイッチ問題

Puzzles/100囚人について、ここに記述してください。

パズルの国のひとたちは100人の囚人が好きだ。

1. スイッチひとつ

問題もいろいろ。

100 Prisoners and A light Bulb　Yisong Son

できるだけ、短期間で釈放されるのが望ましい。

2. The riddleThe riddle is as followings:

One hundred prisoners have been newly ushered into prison.

The warden tells them that starting tomorrow, each of them will be placed in an isolated cell, unable to communicateamongst each other.

Each day, the warden will choose one of the prisoners uniformly at random with replacement, and place him in a central interrogation room containing onlya light bulb with a toggle switch.

The prisoner will be able to observe the current state ofthe light bulb.

If he wishes, he can toggle the light bulb.

He also has the option of announcing that he believes all prisoners have visited the interrogation room at somepoint in time.

If this announcement is true, then all prisoners are set free, but if it is false, all prisoners are executed.

The warden leaves, and the prisoners huddle together to discuss their fate.

Can they agree on a protocol that will guarantee their freedom?