IMO 1972 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 7m11s

Problem

Let $m$ and $n$ be arbitrary non-negative integers. Prove that $$ \frac{(2m)!(2n)!}{m!n!(m+n)!} $$ is an integer. ($0! = 1$.)

Exploration

Consider small values of $m$ and $n$ to examine the expression

$$\frac{(2m)!(2n)!}{m! n! (m+n)!}.$$

For $m = n = 0$, the expression equals $\frac{0! \cdot 0!}{0! \cdot 0! \cdot 0!} = 1$. For $m = 1$, $n = 0$, it equals $\frac{2! \cdot 0!}{1! \cdot 0! \cdot 1!} = 2$. For $m = n = 1$, it equals $\frac{2! \cdot 2!}{1! \cdot 1! \cdot 2!} = 2$. For $m = 2$, $n = 1$, it equals $\frac{4! \cdot 2!}{2! \cdot 1! \cdot 3!} = \frac{24 \cdot 2}{2 \cdot 1 \cdot 6} = 4$. These initial computations suggest the expression is always integral.

One approach is to attempt a combinatorial interpretation. The numerator $(2m)!(2n)!$ can be interpreted as counting sequences of length $2m$ and $2n$, and the denominator $m! n! (m+n)!$ resembles multinomial coefficients. Alternatively, one might analyze divisibility using prime factorization, i.e., Legendre's formula: for a prime $p$, the exponent of $p$ in $k!$ is $\sum_{i=1}^{\infty} \lfloor k/p^i \rfloor$. Then integrality reduces to verifying that the exponent of every prime $p$ in the numerator is at least as large as in the denominator. The tricky step is handling the floor functions carefully for general $m$ and $n$.

A second approach uses induction on $m+n$, attempting to relate the expression for $(m,n)$ to $(m-1,n)$ or $(m,n-1)$.

The most delicate step is proving that the floor sum inequalities hold for all primes simultaneously, which is subtle because floors are discontinuous functions.

Problem Understanding

The problem asks to show that for all non-negative integers $m$ and $n$, the ratio

$$\frac{(2m)!(2n)!}{m! n! (m+n)!}$$

is always an integer. This is a Type B problem: a statement is given and must be proved for all non-negative integer inputs. The objects involved are factorials of integers, which count permutations, and the challenge is to demonstrate exact divisibility for all pairs $(m,n)$.

The core difficulty is that factorials grow rapidly, and naive manipulation of factorials does not immediately reveal divisibility. A direct combinatorial or number-theoretic argument must establish integrality for all primes and all integers $m,n$.

Proof Architecture

The main strategy will be to prove the statement using Legendre's formula for the exponent of a prime $p$ in factorials. The proof structure is:

Lemma 1. For any prime $p$ and integer $k \ge 0$, the exponent of $p$ in $k!$ is

$$\nu_p(k!) = \sum_{i=1}^{\infty} \left\lfloor \frac{k}{p^i} \right\rfloor.$$

This is a standard combinatorial identity obtained by counting multiples of powers of $p$ in $1,2,\dots,k$.

Lemma 2. For all non-negative integers $m$ and $n$ and all integers $i \ge 1$, the inequality

$$\lfloor \frac{2m}{p^i} \rfloor + \lfloor \frac{2n}{p^i} \rfloor \ge \lfloor \frac{m}{p^i} \rfloor + \lfloor \frac{n}{p^i} \rfloor + \lfloor \frac{m+n}{p^i} \rfloor$$

holds. This is the key technical step; it reduces the problem to showing a certain inequality between sums of floor functions.

The overall proof will compute $\nu_p$ for the numerator and denominator and show that the exponent in the numerator is always at least as large as in the denominator for each prime. The most delicate step is Lemma 2, which must be carefully justified.

Solution

Lemma 1

For any prime $p$ and non-negative integer $k$, the exponent of $p$ in $k!$, denoted $\nu_p(k!)$, is

$$\nu_p(k!) = \sum_{i=1}^{\infty} \left\lfloor \frac{k}{p^i} \right\rfloor.$$

Proof. Each integer between $1$ and $k$ contributes a certain number of factors of $p$. An integer divisible by $p^i$ contributes one factor counted in $\lfloor k/p^i \rfloor$. Since higher powers are included in lower powers, summing over all $i \ge 1$ counts all powers exactly once. The sum terminates since $\lfloor k/p^i \rfloor = 0$ for $p^i > k$. ∎

This establishes a precise formula for the exponent of any prime in a factorial.

Lemma 2

For all non-negative integers $m$ and $n$, all primes $p$, and all integers $i \ge 1$, the inequality

$$\lfloor \frac{2m}{p^i} \rfloor + \lfloor \frac{2n}{p^i} \rfloor \ge \lfloor \frac{m}{p^i} \rfloor + \lfloor \frac{n}{p^i} \rfloor + \lfloor \frac{m+n}{p^i} \rfloor$$

holds.

Proof. Let $a = \lfloor m/p^i \rfloor$ and $b = \lfloor n/p^i \rfloor$, and write $m = a p^i + r$ and $n = b p^i + s$ with $0 \le r,s < p^i$. Then

$$\lfloor 2m/p^i \rfloor = \lfloor 2a + 2r/p^i \rfloor = 2a + \lfloor 2r/p^i \rfloor,$$

and similarly $\lfloor 2n/p^i \rfloor = 2b + \lfloor 2s/p^i \rfloor$. Also,

$$\lfloor (m+n)/p^i \rfloor = \lfloor (a+b) + (r+s)/p^i \rfloor = a+b + \lfloor (r+s)/p^i \rfloor.$$

Then the inequality becomes

$$2a + \lfloor 2r/p^i \rfloor + 2b + \lfloor 2s/p^i \rfloor \ge a + b + \lfloor r/p^i \rfloor + \lfloor s/p^i \rfloor + a+b + \lfloor (r+s)/p^i \rfloor.$$

Simplifying, this reduces to

$$\lfloor 2r/p^i \rfloor + \lfloor 2s/p^i \rfloor \ge \lfloor r/p^i \rfloor + \lfloor s/p^i \rfloor + \lfloor (r+s)/p^i \rfloor.$$

Since $0 \le r,s < p^i$, we have $\lfloor r/p^i \rfloor = \lfloor s/p^i \rfloor = 0$, and $0 \le r+s < 2p^i$, so $\lfloor (r+s)/p^i \rfloor$ is either $0$ or $1$. Also $\lfloor 2r/p^i \rfloor$ and $\lfloor 2s/p^i \rfloor$ are either $0$ or $1$. Checking the four possibilities for $r+s < p^i$ or $r+s \ge p^i$ confirms the inequality. ∎

This establishes the critical floor function inequality needed for the prime exponent comparison.

Main Proof

Fix a prime $p$. Using Lemma 1, the exponent of $p$ in the numerator is

$$\nu_p((2m)!) + \nu_p((2n)!) = \sum_{i=1}^{\infty} \lfloor 2m/p^i \rfloor + \sum_{i=1}^{\infty} \lfloor 2n/p^i \rfloor,$$

and the exponent of $p$ in the denominator is

$$\nu_p(m!) + \nu_p(n!) + \nu_p((m+n)!) = \sum_{i=1}^{\infty} \lfloor m/p^i \rfloor + \sum_{i=1}^{\infty} \lfloor n/p^i \rfloor + \sum_{i=1}^{\infty} \lfloor (m+n)/p^i \rfloor.$$

Applying Lemma 2 termwise for each $i$,