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.

### Problem:

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.

### Solution:

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.