Difference between revisions of "2000 IMO Problems/Problem 3"

Revision as of 22:44, 9 April 2021

Let $n \geq 2$ be a positive integer and $\lambda$ a positive real number. Initially there are $n$ fleas on a horizontal line, not all at the same point. We define a move as choosing two fleas at some points $A$ and $B$ , with $A$ to the left of $B$ , and letting the flea from $A$ jump over the flea from $B$ to the point $C$ so that $\frac {BC}{AB} = \lambda$ .

Determine all values of $\lambda$ such that, for any point $M$ on the line and for any initial position of the $n$ fleas, there exists a sequence of moves that will take them all to the position right of $M$ .

Solution

Write $n = N+1$ ; we claim the answer is\[ \boxed{\left\{\lambda\colon \lambda \geq \frac 1N\right\}}. \]Place the points on the number line; let $p$ denote the coordinate of point $P$ . For a configuration $x_1\leq x_2\leq \cdots \leq x_{N+1}$ of points $X_1,X_2,\ldots, X_{N+1}$ , define its cap by $x_{N+1}$ and its score by $X_1X_{N+1} + X_2X_{N+1} + \cdots + X_NX_{N+1}$ . Notice now that we can get all the points past $M$ if and only if we can get the cap to exceed $m$ ; only if clearly holds, and for if just notice that if $X_{N+1}$ is past $M$ , we just reflect everything over $X_{N+1}$ and win. So, we just want to find $\lambda$ so that the cap can get arbitrarily large.

Lemma 1: $\lambda \geq \frac 1N$ all work.

Proof: First, note that we can get a configuration in which no two fleas are at the same point. To do this, first take the leftmost point and reflect over the rightmost point. Then, we have a point strictly to the right of all other points. Suppose the points are $P_1,P_2,\ldots, P_{N+1}$ , respectively. Then, at each point, reflect the leftmost point over the rightmost one $N$ times, until we have $N+1$ points all at distinct places.

Suppose our current configuration is $X_1,X_2,\ldots, X_{N+1}$ , and let $d_1 = X_1X_2$ , $d_2 = X_2X_3, \ldots$ , and write $d = \min(d_i)>0$ . Reflect $X_1$ over $X_{N+1}$ . Then, the configuration becomes $X_2,X_3,\ldots, X_{N+1}, X_1'$ , and the pairwise distances become $d_2,d_3,\ldots, d_N, \lambda(d_1+d_2+\cdots+d_N)$ , which are again all $\geq d$ . So, at each step, we know that the cap has coordinate increasing by at least $d$ every time, so we can get the cap to be arbitrarily large. $\Box$

Lemma 2: $\lambda < \frac 1N$ all fail.

Proof: Define the value $V$ of a configuration to be\[ V = C + \frac{\lambda S}{1-N\lambda}, \]where $C$ is the cap and $S$ is the score, respectively. We claim that the value is nonincreasing. Indeed, suppose we have a configuration $X_1,X_2,\ldots, X_{N+1}$ , where $x_1\leq x_2\leq \cdots \leq x_{N+1}$ . Suppose we reflect $X_i$ over $X_j$ with $i<j$ . Write $\alpha = X_iX_j$ , and $\beta =X_jX_{N+1}$ . If the cap does not change, then clearly the score decreases, since $X_i$ moves closer to $X_{N+1}$ and the other distances do not change. Otherwise, we see that the cap increases by $\lambda \alpha - \beta$ .

Furthermore, since we went from $X_1,X_2,\ldots, X_{N+1}$ to $X_1,X_2,\ldots, X_{i-1},X_{i+1},\ldots, X_{N+1},Q$ , where $Q$ is where $X_i$ jumped to, then the score changes from\[ \sum_{k=1}^N x_{N+1}-x_k = Nx_{N+1} - \sum_{k=1}^N x_k \]to\[ \sum_{\substack{k=1\\ k\neq i}}^{N+1}q - x_k = Nq - \sum_{\substack{k=1\\k\neq i}}^{N+1} x_k, \]so we compute that $\Delta S = N(q-x_{N+1}) - x_{N+1}+x_i = N(\lambda\alpha-\beta) - (\alpha+\beta)$ . So,\[ \Delta V = \Delta C + \frac{\lambda \Delta S}{1-N\lambda} = (\lambda\alpha-\beta) + \frac{\lambda (N(\lambda\alpha-\beta)-\alpha-\beta)}{1-N\lambda} \leq \lambda\alpha + \frac{\lambda(N\lambda-1)\alpha}{1-N\lambda} = 0. \]So, $V$ is indeed nonincreasing. So, if $V_0$ is the initial value, since $S\geq 0$ always we have that\[ C\leq V \leq V_0 \]implying that $m = V_0$ indeed works, and that we cannot move all the fleas to the right of $M$ . $\Box$

