Problem 47668. A KING AND 100 PRISONERS
There are 100 prisoners in 100 different cells.
The cells were enclosed, and the prisoners could not tell the time in any way in their cells, nor could they communicate with each other.Pick a random person every day to go out to a particular place.
The place where was a light inside, which the prisoners could turn on or off at their own choice, and no one but the prisoners could switch the light.The lamp never breaks.
The king thought of a game, if someone could prove to the king that every prisoner had been picked in 20 years, the king would set them free.
Now give the prisoners a way to talk things over, and then play games.
After some discussion, Prisoner A came up with an idea.
He told others some rules. If others follow the rules, then he can prove it
. The rules are as follows:
1.Prisoner A will turn off the light when he found it on.If it is not on, Prisoner A does not operate.
2.If other prisoners find out for the first time that the light if off, turn it on.
After some discussion, the prisoners are sure that will work, but the question is, how long would it take to get out? Can they prove the king's proof question in 20 years?
Simulate this situation and estimate the time required.
Solution Stats
Problem Comments
-
2 Comments
Rafael S.T. Vieira
on 8 Nov 2022
Nice. On the other hand, the test suite should probably forbid people from returning any number between 20 and 40. Just open the file and look for these numbers and their multiples explicitly.
Rafael S.T. Vieira
on 8 Nov 2022
And by the way, it would be faster if all prisoners could turn off the light. They only need to have a variable known by all who share the room but the king. Leave the king doubtful and in the dark, so they would all go free.
Solution Comments
Show commentsProblem Recent Solvers17
Suggested Problems
-
Swap the first and last columns
19913 Solvers
-
9449 Solvers
-
376 Solvers
-
160 Solvers
-
127 Solvers
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!