2
$\begingroup$

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.

  • 1
    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 Restrepo2012-05-06

1 Answers 1

4

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

  • 1
    It does use the PHP, but Robin skipped this step.2010-09-18