免费智力题困难

One Hundred Prisoners and One Hundred Boxes

考察公司OptiverIMC TradingSIG

One hundred prisoners are numbered 1 to 100. In a room are 100 closed boxes, and inside them, in random order, are slips bearing the numbers 1 to 100.

Each prisoner enters alone, may open at most 50 boxes, and must find the slip bearing their own number. Boxes are closed again afterwards and no communication is allowed once the process begins. All prisoners must succeed or all are executed.

They may agree a strategy beforehand. Find a strategy that succeeds with probability greater than 30%.

解析

先自己试一试，卡住了再打开提示。

查看解析

The naive baseline. If each prisoner opens 50 boxes at random, each succeeds with probability $\tfrac12$ , and all succeed with probability $2^{-100} \approx 10^{-30}$ .

The strategy. Prisoner $k$ opens box $k$ first. Whatever number is on the slip inside, they open that box next, and keep following the slips, up to 50 boxes.

Step 1: The slips form loops. Draw an arrow from each box to the box named by the slip inside it. Every box has exactly one arrow going out (its own slip) and exactly one coming in (exactly one slip names it). So the arrows split the boxes into closed loops.

Eight boxes. Arrows run from each box to the box named by its slip, forming loops of 4, 3 and 1. Prisoner 1 follows boxes 1, 4, 7, 2 and finds slip 1 in box 2.

Step 2: Why this helps. Prisoner $k$ starts at box $k$ and walks around the loop that contains box $k$ . Slip $k$ is in the box whose arrow points back to box $k$ , which is the last box of the loop. So prisoner $k$ finds their slip after exactly as many boxes as the loop has. That means:

prisoner $k$ succeeds exactly when the loop through box $k$ has at most $50$ boxes;
everyone succeeds exactly when no loop has more than $50$ boxes.

Step 3: Count the arrangements with a long loop. All $100!$ ways of putting the slips in the boxes are equally likely. Fix a length $\ell$ between $51$ and $100$ . Every arrangement with a loop of exactly $\ell$ boxes can be built in three steps:

Choose which $\ell$ boxes are in the long loop: $\binom{100}{\ell}$ ways. This is just picking a set of $\ell$ boxes out of $100$ ; the order comes in the next step.
Join those $\ell$ boxes into one loop: $(\ell - 1)!$ ways. Start from the smallest box in the set. The other $\ell - 1$ boxes can follow it in any order, and each order is a different loop. Once the loop is fixed, so are the slips in these boxes: each box holds the number of the next box.
Fill the other $100 - \ell$ boxes with the other $100 - \ell$ slips in any way: $(100 - \ell)!$ ways.

The six ways to join boxes 1, 2, 3, 4 into one loop: box 1 comes first and the other three follow in any of 3! = 6 orders.

No arrangement is counted twice, because two loops longer than $50$ would need more than $100$ boxes. Multiplying, and using $\ell! = \ell \cdot (\ell - 1)!$ :

\binom{100}{\ell}(\ell - 1)!\,(100 - \ell)! = \frac{100!}{\ell!\,(100 - \ell)!} \cdot (\ell - 1)!\,(100 - \ell)! = \frac{100!}{\ell}.

Dividing by the $100!$ arrangements in total:

P(\text{there is a loop of exactly } \ell \text{ boxes}) = \frac{1}{\ell}.

Check on a small case: with $4$ boxes and a loop of $3$ , the steps give $\binom43 \cdot 2! \cdot 1! = 8$ , and $4!/3 = 8$ .

Step 4: The probability. At most one loop can be longer than $50$ , so these events for different $\ell$ never happen together, and we can add them:

P(\text{some loop is longer than } 50) = \frac{1}{51} + \frac{1}{52} + \dots + \frac{1}{100} \approx 0.6882.

Answer:

P(\text{all survive}) \approx 1 - 0.6882 = 0.3118,

just over 31%.

With more prisoners, $2n$ prisoners each opening $n$ boxes, the sum $\frac{1}{n+1} + \dots + \frac{1}{2n}$ approaches $\ln 2$ . So the chance of survival only falls to $1 - \ln 2 \approx 0.307$ , even with a million prisoners.

Why interviewers like it. Random guessing makes the prisoners succeed or fail independently. Following the loops ties their fates together, so everyone succeeds on the same event: no long loop.

题目

解析