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.

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