Mathematical Reflections 2016, Issue 5 - Problem S389

Problem:
Let $n$ be a positive integer. Prove that for any integers $a_1, a_2, \ldots, a_{2n+1}$ there is a rearrangement $b_1, b_2, \ldots, b_{2n+1}$ such that $2^n\cdot n!$ divides $$(b_1-b_2)(b_3-b_4)\cdot \ldots \cdot (b_{2n-1}-b_{2n}).$$

Proposed by Cristinel Mortici, Valahia University, Targoviste, Romania

Solution:
Observe that we have $2n$ remainders modulo $2n$. By the pigeonhole principle there exist two integers among $a_1,a_2,\ldots,a_{2n+1}$, say $b_1$ and $b_2$, such that $(b_1-b_2)$ is divisible by $2n$. Now, discard $b_1$ and $b_2$. There remain $2n-1$ numbers among the ones in the given list. Since we have $2n-2$ remainders modulo $2n-2$, by the pigeonhole principle we have that there exist two integers, say $b_3$ and $b_4$, such that $(b_3-b_4)$ is divisible by $2n-2$. Proceeding in this way, we obtain a rearrangement $b_1, b_2, \ldots, b_{2n+1}$ of $a_1, a_2, \ldots, a_{2n+1}$ such that $$(b_1-b_2)(b_3-b_4)\cdot \ldots \cdot(b_{2n-1}-b_{2n})$$ is divisible by $2n\cdot (2n-2) \cdot (2n-4) \cdot \ldots \cdot 4 \cdot 2=2^n \cdot n!$.