Difference between revisions of "2017 IMO Problems/Problem 5"

(Created page with "An integer <math>N \ge 2</math> is given. A collection of <math>N(N + 1)</math> soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove...")
 
(Solution)
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
An integer <math>N \ge 2</math> is given. A collection of <math>N(N + 1)</math> soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove <math>N(N - 1)</math> players from this row leaving a new row of <math>2N</math> players in which the following <math>N</math> conditions hold:
 
An integer <math>N \ge 2</math> is given. A collection of <math>N(N + 1)</math> soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove <math>N(N - 1)</math> players from this row leaving a new row of <math>2N</math> players in which the following <math>N</math> conditions hold:
 +
 
(<math>1</math>) no one stands between the two tallest players,
 
(<math>1</math>) no one stands between the two tallest players,
 +
 
(<math>2</math>) no one stands between the third and fourth tallest players,
 
(<math>2</math>) no one stands between the third and fourth tallest players,
 +
 
<math>\;\;\vdots</math>
 
<math>\;\;\vdots</math>
 +
 
(<math>N</math>) no one stands between the two shortest players.
 
(<math>N</math>) no one stands between the two shortest players.
  
 
Show that this is always possible.
 
Show that this is always possible.
 +
 +
==Solution==
 +
{{solution}}
 +
 +
The answer is <math>\boxed{2016}</math>. Clearly, if we erase less than <math>2016</math> 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 <math>2016</math> terms and have no real roots.
 +
 +
Let <math>f(x)=(x-1)(x-4)</math> and <math>g(x)=(x-2)(x-3)</math>. It is not hard to see that we can erase <math>2016</math> terms to get the equation
 +
<cmath>f(x)f(x-4)\cdots f(x-2012) = g(x)g(x-4)\cdots g(x-2012).</cmath>
 +
We now show this has no real solutions. Clearly, none of <math>1,2,\ldots,2016</math> are solutions, since plugging them in causes one side to be <math>0</math> and one side to not be <math>0</math>. Therefore, letting <math>h(x)=g(x)/f(x)</math>, our solution must satisfy
 +
<cmath>S:=h(x)h(x-4)\cdots h(x-2012)=1.</cmath>
 +
It is not hard to see that <math>h(x)>1</math> for <math>x<1</math> and <math>x>4</math>, and the maximum value of <math>h</math> in <math>(1,4)</math> is <math>1/9</math>. Now, if our root <math>x</math> is an interval of the form <math>(4k,4k+1)</math>, then all the <math>h(x-4j)</math> values are bigger than <math>1</math>, which can't be. Thus, we have that <math>x\in(4k+1,4k+4)</math> for some <math>k</math>. Also, its not too hard to show that <math>h(x-4j)\le h(4|k-j|+1)</math> (we do casework on whether <math>k>j</math> or <math>k<j</math>). But
 +
<cmath>\alpha(|k-j|):=h(4|k-j|+1) = 1 + \frac{1}{2|k-j|(4|k-j|-3)}.</cmath>
 +
We see that <math>\alpha</math> is a decreasing function, so the product of all the <math>h(x-4j)</math> terms besides <math>h(x-4k)</math> is at most
 +
<cmath>\alpha(1)^2\alpha(2)^2\cdots\alpha(1007)^2\alpha(1008),</cmath>
 +
so the entire product <math>S</math> is at most
 +
<cmath>\frac{1}{9}\alpha(1)^2\alpha(2)^2\cdots\alpha(1007)^2\alpha(1008).</cmath>
 +
It suffices to show that this is less than <math>1</math>. Note that <math>\log(1+y)<y</math> for all positive <math>y</math>, so we have that
 +
<cmath>\log(\alpha(x)) < \frac{1}{2x(4x-3)}=:\beta(x).</cmath>
 +
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 <math>S<\frac{1}{9}e^{5/4}<1</math>. Therefore, <math>S\not=1</math>, so there are no roots, as desired
 +
 +
==See Also==
 +
 +
{{IMO box|year=2017|num-b=4|num-a=6}}

Latest revision as of 13:34, 4 December 2024

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 logSlog9+2x=11008log(α(x))<log9+x=120181x(4x3)<log9+1+x=21x(4x4)=log9+1+14=log9+5/4, so $S<\frac{1}{9}e^{5/4}<1$. Therefore, $S\not=1$, so there are no roots, as desired

See Also

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