IMO 1972 SL 8

Origin: GBR

Problem

Let m and n be nonnegative integers. Prove that m!n!(m+ n)! divides (2m)!(2n)!.

Solution

Let f(m, n) = (2m)!(2n)! m!n!(m+n)!. Then it is directly shown that f(m, n) = 4f(m, n −1) −f(m + 1, n −1), and thus n may be successively reduced until one obtains f(m, n) =  r crf(r, 0). Now f(r, 0) is a simple binomial coefficient, and the cr’s are integers. Second solution. For each prime p, the greatest exponents of p that divide the numerator (2m)!(2n)! and denominator m!n!(m + n)! are respectively  k>0 2m pk

2n pk  and  k>0  m pk

n pk

m + n pk  ; hence it suffices to show that the first exponent is not less than the second one for every p. This follows from the fact that for each real x, [2x]+[2y] \geq

[x] + [y] + [x + y], which is straightforward to prove (for example, using [2x] = [x] + [x + 1/2]).