2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Hint: rot13(Rhyrevna Ahzoref). $\endgroup$
    – Vepir
    Feb 1 at 21:01
5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This argument via symmetry is ultimately the most efficient approach, but before I give you the checkmark, might you justify your penultimate line a little more? $\endgroup$
    – Feryll
    Feb 1 at 23:52
  • $\begingroup$ Gave it a try @Feryll. I'm not very good at explaining the obvious, though, so I'm not sure this makes it easier or harder to understand. $\endgroup$ Feb 2 at 2:05
  • $\begingroup$ Actually, I meant the part where you said "each inversion p_i>p_i+1 in a permutation p_1-p_2-...-p_n-1 adds one round" $\endgroup$
    – Feryll
    Feb 2 at 3:05
  • $\begingroup$ @Feryll Oh. Ok done. $\endgroup$ Feb 2 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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