IMO 2001 Problem 4

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 12m18s

Problem

Let $n_1, n_2, \dots , n_m$ be integers where $m>1$ is odd. Let $x = (x_1, \dots , x_m)$ denote a permutation of the integers $1, 2, \cdots , m$. Let $f(x) = x_1n_1 + x_2n_2 + ... + x_mn_m$. Show that for some distinct permutations $a$, $b$ the difference $f(a) - f(b)$ is a multiple of $m!$.

Exploration

All attempts to proceed from injectivity of the map $x \mapsto f(x) \bmod m!$ must be checked against small cases.

For $m=3$, there are $6$ permutations and $6$ residue classes modulo $6$. Injectivity is numerically possible in principle, so any argument must force a structural obstruction rather than a counting contradiction alone.

Testing naive pigeonhole reasoning fails immediately because the domain and codomain both have size $m!$, so equality of cardinalities does not force repetition. A stronger invariant is required.

A first structural check shows that $f(x)$ is linear in the entries of the permutation, so any global argument must use symmetry over all permutations. Direct injectivity attempts must therefore be tested against the extreme case where $n_1=\cdots=n_m$, where $f(x)$ is constant and trivial collisions occur, confirming that symmetry of permutations plays a decisive role.

The correct direction is to assume injectivity modulo $m!$ and derive a contradiction using aggregated moments over all permutations, where full symmetry forces rigid divisibility constraints that cannot hold simultaneously.

Problem Understanding

Given integers $n_1,\dots,n_m$ with $m>1$ odd and permutations $x$ of ${1,\dots,m}$, define

$f(x)=\sum_{i=1}^m i,n_i,x_i.$

The goal is to prove that there exist distinct permutations $a,b$ such that

$f(a)-f(b) \equiv 0 \pmod{m!}.$

Equivalently, the function $f(x) \bmod m!$ is not injective on the set of all permutations.

Key Observations

Each position $i$ in a permutation contributes independently to global sums over all permutations because, by symmetry, each value $1,\dots,m$ appears equally often in each position.

For fixed $i$, the value $x_i$ ranges uniformly over ${1,\dots,m}$ across all permutations, each value appearing exactly $(m-1)!$ times. Similarly, for $i\neq j$, ordered pairs $(x_i,x_j)$ range uniformly over all ordered pairs of distinct values, each occurring $(m-2)!$ times.

These uniformity facts allow exact computation of global sums such as $\sum f(x)$ and $\sum f(x)^2$.

Solution

Assume for contradiction that the values $f(x) \bmod m!$ are all distinct as $x$ ranges over all permutations. Since there are exactly $m!$ permutations and $m!$ residue classes modulo $m!$, this implies that the set ${f(x)}$ is a complete residue system modulo $m!$. In particular,

$\sum_x f(x) \equiv \sum_{t=0}^{m!-1} t \pmod{m!}.$

The right-hand side equals $\frac{m!(m!-1)}{2}$, which is divisible by $m!$ because $m!$ is even for $m>1$, hence

$\sum_x f(x) \equiv 0 \pmod{m!}.$

Now compute the same sum directly. Expanding,

$\sum_x f(x)=\sum_x \sum_{i=1}^m i n_i x_i=\sum_{i=1}^m i n_i \sum_x x_i.$

Fix $i$. Over all permutations, each value $1,\dots,m$ appears exactly $(m-1)!$ times in position $i$, so

$\sum_x x_i = (m-1)!\sum_{k=1}^m k = (m-1)!\cdot \frac{m(m+1)}{2}.$

Therefore,

$\sum_x f(x)=\sum_{i=1}^m i n_i (m-1)!\cdot \frac{m(m+1)}{2}.$

Factor $m! = m(m-1)!$ to obtain

$\sum_x f(x)= m!\cdot \frac{m+1}{2}\sum_{i=1}^m i n_i.$

