One helper who may swap two slips

Question

The setup is the classic one: 100 prisoners, 100 boxes with the prisoners' numbers inside in random order, each prisoner may open 50 boxes, and they use the follow-the-chain strategy. Everyone goes free only if all 100 succeed.

A sympathetic guard is allowed, before the first prisoner enters, to open every box, look at every slip, and swap the contents of exactly two boxes (or leave everything as it is). He knows the prisoners' strategy but cannot talk to them.

Can the guard guarantee that all 100 prisoners succeed? If so, what should he do?

Accepted Answer

Yes. If there is a cycle longer than 50, the guard swaps two slips on that cycle to cut it into two halves of length at most 50. Then every prisoner succeeds. The picture. The boxes and slips define a permutation: box b "points to" the number inside it. The chain strategy makes prisoner k walk around the cycle containing k, and she succeeds if that cycle has length at most 50. So the only bad arrangements are those with a cycle of length 51 or more, and since 51 + 51 is more than 100, there is at most one such cycle. What a swap does. Swapping the slips in two boxes that lie on the same cycle…

One helper who may swap two slips

Your answer

Discussion

Learn the concepts

Related questions