Problem 3

Let

n\ge2

be a positive integer. Initially there are

n

fleas on a horizontal line, not all at the same point. For a positive real number

\lambda

, a move chooses fleas at

A

and

B

with

A

to the left of

B

, and lets the flea at

A

jump to

C

to the right of

B

so that

BC=\lambda AB

. Determine all

\lambda

such that, for every point

M

and every initial position, a finite sequence of moves puts all fleas to the right of

M

Step 1 of 4: Prove necessity below the threshold

Previous step Next step

In plain words

Use a bounded monovariant.

0<\lambda<\frac1{n-1}

Detailed analysis

Assume $0<\lambda<1/(n-1)$ and order the flea positions as $x_1\le\cdots\le x_n$ . Let $X$ be the sum of distances from all fleas to the rightmost flea. A move that does not move the rightmost flea decreases $X$ ; if the rightmost flea advances by $z$ , then $X$ decreases by at least $(1/\lambda-(n-1))z>0$ . Hence its total advance is bounded.