Here’s a question to puzzle out:

An especially cruel jailer announces a “game” to their 100 prisoners. A cabinet with 100 drawers sits in a heavily-monitored room. In each drawer lies one prisoner’s number. If every prisoner draws their own number from a drawer, every one of them walks free; if even one of them fails, however, all the prisoners must spend the rest of their days in solitary confinement. Prisoners must reset the drawers and room after their attempt, otherwise all of them head to solitary, and to ensure they cannot give each other hints everyone goes directly to solitary after their attempt. The jailer does offer a little mercy, though: prisoners can check up to half the drawers in the cabinet during their attempt, and collectively they have plenty of time to brainstorm a strategy.

What is the best one they could adopt?

This seems like a hopeless situation, no doubt. The odds of any one prisoner randomly finding their number is 50%, and the odds of that happening 100 times are so low they make death by shark look like a sure thing.

Nonetheless, the prisoners settle on a strategy. With a little programming code, we can evaluate the chances it’ll grant all their freedom.

      Algorithm	    Trials	      Successes	Percentage
   Random Guess	     50000	              0	0.0000000
         Cyclic	     50000	          15687	31.3740000

Whhaaa? How can the prisoners pull off odds like that?

Rather than think of this in terms of drawers, picture a set of free-floating islands connected by bridges. This turns the problem into a graph, which will help us work out why the prisoner’s strategy works so well.

Oh wait, I never did describe their strategy, did I? Imagine each of the drawers is marked with one of the prisoner’s numbers (if they weren’t, the prisoners would imagine it for you). Each prisoner starts by opening the drawer with their number on it; if that’s their number then they’re done, obvs, but if it’s not then it tells them the next drawer they should open.

Mapping this onto the islands/bridges analogy creates some strict rules for how these bridges can connect islands. The bridges must be one way, because each drawer only contains one number, and every island has exactly one exit and one entrance, because no numbers are repeated or excluded. While it’d be silly in real life, in the analogy it’s legit for the entrance and exit of a bridge to touch the same island, as otherwise we couldn’t represent a drawer containing its own number.If you start on one island and follow the bridges, you’ll eventually find yourself back where you started; there are only a finite number of islands and bridges to see, after all. Each prisoner opening a drawer is like each of them being dropped onto a separate island, then following the path until they come to the island just before the one they started at (find their number in a drawer). Asking whether or not every prisoner finds their number is thus identical to asking if every prisoner makes it back to where they started within 50 bridge crossings.

Notice that this island/bridge collection is nothing but loops. If the longest loop it contains has less than 51 links, the prisoners are guaranteed to be free! So how often do specific loop sizes pop up?

If those numbers are randomly distributed, no loop length is more or less likely than any other: it’s just as likely that every drawer contains its matching number, as it is that each prisoner would have to open every drawer to find their number. But this means that half of the time there’s a loop which prevents at least half the prisoners from finding their number, so right off the bat we have a floor for how successful the prisoners could be.

These loops are mutually exclusive, however. If a loop of length 49 exists, then you know that the remaining boxes can only make a loop of 51 or less. You also know that the odds of that 51 loop are one in fifty-one, so if that 49-hop exists then the prisoners are almost guaranteed to succeed. In contrast, if you know a self-loop exists then the remaining loops could have sizes ranging between 1 and 99, so you haven’t gained much information at all.

Integrating across all this is tricky, but the basics are clear: the overall odds of this strategy’s success lie somewhere between 50% and .98%, the latter being the odds of a 49-hop loop existing but not a 51-hop one. That’s a helluva lot better than random guessing! We don’t need to work out the integral ourselves, as the prior brute-force trials gave us a success rate of about 31% (if you insist, Wikipedia has the deets), but we can also predict that during runs where all prisoners go free, there should be a bias to larger loop sizes.

And sure enough, that’s precisely what we see. Isn’t graph theory awesome?