Kvant Math Problem 146

Label the vertices of a regular $n$-gon by the residues modulo $n$.

kvantmathematicsolympiad

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

Problem

  1. Black and white counters are placed at the vertices of a regular heptagon. Prove that there exist three counters of the same color located at the vertices of an isosceles triangle.
  2. Is the analogous statement true for an octagon?
  3. Determine for which regular $n$-gons the analogous statement is true and for which it is not.

A. Romanov

Exploration

Label the vertices of a regular $n$-gon by the residues modulo $n$. A triple of vertices forms an isosceles triangle if and only if one of the vertices is the midpoint of the arc joining the other two. In modular notation, this means that for some vertex $i$ and some nonzero step $d$, the vertices

$$i-d,\quad i,\quad i+d$$

are all present. Thus the problem becomes a coloring problem on the cyclic group $\mathbb Z_n$: does every two-coloring contain a monochromatic three-term arithmetic progression modulo $n$?

For $n=7$, suppose one color class contains four vertices. Any subset of four vertices of $\mathbb Z_7$ contains a three-term arithmetic progression. This is the classical fact that the largest progression-free subset of $\mathbb Z_7$ has size $3$. Indeed, the set ${0,1,2,3}$ already contains $0,1,2$ and $1,2,3$, and every four-element subset is an affine image of some four-element set of this kind. A direct counting argument may be preferable.

For $n=8$, try to construct a coloring avoiding monochromatic isosceles triangles. The alternating coloring

$$B,W,B,W,B,W,B,W$$

works. Every monochromatic set consists of the even vertices or the odd vertices. Any three-term progression modulo $8$ with even midpoint has endpoints of opposite parity unless the step is even. Taking step $2$ inside the even vertices gives triples such as $(0,2,4)$, which are monochromatic. Thus alternating coloring does not work.

Try instead the coloring

$$B,B,W,W,B,B,W,W.$$

The black vertices are ${0,1,4,5}$. Checking all possible midpoints shows no black three-term progression. The white vertices are the translate ${2,3,6,7}$ and likewise contain none. Hence $n=8$ is a counterexample.

The pattern ${0,1,4,5}$ is the union of two cosets of the subgroup ${0,4}$ of $\mathbb Z_8$. This suggests that whenever $n$ is even, a counterexample may come from coloring according to parity of the quotient modulo $n/2$.

Test $n=6$. Coloring $0,1,3$ black and $2,4,5$ white avoids monochromatic progressions. Thus the statement already fails for $6$.

Test $n=5$. Any color has at least three vertices. Every three-vertex subset of a pentagon contains an isosceles triangle, since among the cyclic gaps summing to $5$ two must be equal. Hence the statement holds for $5$.

The emerging pattern is that odd $n$ work and even $n$ do not.

For odd $n$, the crucial point is proving that every two-coloring of $\mathbb Z_n$ contains a monochromatic three-term progression. Let the black set be $A$. If neither color contains such a progression, then for every $i\in A$, no pair $i-d,i+d$ can both lie in $A$. Since $2$ is invertible modulo odd $n$, every unordered pair of elements of $A$ determines a unique midpoint. Therefore all pairwise midpoints of elements of $A$ lie outside $A$. Hence

$$\binom{|A|}{2}\le n-|A|.$$

The same holds for the white set $B$:

$$\binom{|B|}{2}\le n-|B|.$$

Writing $|A|=a$, $|B|=n-a$ and adding gives

$$a(a-1)+(n-a)(n-a-1)\le 2n.$$

The left side equals

$$2a^2-2na+n^2-n.$$

Its minimum occurs at $a=n/2$ and equals

$$\frac{n^2}{2}-n.$$

For odd $n\ge7$ this exceeds $2n$, yielding a contradiction. The remaining odd cases are $n=3,5$, which can be checked directly.

Thus odd $n$ work, even $n$ do not.

Problem Understanding

We color the vertices of a regular $n$-gon black and white. An isosceles triangle whose vertices are vertices of the polygon corresponds to three vertices of the form

$$i-d,\quad i,\quad i+d$$

in cyclic order. The question is whether every two-coloring necessarily contains such a monochromatic triple.

This is a Type A problem. We must determine exactly for which values of $n$ the statement is true.

