This was question 9 in the Sydney University Mathematical Society Problem Competition 2012. My solution was quite different to the model solution — I use a decomposition technique common in graph theory and algorithm runtime analysis.
For a permutation of , a break of is an element of such that . The score of is the square of the number of breaks. Show that the average score of all permutations of tends to 0 as tends to inﬁnity.
First, note that
As a corollary, we can find so that
for all .
Now, let vary uniformly at random in and let be an indicator function that is 1 if is a break of , and 0 otherwise. We note that and are breaks of if and only if is a permutation when restricted to , and . This says:
Then, by the linearity of expectation:
and the squeeze theorem yields the required result.