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

1

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).

enter image description here

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

enter image description here

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

  • 0
    @LovePaper by little room, I'm referring that no matter how many cards -B- has uncovered, and what their value is, the chance to uncover the right one in the next step will be $1/coveredCards$, because of the arrangement being randomly disposed2012-12-31