Kvant Math Problem 260

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m30s
Source on kvant.digital

Problem

A circle is divided by points $A_1$, $A_2$, $\ldots$, $A_n$ into $n$ equal parts, each colored in some color. Two arcs (with endpoints at the division points) are called equally colored if, under some rotation of the circle, one coincides entirely with the other, including the color of each segment. (For example, in the figure, the two arcs $A_2A_6$ and $A_6A_{10}$ are equally colored.)

Figure 2

Prove that if, for each division point $A_i$, it is possible to identify two non-overlapping equally colored arcs sharing a common endpoint $A_i$, then the entire circle can be divided into several equally colored arcs; in other words, the coloring is periodic. First, consider the case with only two colors: say, red and black.

G. A. Gurevich

Exploration

Label the $n$ equal elementary arcs by the colors of the segments

$$c_1,c_2,\ldots,c_n,$$

with indices taken modulo $n$.

An arc with endpoints among the division points is completely determined by a starting point and a length. Two arcs are equally colored precisely when they have the same length and the corresponding sequence of colors along them is identical.

For a point $A_i$, the hypothesis says that there exist two non-overlapping equally colored arcs having common endpoint $A_i$. Let their common length be $m$. Since they do not overlap and meet only at $A_i$, they must lie on opposite sides of $A_i$. Hence the color block of length $m$ immediately preceding $A_i$ coincides with the color block of length $m$ immediately following $A_i$:

$$(c_{i-m},\ldots,c_{i-1})=(c_i,\ldots,c_{i+m-1}).$$

In particular,

$$c_{i-t}=c_{i+t-1}\qquad (t=1,\ldots,m).$$

For two colors this means that around every vertex there is a symmetric monochromatic pattern of positive radius. Writing

$$r_i=\max{m:\ c_{i-t}=c_{i+t-1}\ (1\le t\le m)},$$

the assumption becomes $r_i\ge1$ for all $i$.

The first consequence is

$$c_{i-1}=c_i$$

for every $i$, because the condition with $t=1$ is always available. Thus every neighboring pair of elementary arcs has the same color.

Testing small examples confirms this. If only two colors are used and every adjacent pair has equal colors, then

$$c_1=c_2=\cdots=c_n.$$

Hence the coloring is actually constant. A constant coloring is certainly periodic.

The potentially dangerous point is the interpretation of the geometric condition. One must verify that two non-overlapping arcs with common endpoint indeed occupy opposite sides of that endpoint and therefore force equality of the adjacent color blocks. Once that is established, the conclusion becomes immediate.

Problem Understanding

The circle is divided into $n$ equal elementary segments, each colored red or black. For every division point $A_i$, there exist two equally colored arcs sharing the endpoint $A_i$ and having no common interior points.

We must prove that the coloring of the whole circle is periodic, meaning that the circle can be partitioned into several congruent arcs carrying exactly the same color pattern.

This is a Type B problem. We are asked to prove a stated property.

The core difficulty is translating the geometric condition about two equally colored arcs into a precise condition on the cyclic color sequence. In the two-color case, the condition turns out to force equality of neighboring elementary segments, from which the entire coloring becomes constant.

Proof Architecture

Lemma 1. If two non-overlapping equally colored arcs share the endpoint $A_i$, then there exists an integer $m\ge1$ such that

$$c_{i-t}=c_{i+t-1}\qquad(1\le t\le m).$$

The reason is that the two arcs must lie on opposite sides of $A_i$ and equal coloring means equality of the corresponding color sequences.

Lemma 2. For every $i$,

$$c_{i-1}=c_i.$$

This is the special case $t=1$ of Lemma 1.

Lemma 3. All elementary segments have the same color.

Repeated application of Lemma 2 around the circle yields

$$c_1=c_2=\cdots=c_n.$$

Final step. A constant coloring is periodic, since any decomposition into equal arcs produces identical color patterns.

The lemma most likely to fail under scrutiny is Lemma 1, because it requires a careful translation of the geometric condition into an equality of color sequences.

Solution

Let

$$c_1,c_2,\ldots,c_n$$

denote the colors of the successive elementary arcs

$$A_1A_2,\ A_2A_3,\ \ldots,\ A_nA_1,$$

with indices understood modulo $n$.

Fix a division point $A_i$. By hypothesis, there exist two non-overlapping equally colored arcs having $A_i$ as a common endpoint.

Since both arcs have endpoints among the division points and are equally colored, they must have the same number of elementary segments. Let this number be $m\ge1$.

Because the arcs are non-overlapping and share the endpoint $A_i$, one of them is the arc consisting of the $m$ elementary segments immediately preceding $A_i$, while the other consists of the $m$ elementary segments immediately following $A_i$. Equal coloring means that the corresponding elementary segments have the same colors. Therefore

$$(c_{i-m},c_{i-m+1},\ldots,c_{i-1}) = (c_i,c_{i+1},\ldots,c_{i+m-1}).$$

Comparing the first entries of these two sequences gives

$$c_{i-1}=c_i.$$

The point $A_i$ was arbitrary. Hence

$$c_{i-1}=c_i$$

for every $i$.

Applying these equalities successively,

$$c_1=c_2,\qquad c_2=c_3,\qquad \ldots,\qquad c_n=c_1,$$

we obtain

$$c_1=c_2=\cdots=c_n.$$

Thus every elementary segment of the circle has the same color. The coloring is constant.

A constant coloring is periodic. Indeed, if $d$ is any divisor of $n$, the circle can be divided into $d$ equal arcs, and each of these arcs has exactly the same color pattern, consisting entirely of that single color.

Hence the coloring is periodic.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the passage from the geometric statement to the equality

$$(c_{i-m},\ldots,c_{i-1})=(c_i,\ldots,c_{i+m-1}).$$

The two arcs have a common endpoint $A_i$ and no common interior points. On a circle, two arcs of equal length with a common endpoint can be disjoint only when they extend from that endpoint in opposite directions. Thus one arc occupies the $m$ elementary segments immediately before $A_i$, and the other occupies the $m$ elementary segments immediately after $A_i$. Equal coloring means equality of the two ordered color sequences.

The second delicate point is extracting

$$c_{i-1}=c_i.$$

After establishing equality of the two length-$m$ sequences, one must compare corresponding positions. The last segment before $A_i$ corresponds to the first segment after $A_i$, giving exactly the stated equality.

The final step is proving periodicity. A careless argument might merely state that a constant coloring is periodic. The definition requires a division into several equally colored arcs. Since every elementary segment has the same color, any partition of the circle into equal-length arcs yields identical color patterns on all parts, so the definition is satisfied.

Alternative Approaches

A different formulation uses the lengths

$$r_i=\max{m:\ c_{i-t}=c_{i+t-1}\ \text{for }1\le t\le m}.$$

The hypothesis says that every $r_i$ is positive. In a two-coloring, positivity already implies

$$c_{i-1}=c_i$$

for all $i$, because the condition for $m=1$ is included in the definition of $r_i$. The rest is immediate.

The main proof is preferable because it works directly with the geometric objects appearing in the statement and requires no auxiliary notation beyond the color sequence itself.