# pigeon-hole and parity

From an olympic book:

Let $m$ be an odd number and $a_1, ... , a_m$ integers. $x=(x_1,...,x_m)$ is a permutation of the integers $1, ..., m$ and $f$ at $x$ is defined by $f(x)=x_1a_1 + ... + x_m a_m$. Prove that there exist two permutations $x$ and $y$ such that $f(x)-f(y)$ is divisible by $m!$.

I'm aware of a few facts. For instance, if all $a_i$ are odd (or even), any permutations of $x$ results in values of $f$ of the same parity, but there are only $m!/2$ (for $m>1$) residues module $m!$ of the same parity, and an application of the Pigeon Hole Principle yields the conclusion. So in the general case I'd like to say something like there's a greater number of permutations that give a value of $f$ of one parity than the other. I don't know how to show this.

• "Un recorrido por la Teoría de Números", by Fabio Brochero and Juan Ignacio Restrepo, published by Olimpiadas Colombianas de Matemáticas. Now you can see why I didn't cite it :) – Weltschmerz Sep 18 '10 at 13:39
• Gracias. Sources in any language, and even when obscure, are actually useful information. Here the book is not online, but from the title and publisher it sounds like it is more an introductory training book than a collection of hardest-ever problems from the competitions, so the problem might be one where it is not too difficult to try to solve and post the solution. But if it was a near-impossible problem that nobody could solve at the IMO, the calculation might be different. – T.. Sep 18 '10 at 18:41
• This is problem 4 from IMO 2001. It does use PHP. I'm glad to see that my book is cited on the Internet :) Juan Ignacio Restrepo – user30726 May 6 '12 at 1:45

## 1 Answer

Let $$S=\{(x_1,\ldots,x_m):x_1,\ldots,x_m\textrm{ is a permutation of }1,\ldots m\}.$$ So for a vector $a=(a_1,\ldots,a_m)\in\mathbb{Z}^n$ we need to show there are distinct $x$, $y\in S$ with $x\cdot a\equiv y\cdot a$ (mod $m!$). If this wasn't true, $x\cdot a$ runs through all congruence classes modulo $m!$ as $x$ runs through $S$. Therefore $$\left(\sum_{x\in S}x\right)\cdot a\equiv\sum_{k=0}^{m!-1}k\pmod{m!}.$$ Each coordinate of $X=\sum_{x\in S}x$ equals $(m-1)!\sum_{j=1}^m j$. But since $m$ is odd, this is divisible by $m!$. Hence $X\cdot a\equiv0$ (mod $m!$) but $\sum_{k=0}^{m!-1}k\not\equiv0$ (mod $m!$).

• Thank you, Robin Chapman. That's a very nice solution. It doesn't even use the PHP (at least not in its usual fashion) and parity. I'm still curious, though, whether there's another solution, since the problem is in the PHP section, far behind the chapters on congruences. – Weltschmerz Sep 18 '10 at 14:24
• It does use the PHP, but Robin skipped this step. – Yuval Filmus Sep 18 '10 at 16:37