# Cycling through prison

In a small prison, $$100$$ prisoners are huddled together in a room, accompanied by their lawyer. They each are numbered from $$1$$ to $$100$$. The only door in that room leads to a small courtyard in which there are $$100$$ boxes, numbered from $$1$$ to $$100$$. Each box also contains a unique number in the set $$\{1,2,\dots,100\}$$, not necessarily equal to its own number.

At a given moment, each prisoner steps outside, one at a time. This prisoner can open at most $$50$$ boxes. If his or her number is present in one of these boxes, he/she is given freedom. In any case, the prisoner is afterwards obligated to leave the courtyard and cannot return to the room with the other prisoners. The boxes are then resealed, and the next prisoner enters the courtyard.
Before this experiment starts, they are allowed to discuss a plan. Moreover, the lawyer is allowed to go onto the courtyard before anyone else. There, she can look at the contents of any box and, if she wants to, she can switch the contents of two boxes. Afterwards, she has to leave and is not allowed to return to the prisoners.

What strategy will result in everyone's freedom?

Source: some friend told me, once.

Every prisoner has to do the following: go to the box that has the same number as yours. Open the box. If this box has your number in it, hooray, freedom awaits! If not, go to the box that shares this newly found number and repeat the process.

When using the above strategy, one 'cycles' through the boxes. If you consider all cycles that arise in this way, the puzzle is solved when no cycles of length greater than $$50$$ exists. That's were the laywer comes into play. She can look at all the boxes and write down all existing cycles. If a cycle of length greater than $$50$$ exists, she can terminate that cycle at length $$50$$ by putting the correct number in the $$50^\text{th}$$ box (pointing towards the first box). This switch will always result in cycles of length at most $$50$$.

Remarks? Want to submit your own solution? Don't hesitate to send me an email!