IMO 2016 Problem 5 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?
 A: 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.
