Kvant Math Problem 190

The motion is completely determined by the two lines and the current point.

kvantmathematicsolympiad

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

Problem

On the plane, two lines $a$ and $b$ are given. At point $A_1$, located on line $a$ at a distance less than 1 from line $b$, a flea sits. Then the flea sequentially jumps to points $B_1$, $A_2$, $B_2$, $A_3$, $B_3$, $\ldots$, following these rules (Fig. 2):

  1. points $A_1$, $A_2$, $A_3$, $\ldots$ lie on line $a$, points $B_1$, $B_2$, $B_3$, $\ldots$ lie on line b;
  2. $A_1B_1 = B_1A_2 = A_2B_2 = B_2A_3 = A_3B_3 = \ldots = 1$;
  3. point $A_n$ does not coincide with $A_{n+1}$, except in the case when $A_nB_n \perp a$ (and similarly, $B_n$ coincides with $B_{n+1}$ only if $B_nA_{n+1} \perp b$). (It is easy to see that conditions (1)—(3) determine the sequence of jumps uniquely, starting from $B_1A_2$.)

Prove that if the angle between lines $a$ and $b$ is measured in a rational number of degrees, then the flea’s path will be periodic; that is, at some point it will return to the starting point $A_1$ and then sequentially pass through the same points $B_2$, $A_2$, $B_3$, $\ldots$ as at the beginning of the path. If the angle is an irrational number of degrees, the flea will not land on any point more than twice.

Figure number 2

Exploration

The motion is completely determined by the two lines and the current point. A natural way to describe it is not by the points themselves, but by the oriented segment joining the current point on one line to the next point on the other line.

Let $\alpha$ be the angle from $a$ to $b$. Suppose a jump from $a$ to $b$ is represented by a unit vector making angle $\theta$ with line $a$. Since the endpoint lies on $b$, the next jump must start from that endpoint and have the same length $1$. The condition excluding immediate backtracking says that, except in the perpendicular case, the next jump is obtained by reflecting the previous unit vector in line $b$. Then the following jump is obtained by reflecting in line $a$, and so on.

Thus the sequence of jump directions is generated by alternating reflections in the two lines. The composition of reflections in $a$ and $b$ is a rotation by $2\alpha$. Hence, after every two jumps, the direction rotates by $2\alpha$.

This suggests introducing the direction angle $\theta_n$ of the jump $A_nB_n$. Then

$$\theta_{n+1}=\theta_n+2\alpha \pmod{2\pi}.$$

The geometry of the visited points should then be recoverable from these directions.

The most delicate point is showing that the actual positions are controlled by these directions in a simple way. Let $u_n$ be the signed coordinate of $A_n$ on line $a$. The projection of the jump $A_nB_n$ onto $a$ equals $\cos\theta_n$. The projection of the next jump $B_nA_{n+1}$ onto $a$ is the same, because it is the reflection of the first jump in $b$. Hence

$$u_{n+1}-u_n=2\cos\theta_n.$$

Using $\theta_n=\theta_1+2(n-1)\alpha$, the motion on $a$ becomes a trigonometric walk.

If $\alpha/\pi$ is rational, the directions take only finitely many values, hence are periodic. The sum of one period of the increments is

$$2\sum \cos(\theta_1+2k\alpha),$$

and for a complete cycle of roots of unity this sum is $0$. Therefore the point on $a$ returns to its initial position after one full period, giving a closed orbit.

If $\alpha/\pi$ is irrational, all directions are distinct modulo $2\pi$. Then the increments never repeat in a periodic way. Suppose some point of $a$ were visited three times. The differences between two pairs of visits would give a nontrivial vanishing trigonometric sum

$$\sum_{k=r}^{s-1} e^{i(\theta_1+2k\alpha)} = \sum_{k=t}^{u-1} e^{i(\theta_1+2k\alpha)}.$$

After cancellation, one obtains a finite relation

$$\sum_{j=m}^{n} e^{2ij\alpha}=0.$$

But this is a geometric progression, whose sum vanishes only when $e^{2i\alpha}$ is a root of unity, contrary to irrationality of $\alpha/\pi$. Hence no point on $a$ can be visited more than twice. The same argument applies to points on $b$.

The appearance of “twice” is explained by the fact that a point may be reached once by a jump coming from one side and once by a jump coming from the other side.

Problem Understanding

We are given two lines $a$ and $b$ and a point $A_1\in a$ whose distance from $b$ is less than $1$. A flea alternately lands on $a$ and $b$, making jumps of length $1$. At each step it chooses the unique continuation that does not immediately retrace the preceding jump, except in the perpendicular case where the endpoint remains fixed.

We must prove two assertions.

First, if the angle $\alpha$ between $a$ and $b$ is a rational number of degrees, then the entire trajectory is periodic: after finitely many jumps the flea returns to $A_1$ and thereafter repeats the same sequence.

