Maths Olympiad Prep

Library / /16 of 52

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Romania

Let nn be a positive integer, let SnS_n be the set of all permutations of the set {1,2,,n}\{1, 2, \dots, n\}, and, for each σ\sigma in SnS_n, let I(σ)={i:σ(i)i}I(\sigma) = \{i: \sigma(i) \le i\}. Evaluate the sum
σSn1I(σ)iI(σ)(i+σ(i)). \sum_{\sigma \in S_n} \frac{1}{|I(\sigma)|} \sum_{i \in I(\sigma)} (i + \sigma(i)).

Solution

Consider the involution of SnS_n which sends a permutation σ\sigma to the permutation σ\sigma^* defined by σ(i)=j\sigma^*(i) = j if and only if σ(nj+1)=ni+1\sigma(n-j+1) = n-i+1. Notice that, for each σ\sigma in SnS_n, the assignment inσ(i)+1i \mapsto n-\sigma(i)+1 defines a bijection from I(σ)I(\sigma) to I(σ)I(\sigma^*) whose inverse sends jj to nσ(j)+1n-\sigma^*(j)+1. Consequently,
σSn1I(σ)iI(σ)(i+σ(i))==12σSn(1I(σ)iI(σ)(i+σ(i))+1I(σ)iI(σ)(i+σ(i)))=12σSn1I(σ)iI(σ)(i+σ(i)+(nσ(i)+1)+(ni+1))=(n+1)!. \begin{align*} \sum_{\sigma \in S_n} \frac{1}{|I(\sigma)|} \sum_{i \in I(\sigma)} (i + \sigma(i)) &= \\ &= \frac{1}{2} \sum_{\sigma \in S_n} \left( \frac{1}{|I(\sigma)|} \sum_{i \in I(\sigma)} (i + \sigma(i)) + \frac{1}{|I(\sigma^*)|} \sum_{i \in I(\sigma^*)} (i + \sigma^*(i)) \right) \\ &= \frac{1}{2} \sum_{\sigma \in S_n} \frac{1}{|I(\sigma)|} \sum_{i \in I(\sigma)} (i + \sigma(i) + (n - \sigma(i) + 1) + (n - i + 1)) \\ &= (n + 1)! . \end{align*}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.