Estonian Mathematical Olympiad

For positive integer $s$ denote by $a_s$ the number of pairs $(x,y)$, where $x,y$ are numbers on the board and $x+y=s$. Since the sum of two numbers on the board cannot be less than $2$ or greater than $2n$, the number of solutions of equation $x+y=z+w$ is $a_2^2+\cdots +a_{2n}^2$. Applying the AM-QM inequality to $a_2,\dots ,a_{2n}$ gives $$a_2^2+\cdots +a_{2n}^2\ge \frac{(a_2+\cdots +a_{2n}{)}^2}{2n-1}.$$ Since each pair $(x,y)$, where $x,y$ are numbers on the board, is counted exactly once in the sum $a_2+\cdots +a_{2n}$, the sum is equal to the number of pairs $k^2$. Hence $$\frac{(a_2+\cdots +a_{2n}{)}^2}{2n-1}=\frac{k^4}{2n-1},$$ which proves the claim.