Solution to the swapper problem:

1) Every permutation can be decomposed into cycles. Start with a point 1 and apply the permutation again and again. For example, the permutation

   (1,2,3,4,5,6,7,8)
         |
   (4,5,2,3,7,1,6,8) 

has consists of one big cycle and a fixed point

    1 -> 4 -> 3 -> 2 -> 5 -> 7 -> 6 -> 1     8 -> 8

The permutation

   (1,2,3,4,5,6,7)
         |
   (2,3,4,1,7,6,5) 

has three cycles

    1-> 2 -> 3 -> 4 -> 1     5 -> 7 -> 5     6 -> 6

2) We can compose any permutation with a swap so that all cycle lengths are smaller or equal than half of the number of elements.
In the first example, we can swap 3 with 6

   (1,2,3,4,5,6,7,8)
         |
   (4,5,1,3,7,2,6,8) 

and get the cycle structure

    1 -> 4 -> 3 -> 1       2 -> 5 -> 7 -> 6 -> 2      8 -> 8

where each cycle has length smaller or equal to 4. 3) In the swapper problem, let the swapper do exactly this. No, the boxes are ordered according to a permutation where each cycle has length smaller or equal than 10.

4) Each person goes in and chooses the box with his own number, then looks up the number which is there, opens that box, then looks at that number, opens the next box etc. Like this, the person follows the permutation and since the cycle structure of each cycle is smaller or equal to 10, each person will get his number in less or equal than 10 hits.

Please send questions and comments to knill@math.harvard.edu

Math E320| Oliver Knill | Spring 2012 | Extension School | Harvard University