📜 ⬆️ ⬇️

Prisoners and boxes

Another problem about prisoners. This time is not so theoretical.

There are 30 prisoners numbered from 1 to 30. Everyone knows all the numbers, including his own. They have time to discuss the algorithm. Then they are led one by one into a room where there are 30 numbered boxes. In each box there is one key with the number of some prisoner (the box number and the key number in it may be different). The keys in the boxes are distributed completely randomly (i.e., all the permutations of the keys in the boxes are equally likely). Each prisoner opens 15 boxes in turn and looks at the keys in them, and, opening the next box, he can first see which key is in it and then decide which one to open. If in one of these 15 boxes there was a key with its number, then it is released; if not, they are shot. The room and all the boxes in it are then returned to their original state, i.e. the following prisoners do not receive any information about what happened to the previous prisoner.
Think of an algorithm so that all prisoners survive with a probability of at least 30%.

PS You can use the calculator.
')
UPD Solution in the comments .

Source: https://habr.com/ru/post/55689/


All Articles