display | more...

An old chestnut that I couldn't find. If it's already been noded, please tell me

There are 100 prisoners in a jail. The warden, having a soft spot for recreational mathematics, puzzles and logic, presents the inmates with an opportunity to earn their freedom. The guards line up the inmates and give each of them a sign, numbered from 1 to 100.

«In these 100 drawers—he explains—I will hide the cards, numbered from 1 to 100, randomly, exactly one per drawer. I will call every one of you at random and you can open 50 drawers, whichever you want. If you can find the card that matches your sign, you'll earn a point. If you collectively earn 100 points, I'll pardon all of you. Otherwise, it's back to your regular sentence!»

The inmates can make a plan ahead, but once the warden starts calling them, they can no longer communicate with each other, or else they'd risk incurring the anger of the trigger-happy guards. They will all be called in any order the warden desires and their guesses will be monitored, so that cheating with extra cards or lying is impossible.

What's the best strategy for the prisoners?

At first glance, it seems almost impossible. Each prisoner has essentially a 50% chance of finding out their number, and the probability of 100 independent events to all be successful is (1/2)100. However, there's a strategy that raises their odds to about 30%

Can you find it?

Standard puzzle provisions are, of course, in order: assume that the prisoners cannot cheat.

July 9, 2020 ⇐ Part of Brevity Quest 2020July 13, 2020