Home > Riddles > The hundred numbered boxes

The hundred numbered boxes

Chance and uncertaintyLevel 4 · Advanced · ●●●●○

There are 100 prisoners numbered 1 to 100. In a room there are 100 closed boxes, also numbered 1 to 100.

Inside each box is a piece of paper with a number from 1 to 100 (each number appears exactly once, randomly distributed). The prisoners enter the room one by one.

Each one can open up to 50 boxes by looking for the paper with their number. If EVERYONE finds his number, everyone is free.

If at least one fails, they all die. They cannot communicate after entering the room or leave clues.

Is there a strategy that gives them more than a 30% chance of success?

Hints

Show hints
  1. Key: A prisoner hits if and only if the loop it belongs to has length $\le 50$.
  2. Since two cycles >50 cannot coexist in 100 elements, the failure event is the disjoint union: P(failure)=sum_ k=51 ^ 100 frac1k.
  3. That ~31% drastically outperforms the random strategy (2^ -100 for collective success).

Solution

Show full solution

Answer: YES there is a strategy with ~31% probability of success.
Hundred boxes: cycle-following strategy (small example)
Cycle strategy:
Each prisoner first opens his own box and then follows the chain indicated by the numbers found:

  1. Open box $i$ (your number).
  2. If there is $j$ inside, open box $j$.
  3. Repeat until you find your number or exhaust 50 openings.

The roles form a permutation of $\{1,\dots,100\}$, and therefore a decomposition into disjoint cycles.
Key: a prisoner hits if and only if the cycle it belongs to has length $\le 50$.
Then everyone guesses correctly if and only if there is no cycle of length greater than 50.
Since two $>50$ cycles cannot coexist in 100 elements, the failure event is the disjoint union:

$$ P(\text{fracaso})=\sum_{k=51}^{100}\frac1k. $$

Therefore,

$$ P(\text{success})=1-\sum_{k=51}^{100}\frac1k\approx 0.31. $$

That ~31% drastically outperforms the random strategy ($2^{-100}$ for collective success).


Related riddles

Keep practicing

If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.

← Previous: The thousand poisoned bottles · Next: The hundred prisoners with hats →