IMO 1967 · Problem 3

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 the product \[ (c_{m+1}-c_k)(c_{m+2}-c_k)\cdots(c_{m+n}-c_k) \] is divisible by the product \(c_1c_2\cdots c_n\).

Official text of the problem. Official problem paper (PDF)

Solution

We use the fact that the product of any \(r\) consecutive integers is divisible by \(r!\). For consecutive positive integers beginning with \(a\), this follows from \[ a(a+1)\cdots(a+r-1)=r!\binom{a+r-1}{r}. \] If the product contains zero, the assertion is immediate. If all its factors are negative, changing their signs and reversing their order reduces it to the positive case.

Set \(p=m+k+1\), which is prime and greater than \(n+1\). For \(1\le i\le n\), \[ c_{m+i}-c_k =(m+i)(m+i+1)-k(k+1) =(m-k+i)(p+i). \] Thus the required numerator is \(AB\), where \[ A=\prod_{i=1}^{n}(m-k+i), \qquad B=\prod_{i=1}^{n}(p+i). \]

The factors of \(A\) are \(n\) consecutive integers, so \[ n!\mid A. \] Also, \[ pB=p(p+1)\cdots(p+n) \] is a product of \(n+1\) consecutive integers. Hence \[ (n+1)!\mid pB. \] Since \(p\) is prime and \(p>n+1\), we have \[ \gcd\bigl(p,(n+1)!\bigr)=1. \] Consequently, \((n+1)!\mid B\). Multiplying the two divisibilities gives \[ n!(n+1)!\mid AB. \] Finally, \[ c_1c_2\cdots c_n =\prod_{i=1}^{n}i(i+1) =n!(n+1)!, \] which proves the claim.

If natural numbers are taken to include zero, the case \(n=0\) also holds: both products are empty and equal to \(1\).

The solution was checked against John Scholes' IMO solution archive (Kalva).