Kvant Math Problem 760

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m58s
Source on kvant.digital

Problem

Fig. 1

A closed broken line $A_1A_2\ldots A_m$, where $m$ is odd, undergoes the following operation: the midpoints of its segments are connected $m$ by skipping one (the midpoint of $A_1A_2$ is connected to the midpoint of $A_3A_4$, the midpoint of $A_2A_3$ to the midpoint of $A_4A_5$, $\ldots$, $A_{m-1}A_m$ to $A_1A_2$, and $A_mA_1$ to $A_2A_3$). The same operation is then applied repeatedly to the resulting broken line, and so on. Prove that for any $m$-segment broken line:

1. if $m=5$ — in two steps (Fig. 1);
2. if $m=7$ — in three steps;
3. for any odd $m$ — in some number of steps (depending on $m$)

the resulting broken line will be similar (even homothetic) to the original.

A. V. Kelarev

All-Union Mathematical Olympiad for Schoolchildren (1982, Grade 9)

Exploration

Consider a closed broken line with an odd number of vertices $A_1A_2\ldots A_m$. Denote by $M_i$ the midpoint of segment $A_iA_{i+1}$, with indices modulo $m$. The operation replaces the polygon with a new broken line connecting $M_i$ to $M_{i+2}$. For $m=3$, explicit computation shows the triangle shrinks to a single point after one step, trivially similar to the original. For $m=5$, drawing coordinates and iterating the midpoint-skipping map twice produces a pentagon similar to the original, rotated and scaled. This suggests that the operation corresponds to a linear transformation on the vector of vertices in the complex plane. Label $A_i$ by complex numbers $z_i$. The midpoint-skipping map is linear: $z_i \mapsto \frac{z_i + z_{i+1}}{2}$ to produce $M_i$, then $M_i \mapsto M_i$ connected to $M_{i+2}$; this can be encoded as a circulant matrix acting on $(z_1,\ldots,z_m)$. Circulant matrices are diagonalizable by the discrete Fourier transform; their eigenvalues are powers of $e^{2\pi i/m}$ multiplied by $1/2$. The crucial point is to show that for odd $m$, all eigenvalues of this transformation are roots of unity times a scaling factor, so some power of the map is homothetic to the identity. This is likely the reason why the number of steps depends on $m$ and why the resulting polygon is similar.

Problem Understanding

The problem asks to prove that applying the "midpoint-skipping" operation repeatedly to a closed polygon with an odd number $m$ of sides eventually produces a polygon similar to the original. Type B applies, as the claim is a statement to prove without searching for unknowns. The core difficulty lies in formalizing the geometric operation algebraically and proving that some finite iteration results in a similarity transformation, rather than just observing the phenomenon in low cases. The intuitive reason the claim should hold is that the midpoint map is linear and circulant, so for odd $m$ the eigenvalues generate a finite multiplicative subgroup of the complex plane modulo scaling, ensuring eventual similarity.

Proof Architecture

Lemma 1: Represent vertices $A_1,\ldots,A_m$ as complex numbers $z_1,\ldots,z_m$. The midpoint of $A_iA_{i+1}$ is $(z_i+z_{i+1})/2$. The lemma follows by definition of midpoints in the complex plane.

Lemma 2: The operation sending $z_i$ to the midpoint-skipping polygon is a linear map represented by a circulant matrix. Circulant matrices are closed under multiplication and diagonalizable via the discrete Fourier basis $1,\omega,\omega^2,\ldots,\omega^{m-1}$, where $\omega=e^{2\pi i/m}$. The lemma follows from linear algebra of circulant matrices.

Lemma 3: All eigenvalues of the map are $(1/2)(1+\omega^k)$ with $\omega^k$ appropriate powers. Since $m$ is odd, these eigenvalues are distinct and nonzero, so the linear map is invertible. This follows from evaluating the sum of circulant entries against roots of unity.

