# Least number of inspections to find a given card

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.

-

Your algorithm is right, I think that by adding a rule to tell how to choose the two cards to swap, it would be complete.

One thing that could hapen is that an arragment of cards could have many small sequences of loops (image - a), or even a sequence with all 100 cards (image - b).

If -A- doesn't swap the two cards, or does it the wrong way, -B- could need to open more than 49 boxes using your algorithm, no matter what value N is.

So, what can -A- do, after he opens all the boxes and sees what the numbers are?

-A- has to cut by two halves the longest sequence, as follows

Now your algorithm can be used, finding N in at most 49 steeps as you have explained

I think you already have found the correct algorimth, provided that -A- swaps the two cards in an appropiate way, as described above

-
The algorithm described in the original question shows that you must be wrong. –  TonyK Dec 30 '12 at 17:19
@TonyK "the maximum length of the cycle will be m+1" what if there is more than a pair of cards that are recursive. I open box N then next[N], but next[next[N]] = N –  rraallvv Dec 30 '12 at 17:36
Well in that case, you have found the answer in two steps. –  TonyK Dec 30 '12 at 17:38
@TonyK True, I was missing the bit when B starts with the box labeled with the required number, I was taking N as a random number too. Which could give an infinite loop. –  rraallvv Dec 30 '12 at 17:48
@TonyK Never mind, maybe I need a cup of coffee –  rraallvv Dec 30 '12 at 17:50