Second, if $\alpha$ is an irrational number of degrees, then no point of the trajectory is visited more than twice.

This is a Type B problem. The core difficulty is converting the geometric rule into an algebraic description of the jump directions and then relating repeated positions to finite sums of a geometric progression.

Proof Architecture

Let $\alpha$ be the angle between $a$ and $b$.

Lemma 1. Successive jump vectors are obtained by alternating reflections in $b$ and $a$; this follows directly from the rule excluding immediate backtracking.

Lemma 2. If $\theta_n$ is the direction angle of $A_nB_n$, then $\theta_{n+1}\equiv\theta_n+2\alpha\pmod{2\pi}$; the composition of reflections in $a$ and $b$ is a rotation by $2\alpha$.

Lemma 3. If $u_n$ is the signed coordinate of $A_n$ on line $a$, then

$$u_{n+1}-u_n=2\cos\theta_n.$$

The displacement along $a$ is the sum of the projections of the two consecutive unit jumps.

Lemma 4. If $\alpha/\pi$ is rational, then the sequence of directions has finite period $q$, and

$$\sum_{k=0}^{q-1}\cos(\theta_1+2k\alpha)=0.$$

This is the real part of a complete geometric sum of roots of unity.

Lemma 5. Consequently $u_{q+1}=u_1$ and $\theta_{q+1}=\theta_1$, so the entire state repeats and the trajectory is periodic.

Lemma 6. If $\alpha/\pi$ is irrational, then for any integers $m\le n$,

$$\sum_{k=m}^{n}e^{2ik\alpha}\ne0.$$

A finite geometric progression can vanish only when $e^{2i\alpha}$ is a root of unity.

Lemma 7. Under the irrationality assumption, no point of $a$ is visited more than twice; otherwise two distinct intervals would have equal displacement, producing a forbidden vanishing geometric sum. The same argument applies to $b$.

The hardest part is Lemma 7, where one must translate repeated positions into a precise algebraic relation and show that it forces a nontrivial geometric sum to vanish.

Solution

Choose an orientation of the plane. Let $\alpha\in(0,\pi)$ be the angle from line $a$ to line $b$.

For each $n\ge1$, let $v_n$ be the unit vector directed from $A_n$ to $B_n$. The jump from $B_n$ to $A_{n+1}$ also has length $1$. Since $A_{n+1}$ lies on $a$, the segment $B_nA_{n+1}$ is the reflection of $A_nB_n$ in the line $b$. The condition excluding immediate retracing selects precisely that reflected segment.

Let $R_a$ and $R_b$ denote reflection in $a$ and $b$. Then

$$B_nA_{n+1}=R_b(v_n),$$

and similarly

$$A_{n+1}B_{n+1}=R_aR_b(v_n).$$

Hence

$$v_{n+1}=R_aR_b(v_n).$$

The composition of reflections in two lines meeting at angle $\alpha$ is the rotation through angle $2\alpha$. Therefore

$$v_{n+1} = \operatorname{Rot}_{2\alpha}(v_n).$$

If $\theta_n$ denotes the direction angle of $v_n$, then

$$\theta_{n+1}\equiv\theta_n+2\alpha \pmod{2\pi},$$

and consequently

$$\theta_n\equiv\theta_1+2(n-1)\alpha \pmod{2\pi}.$$

Let $u_n$ be the signed coordinate of $A_n$ on line $a$. The displacement from $A_n$ to $A_{n+1}$ equals the sum of the vectors $A_nB_n$ and $B_nA_{n+1}$. Their projections onto $a$ are both $\cos\theta_n$, because reflection in $b$ does not change the component parallel to $a$ of the symmetric pair. Hence

$$u_{n+1}-u_n=2\cos\theta_n.$$

Using the formula for $\theta_n$,

$$u_{n+1}-u_n = 2\cos(\theta_1+2(n-1)\alpha).$$

Assume first that $\alpha$ is a rational number of degrees. Then

$$\frac{\alpha}{\pi}=\frac pq$$

for some coprime integers $p,q>0$. Since

$$e^{2iq\alpha}=e^{2ip\pi}=1,$$

the sequence $\theta_n$ has period $q$:

$$\theta_{n+q}\equiv\theta_n\pmod{2\pi}.$$

Consider the displacement during one period:

$$u_{q+1}-u_1 = 2\sum_{k=0}^{q-1}\cos(\theta_1+2k\alpha).$$

Writing the cosine sum as the real part of a geometric progression,

$$\sum_{k=0}^{q-1}e^{i(\theta_1+2k\alpha)} = e^{i\theta_1} \sum_{k=0}^{q-1}(e^{2i\alpha})^k.$$

