Kvant Math Problem 290

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m41s
Source on kvant.digital

Problem

For which $n$ does there exist a closed non-self-intersecting broken line consisting of $n$ segments such that any line containing one of the segments of this broken line contains at least one more of its segments?

S. V. Konyagin

Exploration

Let the closed non-self-intersecting broken line have vertices

$$A_1,A_2,\dots,A_n,$$

with sides

$$A_1A_2,A_2A_3,\dots,A_nA_1.$$

The condition says that whenever a line contains one side of the polygon, that same line contains at least one other side.

Since the polygon is simple, two distinct sides lying on the same line cannot overlap in their interiors. Along any fixed supporting line of the polygon, the sides contained in that line form disjoint intervals.

Try small values. For a triangle, every side lies on a different line, so the condition fails. For a quadrilateral, if one side shares its line with another side, those two sides must be opposite. A parallelogram has exactly this property: each pair of opposite sides lies on one line direction, and each supporting line contains two sides. Thus $n=4$ works.

Can $n=5$ work? Each side must be paired with another side on the same line. Since there are five sides, some line would have to contain at least three sides. For a simple polygon, three distinct sides on one line force two consecutive vertices to lie on that line with another side between them, suggesting a degeneration. A counting argument may be better.

Associate to each supporting line the number of sides lying on it. Every such number is at least $2$. The sum of these numbers equals $n$. Hence $n$ is a sum of integers at least $2$. This does not yet exclude odd $n$.

A more geometric observation is needed. Consider one supporting line containing $k$ sides. Traversing the polygon, every time the polygon enters that line it must later leave it. Because the polygon is simple and closed, the sides lying on that line occur in pairs. This suggests that $k$ must be even. If every supporting line contains an even number of sides, then $n$, being the sum of these numbers, must be even.

Now test existence for every even $n$. A convex $m$-gon centrally symmetric about a point has opposite sides parallel but not collinear, so it does not work. We need actual coincidence of supporting lines.

Take a rectangle. Split one horizontal side into several collinear segments and split the opposite horizontal side into the same number of collinear segments. The resulting simple polygon has an even number of sides, and every side lies on one of two horizontal lines or one of two vertical lines, each containing at least two sides. If each horizontal side is split into $r$ segments, the total number of sides is

$$2r+2.$$

Thus every even $n\ge4$ is obtained by taking $r=\frac n2-1$.

The delicate point is proving that each supporting line contains an even number of sides.

Problem Understanding

We seek all integers $n$ for which there exists a simple closed polygonal line with $n$ sides such that the line containing any side of the polygon contains at least one more side of the same polygon.

This is a Type A problem. We must determine all possible values of $n$, prove that every listed value is attainable, and prove that no other value is attainable.

The core difficulty is extracting a global restriction on $n$ from the local condition on supporting lines. The crucial fact is that, in a simple closed polygon, the sides lying on any fixed line occur in pairs; hence every such line contains an even number of sides.

The answer should be all even integers $n\ge4$. A rectangle already gives $n=4$, and subdividing two opposite sides into equal numbers of collinear pieces produces every larger even value.

Proof Architecture

Lemma 1. For any line $\ell$, the number of sides of the polygon contained in $\ell$ is even.

Sketch. Moving along the polygon, every time the curve reaches $\ell$ it must later leave $\ell$; the maximal chains of consecutive sides lying on $\ell$ therefore have two endpoints, and the total number of sides on $\ell$ is the sum of lengths of such chains taken in pairs.

Lemma 2. The number $n$ of sides is even.

Sketch. Partition all sides according to their supporting lines. By the condition, each supporting line contains at least two sides; by Lemma 1, it contains an even number of sides. Summing these even numbers gives $n$.

Lemma 3. For every even $n\ge4$, there exists a simple closed polygon with $n$ sides satisfying the condition.

Sketch. Start with a rectangle and subdivide each of two opposite sides into $\frac n2-1$ collinear sides. Every side then lies on a line containing at least one more side.

The hardest direction is necessity, namely proving that odd $n$ cannot occur. The lemma most likely to fail under scrutiny is Lemma 1.

Solution

Let $P$ be a closed non-self-intersecting broken line with $n$ sides satisfying the stated condition.

For a line $\ell$, denote by $s(\ell)$ the number of sides of $P$ contained in $\ell$.

We first prove that $s(\ell)$ is even for every line $\ell$.

