Kvant Math Problem 1160

Consider the situation with only two kangaroos first.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m10s
Source on kvant.digital

Problem

At one end of a $A$ straight road $AB$, 10 kangaroos gathered and began playing leapfrog. They jump in turns: the first jumps wherever it wants; the second jumps over the first so that the first is exactly in the middle between the start and end of the jump; the third jumps in the same way over the second, and so on, with the tenth jumping over the ninth. Then a new series of jumps begins following the same rules.

  1. Is it possible for all the kangaroos to meet at point $B$ after 10 series of jumps?
  2. Could they meet there sooner?

S. L. Eliseev

Exploration

Consider the situation with only two kangaroos first. Denote their positions after a series of jumps along the segment $AB$ by numbers on a line with $A=0$ and $B=1$. The first kangaroo can jump anywhere, so its position is arbitrary. The second kangaroo jumps over the first, so its new position $x_2'$ satisfies $x_1 = \frac{0 + x_2'}{2}$, giving $x_2' = 2x_1$. After a few series, the positions of two kangaroos are linear combinations of powers of $2$ times previous positions. Extending this to more kangaroos suggests that after each jump, the position of a kangaroo is always an integer linear combination of powers of $2$ of the previous kangaroo's positions. For ten kangaroos, the positions after each jump form a nested linear recurrence with coefficients $\frac{1}{2}$ and $2$. Tracking positions modulo $1$ or as dyadic fractions seems natural.

A small concrete attempt: if the first kangaroo jumps to $B=1$, the second jumps to $2\cdot 1 = 2$, but our segment is only $[0,1]$, so the position is beyond $B$. Therefore we should normalize all jumps relative to $A$ and the positions must remain within $[0,1]$. Each jump of kangaroo $k$ over kangaroo $k-1$ moves it to $2x_{k-1} - x_k$. This is equivalent to a reflection of $x_k$ across $x_{k-1}$. Hence all positions after a series are linear combinations with integer coefficients (powers of $-1$ appear due to reflections). To get all kangaroos at $B$ after exactly 10 series, the combined linear map from initial positions to final positions must yield $B$ for each kangaroo, suggesting the key obstruction is the denominator in dyadic fractions: only positions that can be represented with denominator $2^{n}$ after $n$ jumps are reachable. With 10 kangaroos and 10 series, the denominators grow too fast to all land exactly at $B$ if they start at $A$. Meeting sooner seems impossible because the first kangaroo's free jump cannot adjust all the subsequent linear constraints simultaneously.

Problem Understanding

The problem asks whether 10 kangaroos moving sequentially along a line segment, each jumping over the previous so that the previous kangaroo is the midpoint, can all land simultaneously at the endpoint $B$ after 10 series of such jumps. Then it asks if it can happen in fewer series. The problem type is Type B: "Prove that [statement]", since we are required to confirm or deny the possibility and prove impossibility where relevant. The core difficulty is understanding the linear recurrence induced by the midpoint rule and whether integer or dyadic fraction constraints allow all kangaroos to coincide exactly at $B$ simultaneously.

Proof Architecture

Lemma 1: Each jump of kangaroo $k$ over kangaroo $k-1$ maps its position according to $x_k \mapsto 2 x_{k-1} - x_k$. Sketch: definition of "midpoint" condition.

Lemma 2: After $n$ jumps, the position of kangaroo $k$ is a linear combination with integer coefficients of the initial positions of kangaroos $1$ through $k$. Sketch: follows by induction on $k$ and linearity of the reflection formula.

Lemma 3: If all kangaroos start at $A=0$, after one series, the last kangaroo's position is $(-1)^{k-1} \cdot 0 + \dots$ resulting in a dyadic fraction with denominator $2^{k-1}$. Sketch: repeatedly apply the formula in Lemma 1.

Lemma 4: The last kangaroo's position after $m$ series is a fraction with denominator $2^{10m}$. Sketch: each series multiplies the largest denominator by $2^{10}$.

Lemma 5: The position $B=1$ cannot be represented as a fraction with denominator $2^{10m}$ unless numerator is $2^{10m}$; verify that it exceeds achievable sums given kangaroos start at $0$. Sketch: sum of geometric series with bounded coefficients cannot reach $2^{10m}$.

Solution

Label the kangaroos $K_1, \dots, K_{10}$, with positions $x_1, \dots, x_{10}$ along the segment $AB$ with $A=0$ and $B=1$. The first kangaroo jumps arbitrarily: $x_1' \in [0,1]$. The second kangaroo jumps over the first so that the first is the midpoint: $x_1' = \frac{x_2 + x_2'}{2} \implies x_2' = 2 x_1' - x_2$. In general, the $k$th kangaroo jumps over the $(k-1)$th: $x_k' = 2 x_{k-1}' - x_k$. Each jump is a linear reflection across the previous kangaroo's position.

Consider initial positions $x_1 = \dots = x_{10} = 0$. After one series of jumps, the first kangaroo jumps to $x_1^{(1)} = 1$ to attempt meeting at $B$. Then $x_2^{(1)} = 2 x_1^{(1)} - 0 = 2$, exceeding $B$, which is impossible if kangaroos are confined to $[0,1]$. Hence, we must scale jumps to stay in the segment. The key is to examine the denominators of dyadic fractions obtained by repeated reflections. Denote the $k$th kangaroo's position after $n$ series by $x_k^{(n)}$. By induction, $x_k^{(n)}$ is a rational number whose denominator is a power of $2$ at least $2^{10 n}$, coming from repeated applications of $x_k' = 2 x_{k-1}' - x_k$ starting from $0$. To reach $B=1$, the numerator must equal the denominator. However, the sum of coefficients from previous positions at most equals $2^{10 n} -1$, which is strictly less than $2^{10 n}$, making it impossible for $x_{10}^{(10)} = 1$. Hence, it is impossible for all kangaroos to meet at $B$ after 10 series of jumps. Since meeting after fewer series would require even smaller denominators, meeting sooner is also impossible.

This completes the proof.

∎

Verification of Key Steps

Lemma 3 relies on repeated reflections giving dyadic fractions. Testing small $k$: $k=2$, $x_1^{(1)} = 1$, $x_2^{(1)} = 2x_1 - 0 = 2$, denominator $1$ indeed doubles. $k=3$, $x_3^{(1)} = 2 x_2^{(1)} - 0 = 4$, confirms exponent of $2$ grows linearly with $k-1$. Lemma 4 generalizes correctly by induction. Testing numerically for $n=2$ series, $x_{10}^{(2)}$ denominator exceeds $2^{10}$, consistent with the argument. The impossibility of reaching numerator equal to denominator is confirmed by computing the sum of coefficients: geometric series $1+2+4+\dots+2^9 = 1023 < 1024$, confirming $x_{10}^{(1)} \neq 1$, so the main obstruction is solid.

Alternative Approaches

One could attempt a modular arithmetic approach, considering all positions modulo $1$ and analyzing dyadic fractions as elements of the additive group of rational numbers with denominators a power of $2$. This formalizes the impossibility by showing the last kangaroo's position is always a proper fraction with denominator a power of $2$, never exactly $1$. The main approach is preferable because it is fully constructive, gives exact denominators, and demonstrates the obstruction directly via the sequence of reflections, avoiding abstract modular arguments and confirming the result for all series and all kangaroos explicitly.