IMO 2016 Problem 5

Question

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?

Answer 1

Continuing from Aaron's Now Deleted Good Hint

Replace $2016$ by $4N$ for some $N\in\mathbb{N}$. As stated by McFry, $k\geq 4N$. I shall prove that $k=4N$ is possible. On the left-hand side of the given equation, factors of the form $(x-j)$ with $j\equiv 0,1\pmod{4}$ are removed, and on the right-hand side of the equation, factors of the form $(x-j)$ with $j\equiv 2,3\pmod{4}$ are removed. Then, we have to show that the polynomial functions $$f(x):=\prod_{r=1}^{N}\,\big(x-(4r-3)\big)\,\big(x-4r\big)$$ and $$g(x):=\prod_{r=1}^N\,\big(x-(4r-2)\big)\,\big(x-(4r-1)\big)$$ do not coincide on $\mathbb{R}$. It is easy to see that $f(x)<g(x)$ for all $x\in\mathbb{R}\setminus\bigcup_{r=1}^N\,\big(4r-2,4r-1)$. We are left to show that $f(x)<g(x)$ also holds for $x\in(4s-2,4s-1)$ for all $s=1,2,\ldots,N$.

For all $r=1,2,\ldots,N$ and for $x\in(4s-2,4s-1)$ for a fixed $s=1,2,\ldots,N$, we have $$\lambda_r(x):=\frac{\big(x-(4r-3)\big)\,\big(x-4r\big)}{\big(x-(4r-2)\big)\,\big(x-(4r-1)\big)}=1-\frac{2}{\big(x-(4r-2)\big)\,\big(x-(4r-1)\big)}\,.$$ Thus, by AM-GM, we have $$\lambda_s(x)\geq 1+\frac{2}{\big((4s-1)-x\big)\big(x-(4s-2)\big)}\geq 1+\frac{2}{1/4}=9\,.$$ Now, $$\prod_{r=1}^{s-1}\,\lambda_r(x)\geq 1-\sum_{r=1}^{s-1}\,\frac{2}{\big(x-(4r-2)\big)\,\big(x-(4r-1)\big)}>1-\sum_{r=1}^{s-1}\,\frac{2}{4(s-r)\big(4(s-r)+1\big)}\,.$$ Hence, $$\prod_{r=1}^{s-1}\,\lambda_r(x)> 1-\frac{1}{8}\,\sum_{r=1}^{s-1}\,\frac{1}{(s-r)^2}>\frac{7}{8}-\frac{1}{8}\,\sum_{i=1}^\infty\,\frac{1}{i(i+1)}=\frac{7}{8}-\frac{1}{8}=\frac{3}{4}\,.$$ Also, $$\prod_{r=s+1}^N\,\lambda_r(x)\geq 1-\sum_{r=s+1}^{N}\,\frac{2}{\big(x-(4r-2)\big)\,\big(x-(4r-1)\big)}>1-\sum_{r=s+1}^{N}\,\frac{2}{4(r-s)\big(4(r-s)-1\big)}\,.$$ Ergo, $$\prod_{r=s+1}^{N}\,\lambda_r(x)> 1-\frac{1}{6}-\frac{1}{8}\,\sum_{r=s+2}^{N}\,\frac{1}{(r-s)(r-s-1)}>\frac{5}{6}-\frac{1}{8}\,\sum_{i=1}^\infty\,\frac{1}{i(i+1)}=\frac{5}{6}-\frac{1}{8}=\frac{17}{24}\,.$$ Hence, $$\frac{f(x)}{g(x)}=\prod_{r=1}^N\,\lambda_r(x)>\frac{3}{4}\cdot 9\cdot \frac{17}{24}>4>1\,.$$ As $f(x)$ and $g(x)$ are both negative, it follows that $f(x)<g(x)$ for all $x\in(4s-2,4s-1)$ with $s=1,2,\ldots,N$. The proof is now complete.

Answer 2

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.