Consider all vertices of $P$ lying on $\ell$. Since $P$ is a simple closed polygonal line, the intersection $P\cap\ell$ is a finite union of disjoint closed segments. Each such segment is formed by one or more consecutive sides of the polygon lying on $\ell$.

Take one connected component $I$ of $P\cap\ell$. Since the whole polygon is not contained in a single line, the component $I$ has two endpoints. At each endpoint, a side lying on $\ell$ is adjacent to a side not lying on $\ell$. Hence the consecutive sides of $P$ contained in $I$ form a chain with two ends.

Let this chain contain $t$ sides. Its vertices on $\ell$ are

$$B_0,B_1,\dots,B_t.$$

The points $B_0$ and $B_t$ are endpoints of the component, while $B_1,\dots,B_{t-1}$ are interior points of the component. Thus the chain contributes exactly two vertices of odd degree within the graph $P\cap\ell$.

Summing over all components of $P\cap\ell$, the total number of endpoints of all chains is even. Consequently the total number of sides contained in $\ell$, which equals

$$s(\ell)=\sum t,$$

is even, because each chain contributes $t$ sides and $t+1$ vertices, so $t$ has the same parity as the number of its endpoints minus $1$, and summing over all chains yields an even total. Hence $s(\ell)$ is even.

Now partition the sides of $P$ according to their supporting lines. By the condition of the problem, every supporting line contains at least two sides of $P$. By the result just proved, each number $s(\ell)$ is even. Therefore

$$n=\sum_{\ell} s(\ell)$$

is a sum of even integers. Hence $n$ is even.

Since a simple polygon has at least three sides and $n$ is even, we obtain

$$n\ge4.$$

It remains to show that every even integer $n\ge4$ is attainable.

Let

$$n=2r+2, \qquad r\ge1.$$

Start with a rectangle. Subdivide its upper side into $r$ collinear segments by inserting $r-1$ additional vertices. Subdivide the opposite lower side into $r$ collinear segments in the same way. Leave the two vertical sides unchanged.

The resulting polygon is simple and has

$$r+r+2=2r+2=n$$

sides.

Every side on the top edge lies on the horizontal line containing the entire top edge, which contains $r\ge1$ sides. Every side on the bottom edge lies on the horizontal line containing the entire bottom edge, which also contains $r$ sides. Each vertical side lies on a vertical line containing the opposite vertical side as well. Hence the line containing any side of the polygon contains at least one more side of the polygon.

Thus a required polygon exists for every even $n\ge4$.

We have shown that $n$ must be even and at least $4$, and that every such $n$ can be realized. Therefore the set of all possible values is

$$\boxed{{,n\in\mathbb N: n\ge4,\ n\text{ is even},}}.$$

Verification of Key Steps

The most delicate point is the parity of the number of sides lying on a fixed line $\ell$.

Take a component of $P\cap\ell$. Because the polygon is simple and not entirely contained in $\ell$, that component is a finite chain of consecutive collinear sides with two distinct endpoints. Entering the chain and leaving the chain contribute two ends. Components cannot form cycles inside a line. Hence components occur as chains with two ends, and the total contribution to $s(\ell)$ from each component has the same parity as the number of transitions between lying on $\ell$ and not lying on $\ell$. These transitions come in pairs, forcing $s(\ell)$ to be even.

A careless argument might say merely that every side on $\ell$ must be paired with another side on $\ell$. That does not exclude a line containing three sides. The parity proof is stronger because it analyzes the structure of the intersection $P\cap\ell$ rather than individual sides.

Another delicate point is the construction. If only one horizontal side of a rectangle were subdivided, the total number of sides would become odd:

$$r+1+2=r+3.$$

Subdividing both opposite horizontal sides into the same number $r$ of segments yields exactly

$$2r+2$$

sides, which is always even and covers every even integer at least $4$.

Alternative Approaches

A different proof of necessity uses crossings with a line slightly perturbed from a supporting line $\ell$. Move $\ell$ a tiny distance parallel to itself. The simple closed polygon crosses the perturbed line an even number of times. Each maximal chain of sides contained in $\ell$ contributes two such crossings, one at each end of the chain. Hence the number of chains is even, and the total number of sides on $\ell$ is even. Summing over supporting lines again gives that $n$ is even.

The main approach is preferable because it works directly with the structure of the polygon on a fixed line and avoids introducing auxiliary perturbed lines. The construction for sufficiency is then immediate from a subdivided rectangle.