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 is given. A collection of soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove players from this row leaving a new row of players in which the following conditions hold:
() no one stands between the two tallest players,
() no one stands between the third and fourth tallest players,
() 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 . Clearly, if we erase less than 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 terms and have no real roots.
Let and . It is not hard to see that we can erase terms to get the equation
We now show this has no real solutions. Clearly, none of are solutions, since plugging them in causes one side to be and one side to not be . Therefore, letting , our solution must satisfy
It is not hard to see that for and , and the maximum value of in is . Now, if our root is an interval of the form , then all the values are bigger than , which can't be. Thus, we have that for some . Also, its not too hard to show that (we do casework on whether or ). But
We see that is a decreasing function, so the product of all the terms besides is at most
so the entire product is at most
It suffices to show that this is less than . Note that for all positive , so we have that
Note that
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 |