Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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

share|improve this answer
    
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
show 9 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.