Difference between revisions of "2000 IMO Problems/Problem 3"
(Created page with "Let <math> n \geq 2</math> be a positive integer and <math> \lambda</math> a positive real number. Initially there are <math> n</math> fleas on a horizontal line, not all at t...") |
|||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
− | + | 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. | ||
− | + | Lemma 1: <math>\lambda \geq \frac 1N</math> 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 <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. | |
− | + | 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> | |
− | + | Lemma 2: <math>\lambda < \frac 1N</math> all fail. | |
− | Proof | + | 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>. | ||
− | + | 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. |
Revision as of 22:44, 9 April 2021
Let be a positive integer and a positive real number. Initially there are fleas on a horizontal line, not all at the same point. We define a move as choosing two fleas at some points and , with to the left of , and letting the flea from jump over the flea from to the point so that .
Determine all values of such that, for any point on the line and for any initial position of the fleas, there exists a sequence of moves that will take them all to the position right of .
Solution
Write ; we claim the answer is\[ \boxed{\left\{\lambda\colon \lambda \geq \frac 1N\right\}}. \]Place the points on the number line; let denote the coordinate of point . For a configuration of points , define its cap by and its score by . Notice now that we can get all the points past if and only if we can get the cap to exceed ; only if clearly holds, and for if just notice that if is past , we just reflect everything over and win. So, we just want to find so that the cap can get arbitrarily large.
Lemma 1: 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 , respectively. Then, at each point, reflect the leftmost point over the rightmost one times, until we have points all at distinct places.
Suppose our current configuration is , and let , , and write . Reflect over . Then, the configuration becomes , and the pairwise distances become , which are again all . So, at each step, we know that the cap has coordinate increasing by at least every time, so we can get the cap to be arbitrarily large.
Lemma 2: all fail.
Proof: Define the value of a configuration to be\[ V = C + \frac{\lambda S}{1-N\lambda}, \]where is the cap and is the score, respectively. We claim that the value is nonincreasing. Indeed, suppose we have a configuration , where . Suppose we reflect over with . Write , and . If the cap does not change, then clearly the score decreases, since moves closer to and the other distances do not change. Otherwise, we see that the cap increases by .
Furthermore, since we went from to , where is where 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 . 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, is indeed nonincreasing. So, if is the initial value, since always we have that\[ C\leq V \leq V_0 \]implying that indeed works, and that we cannot move all the fleas to the right of .
Thus, with both lemmas proven, we may conclude.