|
|
| (4 intermediate revisions by 2 users not shown) |
| Line 1: |
Line 1: |
| − | 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 the same point. We define a move as choosing two fleas at some points <math> A</math> and <math> B</math>, with <math> A</math> to the left of <math> B</math>, and letting the flea from <math> A</math> jump over the flea from <math> B</math> to the point <math> C</math> so that <math> \frac {BC}{AB} = \lambda</math>.
| + | ==Problem== |
| | | | |
| − | Determine all values of <math> \lambda</math> such that, for any point <math> M</math> on the line and for any initial position of the <math> n</math> fleas, there exists a sequence of moves that will take them all to the position right of <math> M</math>. | + | Let <math>n \ge 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 the same point. We define a move as choosing two fleas at some points <math>A</math> and <math>B</math> to the left of <math>B</math>, and letting the flea from <math>A</math> jump over the flea from <math>B</math> to the point <math>C</math> so that <math>\frac{BC}{AB}=\lambda</math>. |
| | + | |
| | + | Determine all values of <math>\lambda</math> such that, for any point <math>M</math> on the line and for any initial position of the <math>n</math> fleas, there exists a sequence of moves that will take them all to the position right of <math>M</math>. |
| | | | |
| | ==Solution== | | ==Solution== |
| − | Write <math>n = N+1</math>; we claim the answer is\[
| + | {{solution}} |
| − | \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: 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\[
| + | ==See Also== |
| − | \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.
| + | {{IMO box|year=2000|num-b=2|num-a=4}} |
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 
to the left of 
so that 
.
on the line and for any initial position of the 
