I met a puzzle, which is basically well known 100 Prisoners' Names in Boxes , but... it has an algorithm, which gives prisoners 100% chance to survive!
This is achieved by a small change in the procedure:
Prisoners can invite a friend, who visit the room before the first prisoner and is allowed to check out all boxes and switch places of two names in them.
That's it. The prisoners and the friend have a chance to plot their strategy in advance, but no communication is allowed after beginning of the procedure.
How 100% survival can be reached here is quite obvious for those who read the linked topic, but anyway here is it:
The numbers from 1 to 100 is given to each prisoner (you can read "number" as a "name") and to each box. The friend must find all chains of numbers like "Box A has number B -> Box B has number C -> ... -> box X has number A". There can be only one chain of length more than 50. If the friend finds it he must switch places of two distant numbers in the chain. In that case the chain will be divided into two chains of length less than 50.
Then all prisoners just must start from the box with their number and follow the chain until they reaches the box, which contains they number. Since there won't be any chain longer than 50 all of them will succeed.
As you can see, we got quite nice puzzle on it's own, which can be given even to a child, who can't do complicated probability calculations.
So I started to wonder - What are other possible changes in the initial 100 Prisoners' Names in Boxes procedure you can make that similarly lead to 100% chance of survival? I mean really small changes, hopefully even smaller than the given example.
No comments:
Post a Comment