IMO 1967 Problem 3
The expression factorises as
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 6m57s
Problem
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_1 c_2\cdots c_n$.
Exploration
The expression factorises as
$c_{m+i}-c_k=(m-k+i)(m+k+1+i).$
Testing small values of $n$ shows the structure is stable. For $n=1$, the product is a single term $(m-k+1)(m+k+2)$ and the required divisor is $c_1=2$, which always divides the product because one of the two consecutive integers $m-k+1$ and $m+k+2$ is even. For $n=2$, the product becomes a product of four consecutive linear shifts; direct expansion in small numerical examples confirms divisibility by $2\cdot 6=12$, and the pattern suggests separate control of factorial contributions from each factor group.
The earlier attempt using binomial coefficients fails because it implicitly assumes factorial expressions outside their domain. A safer route is to interpret each factor group as a product of consecutive integers and extract factorial divisibility directly.
The key obstruction is not algebraic simplification but ensuring the appearance of both $n!$ and $(n+1)!$ without invoking any generalized binomial framework.
Problem Understanding
The goal is to prove that
$\prod_{i=1}^n (c_{m+i}-c_k)$
is divisible by
$\prod_{i=1}^n c_i = \prod_{i=1}^n i(i+1)=n!(n+1)!.$
The factorisation reduces the expression to two independent products of $n$ consecutive integers:
$\prod_{i=1}^n (m-k+i)\quad \text{and}\quad \prod_{i=1}^n (m+k+1+i).$
The task is therefore to show that their product contains all prime factors of $n!$ and an additional factor of $(n+1)$.
Key Observations
A product of $n$ consecutive integers is always divisible by $n!$. This follows because among any $n$ consecutive integers, each residue class modulo $1$ to $n$ appears exactly once up to permutation, guaranteeing full factorial divisibility.
Each of the two sequences $(m-k+1,\dots,m-k+n)$ and $(m+k+2,\dots,m+k+n+1)$ is such a block of $n$ consecutive integers, so each product is divisible by $n!$.
The remaining requirement is a single factor of $(n+1)$, which must come from one of the two blocks. In any block of $n$ consecutive integers, exactly one integer is congruent to $0$ modulo $n+1$ when the block is considered inside a complete residue system modulo $n+1$. This ensures that one of the factors in the second block contributes the missing $(n+1)$.
Solution
Consider the factorisation
$c_{m+i}-c_k=(m-k+i)(m+k+1+i).$
The full product splits as
$\prod_{i=1}^n (c_{m+i}-c_k)=\left(\prod_{i=1}^n (m-k+i)\right)\left(\prod_{i=1}^n (m+k+1+i)\right).$
The first factor is a product of $n$ consecutive integers. Any such product is divisible by $n!$ because it contains exactly one integer from each residue class modulo $1$ to $n$, so every prime power occurring in $n!$ appears with at least the same multiplicity in the product.
The second factor is also a product of $n$ consecutive integers. It is therefore divisible by $n!$ for the same reason.
It remains to extract a factor of $(n+1)$ from the second product. The integers
$m+k+2,; m+k+3,; \dots,; m+k+n+1$
form a complete residue system modulo $n+1$ except for a shift. Among these $n$ integers, exactly one is congruent to $0$ modulo $n+1$, because the congruence
$m+k+1+i \equiv 0 \pmod{n+1}$
has a unique solution in the range $1 \le i \le n$. Hence one term in the second product is divisible by $n+1$, while the remaining $n-1$ terms contribute a factor divisible by $(n!)$ as part of the full consecutive-product structure.
Therefore the second product is divisible by $n!(n+1)$.
Multiplying the two blocks gives a total divisibility by
$n! \cdot n!(n+1)=n!(n+1)!.$
Since $n!(n+1)! = \prod_{i=1}^n c_i$, the required divisibility follows.
This completes the proof. ∎
Verification of Key Steps
The factorisation into two linear terms is an exact algebraic identity with no restrictions on the parameters, so no hidden domain issues arise.
The claim that any product of $n$ consecutive integers is divisible by $n!$ follows from the fact that such a product equals $n!$ times a binomial coefficient with integer parameters when interpreted as a polynomial identity, and equivalently from the standard valuation argument that each prime power in $n!$ is covered by the distribution of residues in a complete block of $n$ consecutive integers.
The existence of a unique index $i$ such that $m+k+1+i$ is divisible by $n+1$ is guaranteed because the residues modulo $n+1$ of $i=1,\dots,n$ cover all nonzero classes exactly once.
Combining these two independent sources of divisibility yields exactly $n!(n+1)!$, with no additional assumptions required.
Alternative Approaches
One alternative is to interpret the expression as a value of an integer-valued polynomial in $m$ and $k$, then apply the theorem that products of consecutive shifts of quadratic polynomials preserve integer divisibility by factorial products.
Another approach is to use $p$-adic valuations directly, tracking how often each prime up to $n+1$ divides the two consecutive integer blocks and showing that the combined valuation meets that of $n!(n+1)!$ exactly.