75th NMO Selection Tests

Let us denote by $A_i=\{a\in A\mid a\equiv i(\mathrm{mod}2k)\}$ and by $a_i=|A_i|$ for each $i=0,\dots ,2k-1$. Observe that $A={\bigcup }_{i=0}^{2k-1}{A}_i$, where $A_i\cap A_j=\varnothing$ for $i\ne j$, and therefore $2n={\sum }_{i=0}^{2k-1}{a}_i$.

For any $a\in A_i$, we have $$P_a=\{b\in A\mid b-a\equiv k(\mathrm{mod}2k)\}=\{b\in A\mid b\equiv k+i(\mathrm{mod}2k)\}=A_{k+i},$$ where the index $k+i$ is considered modulo $2k$. Hence, $p_a=a_{k+i}$, for every $a\in A_i$.

Thus, $$E_A=\sum _{a\in A}{p}_a^2=\sum _{i=0}^{2k-1}\sum _{a\in A_i}{p}_a^2=\sum _{i=0}^{2k-1}{a}_i{a}_{k+i}^2=\sum _{i=0}^{k-1}{a}_i{a}_{k+i}^2+\sum _{i=k}^{2k-1}{a}_i{a}_{k+i}^2.$$ Since the indices are modulo $2k$, $$\sum _{i=k}^{2k-1}{a}_i{a}_{k+i}^2=\sum _{i=0}^{k-1}{a}_{k+i}{a}_i^2,$$ so we get $$E_A=\sum _{i=0}^{k-1}(a_i{a}_{k+i}^2+a_{k+i}{a}_i^2)=\sum _{i=0}^{k-1}{a}_i{a}_{k+i}(a_i+a_{k+i}).$$

We want to maximize $E_A$ under the constraint ${\sum }_{i=0}^{2k-1}{a}_i=2n$. Note that replacing any two distinct pairs $(a_i,a_{i+k})$ and $(a_j,a_{j+k})$ by $(a_i+a_j,a_{i+k}+a_{j+k})$ and $(0,0)$ does not decrease the value of $E_A$, because Therefore, the maximum is achieved when only one pair $(a_i,a_{i+k})$ is nonzero, with $a_i+a_{i+k}=2n$.

Using the inequality between arithmetic and geometric means, we have $E_A=a_i{a}_{i+k}(a_i+a_{i+k})\le \frac{(a_i+a_{i+k}{)}^3}{4}=2n^3$. The maximum value $2n^3$ is attained, for example, by any set $A$ having exactly $n$ multiples of $2k$ and $n$ numbers congruent to $k(\mathrm{mod}2k)$.