uniolympiads Ελληνικά

IMC 2016, Day 1, Problem 5

Let SnS_n denote the set of permutations of the sequence (1,2,…,n)(1, 2, \dots, n). For every permutation π=(π1,…,πn)∈Sn\pi = (\pi_1, \dots, \pi_n) \in S_n, let inv⁡(π)\operatorname{inv}(\pi) be the number of pairs 1≤i<j≤n1 \le i < j \le n with πi>πj\pi_i > \pi_j; i.e. the number of inversions in π\pi. Denote by f(n)f(n) the number of permutations π∈Sn\pi \in S_n for which inv⁡(π)\operatorname{inv}(\pi) is divisible by n+1n + 1.

Prove that there exist infinitely many primes pp such that f(p−1)>(p−1)!pf(p-1) > \frac{(p-1)!}{p}, and infinitely many primes pp such that f(p−1)<(p−1)!pf(p-1) < \frac{(p-1)!}{p}.

Original from the official PDFLet S n denote the set of permutations of the sequence (1, 2, . . . , n) . For every permutation π = (π 1 , . . . , π n ) ∈ S n , let inv(π) be the number of pairs 1 ≤ i < j ≤ n with π i > π j ; i.e. the number of inversions in π . Denote by f (n) the number of permutations π ∈ S n for which inv(π) is divisible by n + 1 . Problem 5. Prove that there exist innitely many primes p such that f (p − 1) > many primes p such that f (p − 1) < (p − 1)! . p (p − 1)! , and innitely p

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Fedor Petrov, St. Petersburg State University)

Solution. We will use the well-known formula

∑π∈Snxinv⁡(π)=1⋅(1+x)⋅(1+x+x2)…(1+x+⋯+xn−1).\sum_{\pi\in S_n} x^{\operatorname{inv}(\pi)} = 1\cdot(1+x)\cdot(1+x+x^2)\ldots(1+x+\cdots+x^{n-1}).
(This formula can be proved by induction on nn. The cases n=1,2n = 1,2 are obvious. From each permutation of (1,2,…,n−1)(1,2,\ldots,n-1), we can get a permutation of (1,2,…,n)(1,2,\ldots,n) such that we insert the element nn at one of the nn possible positions before, between or after the numbers 1,2,…,n−11,2,\ldots,n-1; the number of inversions increases by n−1,n−2,…,1n-1,n-2,\ldots,1 or 00, respectively.)

Now let

Gn(x)=∑π∈Snxinv⁡(π).G_n(x) = \sum_{\pi\in S_n} x^{\operatorname{inv}(\pi)}.
and let ε=e2πin+1\varepsilon = e^{\frac{2\pi i}{n+1}}. The sum of coefficients of the powers divisible by n+1n+1 may be expressed as a trigonometric sum as
f(n)=1n+1∑k=0n−1Gn(εk)=n!n+1+1n+1∑k=1n−1Gn(εk).f(n) = \frac{1}{n+1}\sum_{k=0}^{n-1} G_n(\varepsilon^k) = \frac{n!}{n+1} + \frac{1}{n+1}\sum_{k=1}^{n-1} G_n(\varepsilon^k).
Hence, we are interested in the sign of
f(n)−n!n+1=∑k=1n−1Gn(εk)f(n) - \frac{n!}{n+1} = \sum_{k=1}^{n-1} G_n(\varepsilon^k)
with n=p−1n = p-1 where pp is a (large, odd) prime.

For every fixed 1≤k≤p−11\le k\le p-1 we have

Gp−1(εk)=∏j=1p−1(1+εk+ε2k+…+ε(j−1)k)=∏j=1p−11−εjk1−εk=(1−εk)(1−ε2k)⋯(1−ε(p−1)k)(1−εk)p−1.G_{p-1}(\varepsilon^k) = \prod_{j=1}^{p-1} \big(1 + \varepsilon^k + \varepsilon^{2k} + \ldots + \varepsilon^{(j-1)k}\big) = \prod_{j=1}^{p-1} \frac{1-\varepsilon^{jk}}{1-\varepsilon^k} = \frac{(1-\varepsilon^k)(1-\varepsilon^{2k})\cdots(1-\varepsilon^{(p-1)k})}{(1-\varepsilon^k)^{p-1}}.
Notice that the factors in the numerator are (1−ε)(1-\varepsilon), (1−ε2)(1-\varepsilon^2), …\ldots, (1−εp−1)(1-\varepsilon^{p-1}); only their order is different. So, by the identity (z−ε)(z−ε2)…(z−εp−1)=1+z+⋯+zp−1(z-\varepsilon)(z-\varepsilon^2)\ldots(z-\varepsilon^{p-1}) = 1 + z + \cdots + z^{p-1},
Gp−1(εk)=p(1−εk)p−1=p(1−e2kπip)p−1.G_{p-1}(\varepsilon^k) = \frac{p}{(1-\varepsilon^k)^{p-1}} = \frac{p}{\Big(1 - e^{\frac{2k\pi i}{p}}\Big)^{p-1}}.
Hence, f(p−1)−(p−1)!pf(p-1) - \frac{(p-1)!}{p} has the same sign as
∑k=1p−1(1−e2kπip)1−p=∑k=1p−1ek(1−p)πip(−2isin⁡πkp)1−p==2⋅21−p(−1)p−12∑k=1p−12cos⁡πk(p−1)p(sin⁡πkp)1−p.\begin{aligned} \sum_{k=1}^{p-1} \big(1 - e^{\frac{2k\pi i}{p}}\big)^{1-p} &= \sum_{k=1}^{p-1} e^{\frac{k(1-p)\pi i}{p}} \left( -2i\sin\frac{\pi k}{p} \right)^{1-p} = \\ &= 2\cdot 2^{1-p}(-1)^{\frac{p-1}{2}} \sum_{k=1}^{\frac{p-1}{2}} \cos\frac{\pi k(p-1)}{p} \left( \sin\frac{\pi k}{p} \right)^{1-p}. \end{aligned}
For large primes pp the term with k=1k = 1 increases exponentially faster than all other terms, so this term determines the sign of the whole sum. Notice that cos⁡π(p−1)p\cos\frac{\pi(p-1)}{p} converges to −1-1. So, the sum is positive if p−1p-1 is odd and negative if p−1p-1 is even. Therefore, for sufficiently large primes, f(p−1)−(n−1)!pf(p-1) - \frac{(n-1)!}{p} is positive if p≡3(mod4)p\equiv 3 \pmod 4 and it is negative if p≡1(mod4)p\equiv 1 \pmod 4.

Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?