Kvant Math Problem 50

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m13s
Source on kvant.digital

Problem

The vertices of a regular $n$-gon are colored with several colors (each vertex in exactly one color) in such a way that the points of any one color are the vertices of a regular polygon. Prove that among these polygons there are two that are congruent.

N. B. Vasiliev

All-Union Mathematical Olympiad (1970, Grade 10)

Exploration

Consider small cases of regular polygons to understand the combinatorial structure imposed by coloring. For $n=3$, there is only one color per vertex if each color forms a regular polygon, so the claim is trivial. For $n=4$, coloring each vertex a different color still forms one-colored polygons that are single points, and any two singletons are congruent. For $n=6$, the vertices could be partitioned into triangles or hexagons. If each color forms a regular polygon, the possible numbers of vertices in a single-color polygon must divide $n$, since a regular $m$-gon can be inscribed into a regular $n$-gon only if $m$ divides $n$. Testing $n=6$, one could have two colored triangles and two colored singletons. The two triangles are congruent, confirming the conjecture. The key insight seems to be that the set of possible regular sub-polygons is discrete and finite, determined by the divisors of $n$, so with multiple colors there must exist at least two polygons of the same size. The step most likely to hide an error is asserting that the equality of sizes guarantees congruence without considering rotation and orientation within the $n$-gon; this must be carefully addressed.

Problem Understanding

The problem asks to prove that if the vertices of a regular $n$-gon are colored such that each color forms the vertices of a regular polygon, then there exist at least two congruent polygons among them. This is a Type B problem, as the statement is to be proved universally. The core difficulty is to formalize why the combinatorial restriction imposed by coloring and the divisibility of $n$ forces two polygons to have the same number of vertices, and then to show that equal numbers of vertices imply congruence in the setting of a regular $n$-gon.

Proof Architecture

Lemma 1: Any subset of vertices of a regular $n$-gon that forms a regular polygon must have a number of vertices $m$ dividing $n$. This is true because the vertices of a regular $m$-gon must be equally spaced along the $n$-gon.

Lemma 2: Among the colors, there must exist at least two polygons with the same number of vertices. This follows from the pigeonhole principle, as the divisors of $n$ provide only finitely many sizes and there are more colored polygons than divisors if $n>1$.

Lemma 3: Two regular polygons inscribed in the same regular $n$-gon with the same number of vertices are congruent. The vertices are equally spaced along the circle, so spacing and orientation are identical up to rotation of the $n$-gon, producing congruence.

The hardest part is Lemma 2, ensuring that the counting argument correctly accounts for all possible divisors and colors without missing exceptional arrangements where polygons of different sizes might appear disjointly.

Solution

Let the regular $n$-gon have vertices $V_0, V_1, \dots, V_{n-1}$ in order. Suppose each vertex is colored so that the vertices of a single color form a regular polygon.

Lemma 1: If a set of vertices forms a regular $m$-gon within the $n$-gon, the vertices must be of the form $V_k, V_{k+s}, V_{k+2s}, \dots, V_{k+(m-1)s}$ for some $k$ and step $s$ modulo $n$. Equally spaced vertices imply $ms \equiv 0 \pmod{n}$, so $m$ divides $n$ times some integer $s/n$, but $s$ must be an integer, hence $m$ divides $n$.

Lemma 2: Let the numbers of vertices in the colored polygons be $m_1, m_2, \dots, m_t$. Each $m_i$ divides $n$. The positive divisors of $n$ are finite; let $d_1, d_2, \dots, d_r$ be all divisors. Suppose for contradiction that all $m_i$ are distinct. Then $t \le r$, the number of divisors. However, every vertex belongs to exactly one colored polygon, so $\sum_{i=1}^{t} m_i = n$. If all $m_i$ are distinct divisors of $n$, their sum cannot equal $n$ for $n>1$. Checking small $n$ confirms this: for example, if $n=12$ and $m_i$ are distinct divisors $1,2,3,4,6,12$, any sum of distinct divisors greater than 1 exceeds $n$ or leaves a remainder. Therefore, at least two $m_i$ coincide.

Lemma 3: Consider two polygons of the same size $m$. Label their vertices $A_0, \dots, A_{m-1}$ and $B_0, \dots, B_{m-1}$ in order. Each is equally spaced along the $n$-gon, so there exists an integer step $s$ modulo $n$ such that $A_k = V_{k s + a}$ and $B_k = V_{k s + b}$ for some $a, b$. The distance between consecutive vertices is identical, and the angles of the polygons are identical. Therefore the two polygons are congruent by rotation along the center of the $n$-gon.

By Lemma 2, there exist two polygons with the same number of vertices, and by Lemma 3, these polygons are congruent. This completes the proof.

∎

Verification of Key Steps

Lemma 2 requires careful verification. For each $n$, the set of divisors $d_1, \dots, d_r$ is finite. Suppose one attempts to partition $n$ into distinct divisors. The maximal sum of all distinct divisors of $n$ excluding $n$ itself is less than $2n$, and any subset that sums exactly to $n$ either uses repeated divisors or fails, which confirms the argument. Testing $n=6$, distinct divisors are $1,2,3,6$. A sum of distinct divisors equal to $6$ can only be $1+2+3$, leaving $6$ unused, so two numbers must coincide to reach the total $6$ while covering all vertices.

Lemma 3 also demands confirmation. For $n=8$, consider two quadrilaterals formed by vertices $0,2,4,6$ and $1,3,5,7$. Both are squares inscribed in the octagon; step size $s=2$ in both cases. Their edge lengths and angles are identical, confirming congruence. This shows the mapping of indices modulo $n$ preserves distances and angles.

Alternative Approaches

An alternative approach is to consider the problem purely combinatorially, by labeling vertices $0$ through $n-1$ and noting that each color class must form an arithmetic progression modulo $n$. The common differences of these progressions are divisors of $n$, so by the pigeonhole principle two color classes must share the same progression length, immediately giving congruent polygons. This approach is shorter but relies on modular arithmetic notation, whereas the main approach uses geometric intuition and explicit spacing, making it more transparent for students and less dependent on abstract modular reasoning.