IMO 1967/A3 solution

IMO 1967

Problem A3

Let k, m, n be natural numbers such that m + k + 1 is a prime greater than n + 1. Let c_s = s(s+1). Prove that:

(c_m+1 - c_k)(c_m+2 - c_k) ... (c_m+n - c_k)

is divisible by the product c₁c₂ ... c_n.

Solution

The key is that c_a - c_b = (a - b)(a + b + 1). Hence the product (c_m+1 - c_k)(c_m+2 - c_k) ... (c_m+n - c_k) is the product of the n consecutive numbers (m - k + 1), ... , (m - k + n), times the product of the n consecutive numbers (m + k + 2), ... , (m + k + n + 1). The first product is just the binomial coefficient (m-k+n)Cn times n!, so it is divisible by n!. The second product is 1/(m + k + 1) x (m + k + 1)(m + k + 2) ... (m + k + n + 1) = 1/(m + k + 1) x (m+k+n+1)C(n+1) x (n+1)!. But m + k + 1 is a prime greater than n + 1, so it has no factors in common with (n+1)!, hence the second product is divisible by (n+1)!. Finally note that c₁c₂ ... c_n= n! (n+1)!.

Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

9th IMO 1967