MathDB
Hard algebra with permutations from KoMaL

Source: KoMaL A. 727

May 21, 2023
algebrapermutationsInequality

Problem Statement

For any finite sequence (x1,…,xn)(x_1,\ldots,x_n), denote by N(x1,…,xn)N(x_1,\ldots,x_n) the number of ordered index pairs (i,j)(i,j) for which 1≤i<j≤n1 \le i<j\le n and xi=xjx_i=x_j. Let pp be an odd prime, 1≤n<p1 \le n<p, and let a1,a2,…,ana_1,a_2,\ldots,a_n and b1,b2,…,bnb_1,b_2,\ldots,b_n be arbitrary residue classes modulo pp. Prove that there exists a permutation π\pi of the indices 1,2,…,n1,2,\ldots,n for which N(a1+bπ(1),a2+bπ(2),…,an+bπ(n))≤min⁡(N(a1,a2,…,an),N(b1,b2,…,bn)).N(a_1+b_{\pi(1)},a_2+b_{\pi(2)},\ldots,a_n+b_{\pi(n)})\le \min(N(a_1,a_2,\ldots,a_n),N(b_1,b_2,\ldots,b_n)).
Back to ProblemsView on AoPS