Thus, with both lemmas proven, we may conclude.

@@ Line 4: / Line 4: @@
 ==Solution==
-The answer is <math>\lambda \ge \frac{1}{n-1}</math>.
+Write <math>n = N+1</math>; we claim the answer is\[
+\boxed{\left\{\lambda\colon \lambda \geq \frac 1N\right\}}.
+\]Place the points on the number line; let <math>p</math> denote the coordinate of point <math>P</math>. For a configuration <math>x_1\leq x_2\leq \cdots \leq x_{N+1}</math> of points <math>X_1,X_2,\ldots, X_{N+1}</math>, define its cap by <math>x_{N+1}</math> and its score by <math>X_1X_{N+1} + X_2X_{N+1} + \cdots + X_NX_{N+1}</math>. Notice now that we can get all the points past <math>M</math> if and only if we can get the cap to exceed <math>m</math>; only if clearly holds, and for if just notice that if <math>X_{N+1}</math> is past <math>M</math>, we just reflect everything over <math>X_{N+1}</math> and win. So, we just want to find <math>\lambda</math> so that the cap can get arbitrarily large.
-We change the problem be replacing the fleas by bowling balls <math>B_1</math>, <math>B_2</math>, \dots, <math>B_n</math> in that order. Bowling balls aren't exactly great at jumping, so the operation now works as follows.
+Lemma 1: <math>\lambda \geq \frac 1N</math> all work.
-Choose any indices <math>i < j</math>.
-Then ball <math>B_i</math> moves to <math>B_{i+1}</math>'s location, <math>B_{i+1}</math> moves to <math>B_{i+2}</math>'s location, and so on; until <math>B_{j-1}</math> moves to <math>B_j</math>'s location,
-Finally, <math>B_j</math> moves some distance at most <math>\lambda \cdot |B_j B_i|</math> forward, but it may not pass <math>B_{j+1}</math>.
-Claim: If <math>\lambda < \frac{1}{n-1}</math> the bowling balls have bounded movement.
+Proof: First, note that we can get a configuration in which no two fleas are at the same point. To do this, first take the leftmost point and reflect over the rightmost point. Then, we have a point strictly to the right of all other points. Suppose the points are <math>P_1,P_2,\ldots, P_{N+1}</math>, respectively. Then, at each point, reflect the leftmost point over the rightmost one <math>N</math> times, until we have <math>N+1</math> points all at distinct places.
-Proof. Let <math>a_i \ge 0</math> denote the initial distance between <math>B_i</math> and <math>B_{i+1}</math>, and let <math>\Delta_i</math> denote the distance travelled by ball <math>i</math>. Of course we have <math>\Delta_1 \le a_1 + \Delta_2</math>, <math>\Delta_2 \le a_2 + \Delta_3</math>, \dots, <math>\Delta_{n-1} \le a_{n-1} + \Delta_n</math> by the relative ordering of the bowling balls. Finally, distance covered by <math>B_n</math> is always <math>\lambda</math> times distance travelled by other bowling balls, so\begin{align*} 		\Delta_n &\le \lambda \sum_{i=1}^{n-1} \Delta_i 		\le \lambda \sum_{i=1}^{n-1} 		\left( \left( a_i + a_{i+1} + \dots + a_{n-1} \right) 			+ \Delta_n \right) \\ 		&= (n-1)\lambda \cdot \Delta_n + \sum_{i=1}^{n-1} i a_i 	\end{align*}and since <math>(n-1)\lambda > 1</math>, this gives an upper bound. <math>\blacksquare</math>
+Suppose our current configuration is <math>X_1,X_2,\ldots, X_{N+1}</math>, and let <math>d_1 = X_1X_2</math>, <math>d_2 = X_2X_3, \ldots</math>, and write <math>d = \min(d_i)>0</math>. Reflect <math>X_1</math> over <math>X_{N+1}</math>. Then, the configuration becomes <math>X_2,X_3,\ldots, X_{N+1}, X_1'</math>, and the pairwise distances become <math>d_2,d_3,\ldots, d_N, \lambda(d_1+d_2+\cdots+d_N)</math>, which are again all <math>\geq d</math>. So, at each step, we know that the cap has coordinate increasing by at least <math>d</math> every time, so we can get the cap to be arbitrarily large. <math>\Box</math>
-Claim: When <math>\lambda \ge \frac{1}{n-1}</math>, it suffices to always jump the leftmost flea over the rightmost flea.
+Lemma 2: <math>\lambda < \frac 1N</math> all fail.
-Proof. If we let <math>x_i</math> denote the distance travelled by <math>B_1</math> in the <math>i</math>th step, then <math>x_i = a_i</math> for <math>1 \le i \le n-1</math> and <math>x_i = \lambda(x_{i-1} + x_{i-2} + \dots + x_{i-(n-1)})</math>.
+Proof: Define the value <math>V</math> of a configuration to be\[
+V = C + \frac{\lambda S}{1-N\lambda},
+\]where <math>C</math> is the cap and <math>S</math> is the score, respectively. We claim that the value is nonincreasing. Indeed, suppose we have a configuration <math>X_1,X_2,\ldots, X_{N+1}</math>, where <math>x_1\leq x_2\leq \cdots \leq x_{N+1}</math>. Suppose we reflect <math>X_i</math> over <math>X_j</math> with <math>i<j</math>. Write <math>\alpha = X_iX_j</math>, and <math>\beta =X_jX_{N+1}</math>. If the cap does not change, then clearly the score decreases, since <math>X_i</math> moves closer to <math>X_{N+1}</math> and the other distances do not change. Otherwise, we see that the cap increases by <math>\lambda \alpha - \beta</math>.
-In particular, if <math>\lambda \ge \frac{1}{n-1}</math> then each <math>x_i</math> is at least the average of the previous <math>n-1</math> terms. So if the <math>a_i</math> are not all zero, then <math>\{x_{n}, \dots, x_{2n-2}\}</math> are all positive and thereafter <math>x_i \ge \min \left\{ x_n, \dots, x_{2n-2} \right\} > 0</math> for every <math>i \ge 2n-1</math>. So the partial sums of <math>x_i</math> are unbounded, as desired. <math>\blacksquare</math>
+Furthermore, since we went from <math>X_1,X_2,\ldots, X_{N+1}</math> to <math>X_1,X_2,\ldots, X_{i-1},X_{i+1},\ldots, X_{N+1},Q</math>, where <math>Q</math> is where <math>X_i</math> jumped to, then the score changes from\[
+\sum_{k=1}^N x_{N+1}-x_k = Nx_{N+1} - \sum_{k=1}^N x_k
+\]to\[
+\sum_{\substack{k=1\\ k\neq i}}^{N+1}q - x_k = Nq - \sum_{\substack{k=1\\k\neq i}}^{N+1} x_k,
+\]so we compute that <math>\Delta S = N(q-x_{N+1}) - x_{N+1}+x_i = N(\lambda\alpha-\beta) - (\alpha+\beta)</math>. So,\[
+\Delta V = \Delta C + \frac{\lambda \Delta S}{1-N\lambda} = (\lambda\alpha-\beta) + \frac{\lambda (N(\lambda\alpha-\beta)-\alpha-\beta)}{1-N\lambda} \leq \lambda\alpha + \frac{\lambda(N\lambda-1)\alpha}{1-N\lambda} = 0.
+\]So, <math>V</math> is indeed nonincreasing. So, if <math>V_0</math> is the initial value, since <math>S\geq 0</math> always we have that\[
+C\leq V \leq V_0
+\]implying that <math>m = V_0</math> indeed works, and that we cannot move all the fleas to the right of <math>M</math>. <math>\Box</math>
+Thus, with both lemmas proven, we may conclude.

Page

Toolbox

Search

Difference between revisions of "2000 IMO Problems/Problem 3"

Revision as of 22:44, 9 April 2021

Solution