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$.
next[k] as the number of the card which box $k$ contains. Then we can proceed as follows.
(1) open box
(2) if box
n does not contain
(3) if box
next[n] does not contain
(4) repeat while card
n is not found.
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
m = 49.