3
$\begingroup$

There are $100$ boxes numbered from $1$ to $100$. A game is played by a host and two cooperating players $A$ and $B$.

The host puts $100$ cards (also numbered from $1$ to $100$) into the boxes in random order, one card in each box. Meanwhile, players $A$ and $B$ agree on a strategy.

Then, player $A$ enters the room, opens all the boxes, swaps at most one pair of cards, and leaves the room.

The host gives player $B$ an integer $n$, the number of the card player $B$ has to find.

Player $B$ enters the room and opens at most $m$ boxes, where the choice of boxes to open may depend on the cards found in boxes already opened. Then player $B$ has to select the box containing card $n$.

What is the least number $m$ such that player $B$ can always select the correct box, and what strategy leads to this $m$?


I was given this question by my friend, and I thought about it for a month, but I couldn't come up with anything. Can you give some advice? Thanks :)


I've found a solution for $m = 49$.

Let's define next[k] as the number of the card which box $k$ contains. Then we can proceed as follows.

(1) open box n.

(2) if box n does not contain n, open next[n].

(3) if box next[n] does not contain n, open next[next[n]].

(4) repeat while card n is not found.

n, next[n], next[next[n]], ... form a cycle, and the maximum length of the cycle will be m+1. So the following strategy works.

(1) Player $A$ can open all the boxes and see the form of the cycle and switch two cards which minimize the maximum length of the cycle.

(2) Player $B$ reveals the cards according to the above algorithm. If player $B$ reveals $49$ cards, he knows that the last card must be n, so m = 49.

1 Answers 1