IMO 2016 · Problem 5

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?

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

Answer

\[ \boxed{2016} \]

Solution

For each \(i\in\{1,\ldots,2016\}\), at least one of the two copies of \(x-i\) must be erased. Otherwise, \(x=i\) makes both sides zero and is a real solution. Consequently, \[ k\ge2016. \]

We construct an example attaining this bound. Retain the factors whose indices are congruent to \(0\) or \(1\pmod4\) on the left, and those whose indices are congruent to \(2\) or \(3\pmod4\) on the right. The resulting equation is \(P(x)=Q(x)\), where \[ P(x)=\prod_{j=0}^{503}(x-4j-1)(x-4j-4), \qquad Q(x)=\prod_{j=0}^{503}(x-4j-2)(x-4j-3). \] Exactly one copy of every original factor was erased, so there were \(2016\) erasures, and \(1008\) factors remain on each side.

We prove that \(P(x)<Q(x)\) for every real \(x\).

Write \[ A_j=(x-4j-1)(x-4j-4),\qquad B_j=(x-4j-2)(x-4j-3). \] Then \[ B_j=A_j+2. \] Moreover, \(A_j\le0\) precisely when \(x\in[4j+1,4j+4]\). These intervals are pairwise disjoint, so at most one \(A_j\) is nonpositive.

First suppose that every \(B_j\ge0\). If every \(A_j>0\), multiplying \(A_j<B_j\) gives \(P(x)<Q(x)\). Otherwise, there is exactly one nonpositive \(A_t\), and all other \(A_j\) and \(B_j\) are positive. If \(A_t<0\), then \[ P(x)<0\le Q(x). \] If \(A_t=0\), then \(B_t=2\), so \[ P(x)=0<Q(x). \] Thus \(P(x)<Q(x)\) in all these cases.

It remains to consider the case \(B_t<0\) for some \(t\), which means \[ 4t+2<x<4t+3. \] Regroup the same factors as follows: \[ P(x)=(x-1)(x-2016) \prod_{j=1}^{503}(x-4j)(x-4j-1), \] \[ Q(x)=(x-2)(x-2015) \prod_{j=1}^{503}(x-4j+1)(x-4j-2). \] For \(1\le j\le503\), put \[ C_j=(x-4j)(x-4j-1),\qquad D_j=(x-4j+1)(x-4j-2). \] We have \[ C_j=D_j+2. \] Also, \(D_j>0\): if \(j\le t\), both its roots are less than \(x\), since \(4j+2<x\); if \(j\ge t+1\), both its roots are greater than \(x\), since \(4j-1>x\). Hence \[ C_j>D_j>0 \qquad(1\le j\le503). \]

Finally, \(2<x<2015\), so the quantities \[ U=(x-1)(2016-x),\qquad V=(x-2)(2015-x) \] are positive, and \[ U-V=2014>0. \] Using the regrouped products, we obtain \[ -P(x)=U\prod_{j=1}^{503}C_j > V\prod_{j=1}^{503}D_j =-Q(x). \] Thus \(P(x)<Q(x)\) in this last case as well.

The constructed equation therefore has no real solutions. It attains the lower bound, proving that the least possible number of erasures is \(2016\).

The solution was checked against the official IMO shortlist solutions.