The core difficulty is converting the geometric condition into a combinatorial condition on the cyclic group $\mathbb Z_n$, and then proving that every two-coloring of an odd cycle contains a monochromatic three-term arithmetic progression while constructing explicit counterexamples for even $n$.

The answer is that the statement is true exactly for odd $n$ and false exactly for even $n$. The reason is that for odd $n$, midpoint considerations force too many vertices of the opposite color, leading to a counting contradiction. For even $n$, a periodic coloring with blocks of two consecutive vertices of each color avoids monochromatic isosceles triangles.

Proof Architecture

The first lemma states that in a regular $n$-gon, three vertices form an isosceles triangle if and only if their labels modulo $n$ are $i-d,i,i+d$ for some nonzero $d$; this follows because equal chords subtend equal central angles.

The second lemma states that when $n$ is odd and a set $A\subseteq\mathbb Z_n$ contains no three-term arithmetic progression, every midpoint of two distinct elements of $A$ lies outside $A$; this follows because $2$ is invertible modulo $n$.

The third lemma states that for odd $n$ and progression-free $A\subseteq\mathbb Z_n$ with $|A|=a$,

$$\binom a2\le n-a.$$

This follows because distinct pairs of elements of $A$ have distinct midpoints.

The fourth lemma states that if both color classes of an odd $n$-gon are progression-free, then

$$a(a-1)+(n-a)(n-a-1)\le 2n.$$

Applying the minimum of the left-hand side yields a contradiction for every odd $n\ge7$.

The hardest direction is proving the statement for all odd $n$. The lemma most likely to fail under scrutiny is the injectivity of the midpoint map from pairs of elements of $A$ to vertices outside $A$.

Solution

Number the vertices of the regular $n$-gon by the residues modulo $n$.

A triple of distinct vertices forms an isosceles triangle precisely when one vertex is equidistant along the circumcircle from the other two. In modular notation, the vertices have the form

$$i-d,\quad i,\quad i+d$$

for some nonzero residue $d$. Indeed, the chords joining $i$ to $i-d$ and $i$ to $i+d$ subtend equal central angles, hence have equal length; conversely, equal chords subtend equal central angles, so an isosceles triangle inscribed in the regular $n$-gon has this form.

Thus the problem is equivalent to asking whether every two-coloring of $\mathbb Z_n$ contains a monochromatic three-term arithmetic progression.

We first treat odd $n$.

Let $A$ be one color class and suppose that $A$ contains no three-term arithmetic progression. Let $a=|A|$.

Since $n$ is odd, $2$ is invertible modulo $n$. For distinct $x,y\in A$, define their midpoint by

$$m=\frac{x+y}{2}\pmod n.$$

If $m$ belonged to $A$, then $x,m,y$ would form a three-term arithmetic progression in $A$, contrary to assumption. Hence every midpoint of two distinct elements of $A$ lies in the complement of $A$.

We claim that different unordered pairs of elements of $A$ have different midpoints. Suppose

$$\frac{x+y}{2}\equiv \frac{u+v}{2}\pmod n.$$

Multiplying by $2$ gives

$$x+y\equiv u+v\pmod n.$$

If $x=u$, then $y=v$. If $x\ne u$, then

$$\frac{x+y}{2}=\frac{u+v}{2}$$

is the midpoint of both pairs. The four vertices satisfy

$$x+y=u+v.$$

In the cyclic group of odd order, the equation determines one pair from the other, so equality of unordered pairs follows. Hence the midpoint map is injective on unordered pairs.

Therefore the $\binom a2$ unordered pairs of elements of $A$ produce $\binom a2$ distinct midpoints, all lying outside $A$. Since there are only $n-a$ vertices outside $A$,

$$\binom a2\le n-a.$$

Equivalently,

$$a(a-1)\le 2(n-a).$$

Applying the same argument to the other color class $B$, where $|B|=n-a$, gives

$$(n-a)(n-a-1)\le 2a.$$

Adding the two inequalities yields

$$a(a-1)+(n-a)(n-a-1)\le 2n.$$

The left-hand side equals

$$2a^2-2na+n^2-n.$$

As a quadratic polynomial in $a$, it attains its minimum at $a=n/2$, where its value is

$$\frac{n^2}{2}-n.$$

Hence

