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

0

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
    The algorithm described in the original question shows that you must be wrong.2012-12-30
  • 0
    @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]] = N2012-12-30
  • 0
    Well in that case, you have found the answer in two steps.2012-12-30
  • 0
    @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.2012-12-30
  • 0
    @TonyK Never mind, maybe I need a cup of coffee2012-12-30
  • 0
    My algorithm and your algorithm looks the same. I think there must be a better solution, but I can't find it.2012-12-30
  • 0
    @LovePaper My solution is not an algorithm, but rhater an add-on to yours, by requiring -A- to swap two cards in the longest recursive sequence. If you don't add this condition there is a chance that -B- needs to open more than 49 boxes2012-12-30
  • 0
    @LovePaper So, by allowing to swap at most two cards the numbers of steps are reduced to 49 at most, which is why the swap could be introduced in the first place2012-12-30
  • 0
    @rraallvv Player A opens all the box, so the player can see the form of the cycle. Then, the player will switch two cards which minimizes the maximum length of the cycle.2012-12-31
  • 0
    @LovePaper I've clarified my answer2012-12-31
  • 0
    @rraallvv Thanks, but I want a better solution than $m = 49$.2012-12-31
  • 0
    @LovePaper No problem... I think it would require a formal demonstration, but my guess is that given an arrangement of cards, for each possible N would be a required X steps, and by swaping just two cards, the best thing one could do is to shorten the longest path, or greatest value for X. Given that the arrangement is disposed at random, there is litle room for what to do with the number on a card once it is revealed inside a box.2012-12-31
  • 0
    @rraallvv Can you give me some hints about the 'little room'? I thought about this for 2-3 months, but I can't find a solution better than m = 49.2012-12-31
  • 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