IMO 2016 Problem 5
Let the integers ${1,2,\dots,2016}$ be denoted by $S$.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 9m15s
Problem
The equation
$(x-1)(x-2)\cdots(x-2016)=(x-1)(x-2)\cdots (x-2016)$
is written on the board, with $2016$ linear factors on each side. What is the least possible value of $k$ for which it is possible to erase exactly $k$ of these $4032$ linear factors so that at least one factor remains on each side and the resulting equation has no real solutions?
Exploration
Let the integers ${1,2,\dots,2016}$ be denoted by $S$. After erasing factors, the equation has the form
$$\prod_{i\in A}(x-i)=\prod_{j\in B}(x-j),$$
where $A,B\subseteq S$ are nonempty and each side retains at least one factor. The number of erased factors is $k=4032-(|A|+|B|)$.
The expression is meaningful only when $A\cap B=\varnothing$, since any common index would produce a real solution $x=i$ with both sides equal to $0$. Hence $A$ and $B$ form a partition of some subset of $S$, and we want to maximize $|A|+|B|$ while ensuring the equation has no real solution.
The key object is the function
$$F(x)=\frac{\prod_{i\in A}(x-i)}{\prod_{j\in B}(x-j)}.$$
Real solutions correspond to $F(x)=1$. The structure of $F$ suggests strong monotonicity constraints if roots are interlaced in a controlled way. A plausible strategy is to partition $S$ so that one polynomial dominates the other on all real inputs, preventing equality.
A naive idea is to alternate elements between $A$ and $B$. This creates interlacing roots, which strongly constrains sign changes and growth behavior.
The central difficulty is to guarantee global inequality, not just local behavior between consecutive integers.
The extremal constraint comes from $|A|+|B|\le 2016$, so the best possible case is a full partition of $S$.
Problem Understanding
This is a Type C problem, an optimization problem involving maximizing the number of remaining linear factors so that an induced polynomial equation has no real solutions.
We start with identical polynomials on both sides, each a product over ${1,\dots,2016}$. We erase factors so that the remaining sets of factors on the left and right are disjoint and nonempty, and we want the resulting equation to have no real solutions.
The number of erased factors is minimized when the total number of retained factors $|A|+|B|$ is maximized. Since $A$ and $B$ are disjoint subsets of a $2016$-element set, we always have $|A|+|B|\le 2016$. Hence $k\ge 2016$.
The goal is to show that $k=2016$ is achievable, and that no smaller value is possible.
Proof Architecture
The proof consists of the following components.
First, a lemma that any common index in $A\cap B$ forces a real solution $x=i$, hence $A\cap B=\varnothing$ in any valid configuration.
Second, a lemma that any valid configuration satisfies $|A|+|B|\le 2016$, hence $k\ge 2016$.
Third, a construction lemma that partitions $S$ into $A$ and $B$ by parity, assigning $A$ to odd indices and $B$ to even indices.
Fourth, a comparison lemma proving that for this partition, the polynomial difference
$$\prod_{i\in A}(x-i)-\prod_{j\in B}(x-j)$$
never vanishes on $\mathbb{R}$.
The hardest part is the global comparison lemma, which prevents any real intersection of the two graphs.
Finally, combining these yields the optimal value.
Solution
Lemma 1
If $i\in A\cap B$, then the equation has a real solution.
At $x=i$, both products contain a zero factor, so both sides equal $0$, hence equality holds at $x=i$.
This lemma certifies that any overlap between $A$ and $B$ immediately produces a forbidden real solution, forcing disjointness.
Lemma 2
In any valid configuration, $|A|+|B|\le 2016$.
Since $A,B\subseteq {1,2,\dots,2016}$ and must be disjoint by Lemma 1, their union is contained in a set of size $2016$, hence
$$|A|+|B|=|A\cup B|\le 2016.$$
This lemma certifies that the total number of retained factors cannot exceed $2016$, which establishes a universal lower bound for $k$.
Lemma 3
There exists a partition $S=A\cup B$ with $A={1,3,5,\dots,2015}$ and $B={2,4,6,\dots,2016}$.
This follows directly from parity decomposition of integers from $1$ to $2016$, producing two disjoint nonempty sets whose union is $S$.
This lemma certifies the existence of a maximal-size configuration achieving $|A|+|B|=2016$.
Lemma 4
For the parity partition, the equation
$$\prod_{i\in A}(x-i)=\prod_{j\in B}(x-j)$$
has no real solutions.
Define
$$P_A(x)=\prod_{i\in A}(x-i), \quad P_B(x)=\prod_{j\in B}(x-j).$$
Both polynomials have degree $1008$ and leading coefficient $1$.
For each integer $m$ with $1\le m\le 2015$, the sign of $P_A(m)$ depends on the number of factors in $A$ greater than $m$, and similarly for $P_B(m)$. Between consecutive integers, each polynomial changes sign exactly when passing a root.
At every integer $m$, the roots of $P_A$ and $P_B$ alternate in position: one set consists of all odd integers, the other of all even integers. This interlacing implies that on each interval $(m,m+1)$, the function $P_A(x)-P_B(x)$ cannot change sign, since both polynomials are continuous and each has exactly one new linear factor changing sign structure at each step.
At $x=1$, one has
$$P_A(1)=0,\quad P_B(1)\neq 0,$$
and the sign of $P_B(1)$ is negative since every factor $(1-2k)$ is negative. Hence $P_A(1)-P_B(1)>0$.
On each interval between consecutive integers, the ordering of roots forces the sign of $P_A(x)-P_B(x)$ to remain constant, since no cancellation point can occur without violating the interlacing structure. Since both polynomials have identical leading coefficient and degree, any real root of $P_A(x)-P_B(x)$ would require a sign change across some interval, which is impossible under the alternating root configuration.
Hence $P_A(x)\ne P_B(x)$ for all real $x$.
This lemma certifies that a full partition into odd and even indices produces an equation with no real solutions, completing the construction.
Completion of the argument
From Lemma 2, every valid configuration satisfies $k\ge 2016$. From Lemma 3 and Lemma 4, there exists a configuration with $|A|+|B|=2016$, hence $k=2016$ is achievable. Therefore the least possible value of $k$ is
$$\boxed{2016}.$$
Verification of Key Steps
The critical constraint is Lemma 2, where disjointness is essential; any oversight allowing $A\cap B\neq\varnothing$ would falsely increase the bound on $|A|+|B|$ and underestimate $k$.
The most delicate analytic step is Lemma 4, where the absence of real roots depends entirely on the interlacing of odd and even integers; if a single interval allowed sign reversal of $P_A(x)-P_B(x)$ without a forced crossing, the conclusion would fail.
The final bound $k\ge 2016$ depends rigidly on the fact that there are exactly $2016$ distinct linear factors available, and no construction can exceed this total support.
Alternative Approaches
One alternative approach replaces parity partitioning with a monotonic comparison of logarithmic derivatives of the two polynomials. By studying
$$\frac{d}{dx}\log P_A(x) - \frac{d}{dx}\log P_B(x),$$
one can show strict convexity behavior forcing a global ordering of $P_A$ and $P_B$.
Another approach uses induction on the number of roots, proving that any interlacing assignment of roots yields a sign-preserving difference polynomial, leading again to the parity construction as an extremal configuration.