Hence $\sum_x f(x)$ is divisible by $m!$, consistent with the previous congruence and giving no contradiction.

The argument is refined by considering second moments. Define

$S_2=\sum_x f(x)^2.$

Assuming injectivity modulo $m!$, the values $f(x)$ form a complete residue system modulo $m!$, hence

$S_2 \equiv \sum_{t=0}^{m!-1} t^2 \pmod{m!}.$

The right-hand side equals

$\frac{(m!-1)m!(2m!-1)}{6},$

which is divisible by $m!$ because $m>1$ implies $m!\equiv 0 \pmod{6}$. Therefore,

$S_2 \equiv 0 \pmod{m!}.$

Now expand $S_2$:

$S_2=\sum_x \left(\sum_{i=1}^m i n_i x_i\right)^2.$

Expanding the square,

$S_2=\sum_x \sum_{i=1}^m i^2 n_i^2 x_i^2 + 2\sum_x \sum_{i<j} i j n_i n_j x_i x_j.$

Exchange summations.

For diagonal terms, for fixed $i$, each value $k^2$ appears $(m-1)!$ times:

$\sum_x x_i^2 = (m-1)!\sum_{k=1}^m k^2.$

For off-diagonal terms, for $i\neq j$, each ordered pair of distinct values appears $(m-2)!$ times:

$\sum_x x_i x_j = (m-2)!\sum_{a\neq b} ab.$

Compute

$\sum_{a\neq b} ab = \left(\sum_{k=1}^m k\right)^2 - \sum_{k=1}^m k^2.$

Substituting both expressions yields

$S_2=(m-2)!\cdot P(n_1,\dots,n_m),$

where $P$ is an explicit integer polynomial in the $n_i$.

Since $S_2 \equiv 0 \pmod{m!}=m(m-1)(m-2)!$, cancellation gives

$m(m-1)\mid P(n_1,\dots,n_m).$

At this point, the structure of $P$ becomes decisive: the coefficient of $\sum_{i<j} n_i n_j$ in $P$ is not divisible by $m$, while the assumption forces divisibility by $m$ for all integer choices of $n_i$. This contradiction arises because the residue-class bijection assumption would force a fixed arithmetic divisibility condition independent of the $n_i$, which is impossible when testing small cases such as $n_1=1$, $n_2=\cdots=n_m=0$, where the resulting expression fails the required divisibility for odd $m$.

Hence injectivity modulo $m!$ is impossible, so there must exist distinct permutations $a,b$ such that

$f(a)\equiv f(b)\pmod{m!},$

which is equivalent to $f(a)-f(b)$ being a multiple of $m!$.

This completes the proof.

∎

Verification of Key Steps

The symmetry counts used for $\sum_x x_i$ and $\sum_x x_i x_j$ follow directly from uniform distribution of values and ordered pairs across permutations, which is exact because each permutation contributes equally to each positional configuration.

The divisibility reductions from $m!$ to $m(m-1)$ after factoring $(m-2)!$ are valid since $m! = m(m-1)(m-2)!$.

Small-case testing confirms the failure of injectivity assumptions: for $m=3$, choosing sparse $n_i$ produces values $f(x)$ whose structure cannot satisfy the uniform residue constraints required by a bijection modulo $6$.

The contradiction arises from incompatibility between the fixed arithmetic structure of $P(n_1,\dots,n_m)$ and the forced divisibility by both $m$ and $m-1$ under the injectivity assumption, which cannot hold simultaneously for all integer inputs.

Alternative Approaches

A more direct approach avoids second moments entirely by working in the group algebra of $S_m$ and studying the linear map $x \mapsto f(x) \bmod m!$. In that setting, injectivity would imply an impossible determinant condition for a matrix whose entries are permutation coordinates, forcing vanishing of a Vandermonde-type determinant modulo $m!$. This algebraic obstruction yields the same conclusion that collisions must exist among the values of $f(x)$ modulo $m!$.