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
.