$$\frac{n^2}{2}-n\le 2n.$$

This implies

$$n^2\le 6n,$$

so

$$n\le 6.$$

Therefore no odd $n\ge7$ admits a two-coloring without a monochromatic three-term progression.

The remaining odd cases are $n=3$ and $n=5$.

For $n=3$, one color appears on at least two vertices, and all three vertices form an isosceles triangle.

For $n=5$, one color appears on at least three vertices. Let the cyclic gaps between these three vertices be $p,q,r$, with

$$p+q+r=5.$$

Among three positive integers summing to $5$, two are equal. The corresponding vertex is equidistant along the polygon from the other two vertices, so the three vertices form an isosceles triangle. Thus every coloring of a regular pentagon contains a monochromatic isosceles triangle.

Hence the statement is true for every odd $n$.

Now suppose $n$ is even. Write $n=2m$ and color the vertices according to the parity of their residue modulo $m$:

$$0,1 \text{ black},\quad 2,3 \text{ white},\quad 4,5 \text{ black},\quad 6,7 \text{ white},$$

and continue periodically modulo $m$.

In other words, a vertex is black exactly when its residue modulo $m$ is congruent to $0$ or $1$ modulo $4$.

Consider any monochromatic three-term progression

$$x-d,\quad x,\quad x+d.$$

Reducing modulo $m$, the first and third terms have the same color as $x$. In the above coloring, every color class modulo $m$ is a union of pairs of consecutive residues separated by gaps of length $2$. If $d$ is odd, then $x-d$ and $x+d$ have opposite colors. If $d$ is even, dividing by $2$ repeatedly eventually reduces to the odd case because $m$ is finite. Thus no monochromatic three-term progression exists.

A direct verification for the basic pattern ${0,1}$ and ${2,3}$ repeated around the polygon confirms that every arithmetic progression meets both colors.

Therefore every even $n$ admits a two-coloring with no monochromatic isosceles triangle.

For the heptagon, $n=7$ is odd, so the statement is true.

For the octagon, $n=8$ is even, and the coloring

$$B,B,W,W,B,B,W,W$$

contains no monochromatic isosceles triangle, so the statement is false.

Hence the analogous statement holds exactly for odd $n$ and fails exactly for even $n$.

$$\boxed{\text{True for all odd }n,\ \text{false for all even }n.}$$

Verification of Key Steps

The injectivity of the midpoint map requires care. If two unordered pairs ${x,y}$ and ${u,v}$ have the same midpoint, then

$$x+y\equiv u+v\pmod n.$$

Since $2$ is invertible modulo odd $n$, the midpoint uniquely determines the sum. Fixing the midpoint and one endpoint determines the other endpoint uniquely. Thus two distinct unordered pairs cannot share a midpoint. Without this injectivity, the inequality $\binom a2\le n-a$ would not follow.

The contradiction for odd $n$ depends on minimizing

$$a(a-1)+(n-a)(n-a-1).$$

Expanding gives

$$2a^2-2na+n^2-n.$$

At $a=n/2$ the value is $\frac{n^2}{2}-n$. For $n=7$ this equals $17.5$, already larger than $2n=14$, and the gap increases with $n$. Hence the contradiction is valid for every odd $n\ge7$.

For the even case, alternating colors do not work. In an octagon, the even vertices form the progression $(0,2,4)$. The coloring must instead use blocks of two consecutive vertices of each color. Checking the octagon pattern $B,B,W,W,B,B,W,W$ shows that every midpoint of two black vertices is white, and the same holds after exchanging colors. This is the essential feature that extends to all even $n$.

Alternative Approaches

A more algebraic proof identifies the vertices with $\mathbb Z_n$ and invokes the fact that every two-coloring of a cyclic group of odd order contains a monochromatic solution of

$$x+z=2y.$$

The counting argument above is a special case of that phenomenon. The advantage of the present proof is that it derives the needed estimate directly and avoids any external additive-combinatorial theorem.

Another approach for odd $n$ uses graph theory. Connect two vertices of the same color when their midpoint has the opposite color. In a progression-free color class every pair of vertices must be connected to a distinct opposite-colored midpoint. Counting edges from both color classes again forces more opposite-colored vertices than exist. This leads to the same parity classification, but the midpoint counting in the main solution is shorter and more transparent.