MathDB
IMC 2016, Problem 5

Source: IMC 2016

July 27, 2016
IMCIMC 2016prime numberspermutationscollege contests

Problem Statement

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(π)\mathrm{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(π)\mathrm{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}.
(Proposed by Fedor Petrov, St. Petersburg State University)
Back to ProblemsView on AoPS