[Math] IMO 2016 Problem 5

combinatoricscontest-mathpolynomialsrecreational-mathematicsroots

The equation
$$
(x-1)(x-2)(x-3)\dots(x-2016)=(x-1)(x-2)(x-3)\dots(x-2016)
$$
is written on a 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$ factors so that at least one factor remains on each side and the resulting equation has no real solutions?

Best Answer

An interpretation of the solution from here. Sorry my Chinese.

  1. $k\ge 2016$ (see @McFry comment above).
  2. For $t=1,2,\ldots,504$, remove the following (exactly $2016$ many) factors $$ \begin{align*} & (x-(4t-2)),\quad (x-(4t-1)) &\qquad \text{ from the LHS},\\ & (x-(4t-3)),\quad (x-4t) &\qquad \text{ from the RHS}. \end{align*} $$ We are to prove that what's left has no real solutions. It would mean that the smallest $k$ is $2016$. We are left with the equation $$ \begin{align*} & (x-1)(x-4)(x-5)(x-8)\ldots(x-2013)(x-2016)=\\ = & (x-2)(x-3)(x-6)(x-7)\ldots (x-2014)(x-2015). \end{align*}\tag{1} $$
  3. Let's prove that for all $x\in\mathbb{R}$ it holds $$ \begin{align*} (x-1)(x-4)&<(x-2)(x-3),\\ (x-5)(x-8)&<(x-6)(x-7)\qquad \text{etc.}\tag{2} \end{align*} $$ In other words, we prove that for $t=1,\ldots,504$ $$ (x-(4t-3))(x-4t)<(x-(4t-2))(x-(4t-1)).\tag{3} $$ Denote $y=x-4t$. Then "RHS minus LHS" in (3) is $$ (y+2)(y+1)-(y+3)y=y^2+3y+2-y^2-3y=2>0. $$ Hence (2) is proven for all $x\in\mathbb{R}$.
  4. Obviously, $x\in \{1,2,\ldots,2016\}$ is not a solution
  5. If $x<1$, $x>2016$ or $\exists m\colon 1\le m\le 503$ such that $4m<x<4m+1$ then all sides of the inequalities in (2) are positive, therefore, (1) has no real roots.
  6. If $\exists n\colon 1\le n\le 504$ such that $4n-3<x<4n-2$ or $4n-1<x<4n$ then one inequality among first $n$ has negative LHS and positive RHS and the rest 503 inequalities have both sides positive. Then equality in (1) is again impossible.
  7. What's left is to prove that $4n-2<x<4n-1$ for some $n$, $1\le n\le 504$, cannot be a solution to (1). In this case the following $503$ inequalities holds true (similar prove as above) with both sides being positive $$ \begin{align*} (x-4)(x-5)&>(x-3)(x-6),\\ (x-8)(x-9)&>(x-7)(x-10),\\ &\vdots\\ (x-2012)(x-2013)&>(x-2011)(x-2014). \end{align*} $$ Moreover, for $1\le n\le 504$ we have $2\le 4n-2<x<4n-1\le 2015$, hence $$ \begin{align*} (x-1)&>(x-2)&>0,\\ -(x-2016)&>-(x-2015)&>0, \end{align*} $$ which implies $$ \begin{align*} & -(x-1)(x-4)(x-5)(x-8)\ldots(x-2013)(x-2016)>\\ > & -(x-2)(x-3)(x-6)(x-7)\ldots (x-2014)(x-2015), \end{align*} $$ so again (1) is impossible.
Related Question