How long will it take to hand out the shuffled papers?

Question

A teacher has $n$ students sit in a circle in her classroom. She holds in her hands a perfectly shuffled stack of the students' graded homework, with Juan's on top. She is currently standing in front of Juan, and intends to hand out the homework by repeatedly (1) seeing whose paper is on the top of the stack, and then (2) walking clockwise to that student to hand over the homework. She will finish by continuing to walk clockwise back to Juan.

For example, if the stack were perfectly in order with the students' clockwise positions, then she would do exactly one rotation in total. In the worst case scenario, if the stack were perfectly in order with the students' counterclockwise positions, then she would do exactly $n-1$ rotations in total.

How many rotations will she be performing on average?

Answer 1

That should be

n/2 if n>1

Reasoning:

We can group the set of all permutations (excluding Juan who serves as an anchor) into pairs by associating each permutation with its up-side-down, for example, if there are 5 people plus Juan 4-3-5-2-1 (read: 1st in stack is 4th in circle 2nd in stack is 3rd in circle etc.) would be associated with 1-2-5-3-4. The number of rounds is one in the best case. Counting rounds by counting how often we passed Juan it is clear that each inversion p_i>p_i+1 in a permutation p_1-p_2-...-p_n-1 adds one round. As the up-side-down permutation consists of the same pairs but each pair flipped each of the n-2 pairs is an inversion in exactly one: either the original or the up-side-down permutation. (Formally, writing the up-side-down of p_1-p_2-... as q_1-q_2-... we have (q_i,q_i+1) = (p_n-i,p_n-i-1) ). From this it is clear that each pair of associated permutations totals n-2 inversions, hence the average is n/2.