Thirty-one per cent, and a million would do as well
A hundred people. A hundred boxes, each holding one of their names in an
order nobody chose. Each person opens fifty boxes, alone, and puts everything back as
it was. They all go free only if every one of them finds their own name.
Guessing at random gives one chance in 2100, which is a decimal point
and thirty zeros. Opening boxes by following the names inside them gives
31.2% — and if there were a million of them instead of a hundred it would still
be 30.7%. The odds do not thin out, because the thing that sinks them is a
single loop that is too long, and a loop longer than half the boxes has no room for a
second.
One instruction, and no talking
Agreed beforehand, and then never again: the boxes are numbered, and so are you.
- Open your own number.
- It holds somebody's name. Open that person's number next.
- Keep going. Stop when you find your own name, or when you have opened fifty.
You are walking a loop. The name in your box points at a box, whose name points at another, and the only way back to the box you started from is through your own name — so the walk ends on you, or it does not end in time. Everybody walks the loop they are standing in, so everybody wins or nobody does, and the fate of the whole hundred hangs on one question: is the longest loop longer than fifty?
Why it is not a small number
Count the shuffles that have a loop of length k, for
k more than half of N. Choose which boxes are in it
(C(N,k)), arrange them into a loop ((k−1)!), shuffle the
rest ((N−k)!) — and that multiplies out to N!/k, whatever
k is. So a loop of length k turns up in one shuffle in
k.
Now the part that does the work. Two loops longer than half would need more than
N boxes between them, so there is at most one, and the cases
cannot overlap. Add them up and the chance of being sunk is
1/51 + 1/52 + … + 1/100, a piece of the harmonic series that is on its
way to ln 2. Everything else is the answer:
Where that argument stops working
The counting above leans on one sentence — there is at most one long loop —
and that sentence is true only while long means more than half. Allow
each person fewer than half the boxes and two overlong loops fit side by side, the
cases stop being separate, and adding them up counts some shuffles twice. The sum is
then not the answer but an over-estimate of the danger, so the formula reads
too low — and below N/e it goes below zero and stops even
pretending.
Both lines below are computed. The blue one is the sum above, used where it has no
right to be. The yellow one counts the shuffles properly, by a recurrence that takes
the loop containing box one and multiplies by what is left:
g(m) = (1/m) · Σ g(m−k) for k up to the limit. They lie on
top of each other from the halfway rule rightwards, and only there.
| may open | counted | the sum | the same? |
|---|
And it is not an argument about the shuffle
The strategy does not make the boxes friendlier; it makes a hundred separate
gambles into one. A hundred independent coin-flips at even odds is
2−100. Tying every person's fate to the same question — how
long is the longest loop — throws away all the ways to lose fifty-fifty and keeps
only one, and that one has a bit under a third of the room in it. To see that this is
not arithmetic on paper, the page also just plays it, with a seeded generator
so the tally below is the same every time this page is opened.
What this page checks about itself
Nothing here is a stored constant. The exact counts come from the recurrence, the formula from summing the harmonic tail, and the tally from playing the game · times with a seeded generator; the three are compared against one another rather than against a number typed in.