Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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...")
 
(→‎See Also)
 
(5 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==
−
The answer is <math>\lambda \ge \frac{1}{n-1}</math>.
+
{{solution}}
−
 
 
−
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.
 
−
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. 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>
 
−
 
 
−
Claim: When <math>\lambda \ge \frac{1}{n-1}</math>, it suffices to always jump the leftmost flea over the rightmost flea.
 
  
−
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>.
+
==See Also==
  
−
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>
+
{{IMO box|year=2000|num-b=2|num-a=4}}

Latest revision as of 00:16, 19 November 2023

Problem

Let $n \ge 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$ 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

This problem needs a solution. If you have a solution for it, please help us out by adding it.

See Also

2000 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_IMO_Problems/Problem_3&oldid=204486"