2017 IMO Problems/Problem 5

Problem

An integer $N \ge 2$ is given. A collection of $N(N + 1)$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $N(N - 1)$ players from this row leaving a new row of $2N$ players in which the following $N$ conditions hold:

( $1$ ) no one stands between the two tallest players,

( $2$ ) no one stands between the third and fourth tallest players,

$\;\;\vdots$

( $N$ ) no one stands between the two shortest players.

Show that this is always possible.

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

The answer is $\boxed{2016}$ . Clearly, if we erase less than $2016$ terms, then some term will appear on both sides by the pigeonhole principle, thereby causing a real root. Now, we show how we can erase $2016$ terms and have no real roots.

Let $f(x)=(x-1)(x-4)$ and $g(x)=(x-2)(x-3)$ . It is not hard to see that we can erase $2016$ terms to get the equation $f(x)f(x-4)\cdots f(x-2012) = g(x)g(x-4)\cdots g(x-2012).$ We now show this has no real solutions. Clearly, none of $1,2,\ldots,2016$ are solutions, since plugging them in causes one side to be $0$ and one side to not be $0$ . Therefore, letting $h(x)=g(x)/f(x)$ , our solution must satisfy $S:=h(x)h(x-4)\cdots h(x-2012)=1.$ It is not hard to see that $h(x)>1$ for $x<1$ and $x>4$ , and the maximum value of $h$ in $(1,4)$ is $1/9$ . Now, if our root $x$ is an interval of the form $(4k,4k+1)$ , then all the $h(x-4j)$ values are bigger than $1$ , which can't be. Thus, we have that $x\in(4k+1,4k+4)$ for some $k$ . Also, its not too hard to show that $h(x-4j)\le h(4|k-j|+1)$ (we do casework on whether $k>j$ or $k<j$ ). But $\alpha(|k-j|):=h(4|k-j|+1) = 1 + \frac{1}{2|k-j|(4|k-j|-3)}.$ We see that $\alpha$ is a decreasing function, so the product of all the $h(x-4j)$ terms besides $h(x-4k)$ is at most $\alpha(1)^2\alpha(2)^2\cdots\alpha(1007)^2\alpha(1008),$ so the entire product $S$ is at most $\frac{1}{9}\alpha(1)^2\alpha(2)^2\cdots\alpha(1007)^2\alpha(1008).$ It suffices to show that this is less than $1$ . Note that $\log(1+y)<y$ for all positive $y$ , so we have that $\log(\alpha(x)) < \frac{1}{2x(4x-3)}=:\beta(x).$ Note that \begin{align*} \log S &\le -\log 9 + 2\sum_{x=1}^{1008}\log(\alpha(x)) \\ &< -\log 9 + \sum_{x=1}^{2018}\frac{1}{x(4x-3)} \\ &< -\log 9 + 1+\sum_{x=2}^{\infty}\frac{1}{x(4x-4)} \\ &= -\log 9 + 1 + \frac{1}{4} \\ &= -\log 9 + 5/4, \end{align*} so $S<\frac{1}{9}e^{5/4}<1$ . Therefore, $S\not=1$ , so there are no roots, as desired

2017 IMO (Problems) • Resources
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All IMO Problems and Solutions

Page

Toolbox

Search

2017 IMO Problems/Problem 5

Problem

Solution

See Also