In Living With Crazy Buttocks  I posed a problem where 20 party guests were each given an unusual book.  These books were placed in identical boxes.  The guests enter the room with the boxes one at a time and are allowed to open half of the boxes.  They leave by a different door and cannot communicate with the other guests.  The room is put back identically before the next guest enters.

If every guest finds their book then the whole group win a trip to Paris.

What is their best strategy?

This puzzle comes from a Peter Winkler book, Mathematical Mind-Benders.   It was called Names in Boxes and was about prisoners trying to escape the death penalty.

This is the guests best strategy:

Associate each box with one of the guests.  Each guest first opens their own box.  If they find their own book they can stop.  Otherwise they open the box associated with the owner of the book.  They keep doing this until they find their own book or have opened 10 boxes.

Incredibly this gives them more than a 33% chance of success.  Even more incredibly this strategy will always have a better than 30% chance of success regardless of the number of guests.

To see how this works lets imagine that Stan repeats the procedure forever.  At some point he will find his book.  Next he will open his own box again.  He will repeat the same loop endlessly.  

If this loop contains up to ten boxes then all of the guests whose boxes lie in the loop will find their book.

The procedure splits the boxes into separate loops.  If no loop is bigger than ten then all of the guests will succeed, otherwise most of them will fail.

It is still true each individual guest has a fifty-fifty chance, the procedure means that they tend to succeed or fail together.

So what is the chance of success?

We have come across these sorts of loops before in Follow Up: Loops and the Harmonic Series. In the comments we noted that on average there will be 1/r loops of length r. As we are interested in loops containing more than half the boxes there can only be one such loop, so we can say the chance of a loop of length r is 1/r.

First we calculate the number of loops of length r if we have n boxes, in the puzzle n =10.  There are n!/r!(n-r)! ways of choosing r boxes and there are r! ways of ordering them.   We could have chosen any box in the loop to be the first one so to avoid double counting we must divide by r.  This gives (n!/r!(n-r)!)r!/r = n!/r(n-r)!

The other n-r boxes could be arranged in (n-r)! ways.  In total there are n! arrangements of all n boxes.  So a random arrangment will have on average (n-r)!/n! occurrences of a particular loop.  

A random arrangement will have on average (n!/r(n-r)!)((n-r)!/n!) = 1/r loops of length r.

Since there can only be one loop larger than 10 this means the chance of success is 1 -1/11 -1/12 -… -1/20 which is about 0.331229…

As the number of guests increases this tends to 1 – integral[ N<x<2N ]( 1/x ) = 1 – ln 2N + ln N = 1 – ln 2 = 0.3068528…

However many guests there are they will always have a better than 30% chance of success!