It's time to paint the prison. The warden wants the cells cleared for the convenience of the painter. He devises a scheme by which his 100 prisoners either will be all freed or all executed. Either way, the painting will be made easier. His scheme offers a survival probability that seems terribly small.

In a room he places their names, on sheets of paper, in 100 wooden boxes, numbered 1-100 and lined up on a table, one name to a box. Prisoners are led into the room one by one and are told to look inside the boxes in search of their name. But each prisoner can open at most 50 boxes. Successful or not, each prisoner must then leave the room, exactly as he found it, and he is permitted no further communication with the others. They may plot a strategy in advance. It needs to be a clever one, because every prisoner must find his own name in order for any of them to survive.

Your fame as a logician has reached the prison and you have been called in to help. They want you to provide them with a strategy having a survival probability that exceeds 30%! They have connections on the outside, they remind you, and they know where you live.

## Question

## bonanova

It's time to paint the prison. The warden wants the cells cleared for the convenience of the painter. He devises a scheme by which his 100 prisoners either will be all freed or all executed. Either way, the painting will be made easier. His scheme offers a survival probability that seems terribly small.

In a room he places their names, on sheets of paper, in 100 wooden boxes,

numbered 1-100 andlined up on a table, one name to a box. Prisoners are led into the room one by one and are told to look inside the boxes in search of their name. Buteach prisonercan open at most 50 boxes. Successful or not, each prisoner must then leave the room, exactly as he found it, and he is permitted no further communication with the others. They may plot a strategy in advance. It needs to be a clever one, because every prisoner must find his own name in order for any of them to survive.Your fame as a logician has reached the prison and you have been called in to help. They want you to provide them with a strategy having a survival probability that exceeds 30%! They have connections on the outside, they remind you, and they know where you live.

## Link to comment

## Share on other sites

## 18 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.