100 prisoners problem

The 100 prisoners problem is a mathematical puzzle that seems impossible, but it has a solution. And the solution only requires a bit of simple logic. Yet it still seems counterintuitive even when you know the answer!

The problem

A prison holds 100 prisoners, each with a unique prisoner number from 1 to 100.

One day the warder decides to torment the prisoners by offering them a chance of freedom. But with the odds stacked so they have no chance of winning.

He places 100 boxes, numbered 1 to 100, in a room. He then takes 100 cards, again numbered 1 to 100. He places a card in each numbered box, completely randomly. Here, we can see the contents of the boxes, but the prisoners cannot until they open each box:

The prisoners are allowed into the room, one at a time, tasked with finding their own number. They are allowed to look in a maximum of 50 boxes to try to find their number.

When they are finished, they must leave the room exactly as they found it, and they are not allowed to communicate with the other prisoners who have yet to enter the room.