Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
"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
add comment

1 Answer

up vote 4 down vote accepted

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!$).

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.