Math E-320: Spring 2012

Teaching Math with a Historical Perspective

Mathematics E-320:

Instructor: Oliver Knill

Office: SciCtr 432

Email: knill@math.harvard.edu

(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 -> 8The 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 -> 62) 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 -> 8where 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