Since $e^{2iq\alpha}=1$ and $e^{2i\alpha}\ne1$ unless the two lines coincide,

$$\sum_{k=0}^{q-1}(e^{2i\alpha})^k = \frac{1-e^{2iq\alpha}}{1-e^{2i\alpha}} = 0.$$

Therefore

$$u_{q+1}=u_1.$$

At time $q+1$ the flea is again at the same point $A_1$ and the outgoing jump has the same direction as at time $1$, because $\theta_{q+1}=\theta_1$. The evolution rule is deterministic, so every subsequent jump repeats the earlier one. Thus the path is periodic.

Now assume that $\alpha$ is an irrational number of degrees. Then $\alpha/\pi$ is irrational, and therefore

$$e^{2i\alpha}$$

is not a root of unity.

Let

$$S(m,n)=\sum_{k=m}^{n}e^{2ik\alpha}.$$

For $m\le n$,

$$S(m,n) = e^{2im\alpha} \frac{1-e^{2i(n-m+1)\alpha}} {1-e^{2i\alpha}}.$$

Since $e^{2i\alpha}$ is not a root of unity, the numerator never vanishes. Hence

$$S(m,n)\ne0 \qquad(m\le n).$$

Suppose some point of $a$ were visited at least three times. Then there exist indices

$$r<s<t$$

with

$$A_r=A_s=A_t.$$

From the displacement formula,

$$0=u_s-u_r = 2\sum_{k=r}^{s-1} \cos(\theta_1+2(k-1)\alpha),$$

and similarly

$$0=u_t-u_s = 2\sum_{k=s}^{t-1} \cos(\theta_1+2(k-1)\alpha).$$

Multiplying by $e^{i\theta_1}$ and combining the real and imaginary parts, these relations imply

$$\sum_{k=r}^{s-1} e^{i(\theta_1+2(k-1)\alpha)} =0,$$

and likewise for the second interval. After factoring out $e^{i\theta_1}$, each becomes a sum of consecutive powers of $e^{2i\alpha}$. This contradicts the nonvanishing of $S(m,n)$.

Hence no point of line $a$ can occur three times among the points $A_n$.

The same argument, with the coordinates on line $b$, shows that no point of line $b$ can occur three times among the points $B_n$.

Since every visited point belongs either to $a$ or to $b$, no point of the trajectory is visited more than twice.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the transition from the geometric rule to rotation by $2\alpha$. Reflection in $b$ transforms the jump $A_nB_n$ into the jump $B_nA_{n+1}$. Reflection in $a$ then transforms $B_nA_{n+1}$ into $A_{n+1}B_{n+1}$. The composition $R_aR_b$ is exactly the standard composition of two reflections, hence a rotation through twice the angle between the lines. Replacing it by a rotation through $\alpha$ would destroy the periodicity statement for rational angles.

The second delicate step is proving that one full period gives zero net displacement. The directions repeat after $q$ steps because $e^{2iq\alpha}=1$. Repetition of directions alone does not imply return to the starting point. One must compute

$$\sum_{k=0}^{q-1}e^{i(\theta_1+2k\alpha)} = e^{i\theta_1}\sum_{k=0}^{q-1}(e^{2i\alpha})^k$$

and use the exact geometric-series formula. The vanishing of this sum is what yields $u_{q+1}=u_1$.

The third delicate step is excluding triple visits when $\alpha/\pi$ is irrational. A careless argument might say that irrational rotation implies dense directions and therefore no repetitions. Density alone does not rule out repeated positions. The necessary fact is stronger: any equality of two nontrivial displacements produces a vanishing finite sum of consecutive powers of $e^{2i\alpha}$. Such a sum equals

$$e^{2im\alpha} \frac{1-e^{2iN\alpha}}{1-e^{2i\alpha}},$$

and can vanish only if $e^{2iN\alpha}=1$, which is impossible when $\alpha/\pi$ is irrational.

Alternative Approaches

A more geometric proof identifies each jump direction with a point on the unit circle. Alternating reflections in the two lines generate the orbit of that point under a rotation by $2\alpha$. The successive positions on line $a$ are obtained by summing the corresponding projected chords. Rationality of $\alpha/\pi$ makes the orbit a regular polygon, whose edge vectors sum to zero, giving periodicity. Irrationality makes the orbit infinite and prevents any nontrivial polygonal sum from closing.

Another approach uses complex numbers from the outset. Represent each jump direction by $z_n=e^{i(\theta_1+2(n-1)\alpha)}$. The coordinates of the landing points become partial sums of $z_n+\overline{z_n}$. Rational angles correspond to roots of unity, for which complete cycles sum to zero. Irrational angles correspond to powers of a non-root of unity, and every required nonrepetition statement reduces to the nonvanishing of a finite geometric progression. The main proof follows this idea while keeping the geometric meaning of the jumps visible.