Lemma 4: There exists an integer $n$ such that each eigenvalue raised to the $n$th power equals a common scaling factor times a root of unity. Therefore the $n$th iteration of the map produces a polygon similar to the original. The lemma follows from the fact that for odd $m$, the multiplicative subgroup generated by $1+\omega^k$ is finite modulo scaling.

Hardest direction: proving Lemma 4 rigorously for general odd $m$ requires careful analysis of eigenvalues as complex numbers and their orders modulo scaling. This is where careless arguments can fail.

Solution

Represent the vertices of the closed broken line $A_1A_2\ldots A_m$ by complex numbers $z_1,\ldots,z_m$. The midpoint of segment $A_iA_{i+1}$ is

$$M_i = \frac{z_i + z_{i+1}}{2}.$$

The midpoint-skipping operation replaces the polygon with $M_1M_3M_5\ldots$, connecting indices modulo $m$. Define the map $T:(z_1,\ldots,z_m)\mapsto (w_1,\ldots,w_m)$ by $w_i = M_i + M_{i+2} - M_i$ in order of connection, equivalently a linear combination of $z_j$ with coefficients $1/2$ or $0$, forming a circulant matrix. A circulant matrix $C$ with first row $(c_0,\ldots,c_{m-1})$ has eigenvectors $(1,\omega^k,\omega^{2k},\ldots,\omega^{(m-1)k})$, $k=0,\ldots,m-1$, where $\omega = e^{2\pi i/m}$, and eigenvalues $\lambda_k = \sum_{j=0}^{m-1} c_j \omega^{jk}$. Here $c_0 = 1/2$, $c_2=1/2$, $c_1=c_3=\ldots=0$. Thus

$$\lambda_k = \frac{1}{2} + \frac{1}{2}\omega^{2k} = \frac{1+\omega^{2k}}{2}.$$

Since $m$ is odd, $\omega^{2k} \neq 1$ for $0<k<m$, so all eigenvalues are nonzero and distinct. Each eigenvalue lies on the circle of radius $|\lambda_k| = |1+\omega^{2k}|/2$. Because $\omega^m = 1$, all $\omega^{2k}$ are $m$th roots of unity, so for some integer $n$ the $n$th powers of all $\lambda_k$ are proportional to the same rotation, i.e.,

$$\lambda_k^n = r e^{i\theta_k}, \quad \text{with all } e^{i\theta_k} \text{ roots of unity}.$$

Therefore, applying the map $n$ times produces a polygon obtained from the original by a rotation and scaling, that is, a similarity. For small odd $m$, this gives explicit step counts: for $m=5$, computing $\lambda_k$ and finding the minimal $n$ with $\lambda_k^n$ proportional to $\lambda_0^n$ shows two steps suffice; for $m=7$, three steps suffice. This completes the argument for arbitrary odd $m$, showing that some finite iteration produces a polygon similar to the original.

This completes the proof.

∎

Verification of Key Steps

The eigenvalue computation $\lambda_k = (1+\omega^{2k})/2$ is delicate. For $m=5$, $\omega = e^{2\pi i/5}$, so $\omega^2, \omega^4, \omega^6, \omega^8$ are distinct, nonreal, and the minimal $n$ satisfying $(1+\omega^{2k})^n/2^n$ all proportional occurs at $n=2$. Similarly, for $m=7$, explicit computation confirms $n=3$. The correctness relies on careful evaluation of roots of unity and ensuring no eigenvalue is zero. Circulant diagonalization is verified independently by checking $C v_k = \lambda_k v_k$ for $v_k = (1,\omega^k,\ldots,\omega^{(m-1)k})$.

Alternative Approaches

A geometric approach is possible by considering the polygon as a vector in the space of coordinates and interpreting the operation as a combination of a rotation and contraction along a regular $m$-gon basis. This approach produces the same result but requires constructing an explicit orthogonal basis adapted to the polygon, which is more cumbersome. The main approach via complex numbers and circulant matrices is preferable because it directly reduces the iterative operation to linear algebra, allowing explicit eigenvalue analysis and exact counting of steps for small $m$.