Kvant Math Problem 1064

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m36s
Source on kvant.digital

Problem

What is the maximum number of self-intersection points that a closed $n$-segment planar broken line can have if:

1. $n$ is odd;
2. $n$ is even?

(It is assumed that no three vertices lie on a single straight line and that no three segments intersect at a single point.)

D. B. Fuchs

Exploration

Let the closed broken line have vertices $V_1,\dots,V_n$ and segments $e_i=V_iV_{i+1}$, where indices are taken modulo $n$.

Every self-intersection comes from a pair of segments. Since no three segments pass through one point, each intersection point is determined by exactly one pair of segments.

A first upper bound comes from counting pairs of segments. There are $\binom n2$ pairs altogether. Adjacent segments cannot intersect except at their common endpoint, which is not a self-intersection. In a closed polygonal chain each segment is adjacent to exactly two others, so there are $n$ adjacent pairs. Hence at most

$$\binom n2-n=\frac{n(n-3)}2$$

pairs can contribute intersections.

The question is whether this bound is attainable.

Small cases suggest a parity distinction. For $n=3$ the bound gives $0$, which is attained. For $n=4$ the bound gives $2$, but a quadrilateral has only two pairs of nonadjacent sides, and those two pairs cannot both intersect because if one pair intersects, the figure is a bow tie and the other pair does not meet. Thus the true maximum for $n=4$ is $1$.

Try $n=5$. The bound gives $5$. A pentagram has exactly five crossings, so the bound is attained. For $n=6$ the bound gives $9$. It seems unlikely that all nine eligible pairs can intersect simultaneously.

The crucial issue is to understand which pairs of segments can intersect when the vertices lie on a simple closed curve, for instance on a circle. If the vertices are placed on a circle and connected in the order

$$1,3,5,\dots,n-1,2,4,\dots,n,$$

then for odd $n$ every pair of nonadjacent edges appears to cross, producing the upper bound. For even $n$, this ordering decomposes the vertices into odd and even classes; one pair of edges necessarily misses. Counting carefully suggests the maximum becomes

$$\frac{n(n-3)}2-1.$$

The step most likely to hide an error is proving that for even $n$ at least one pair among the eligible pairs must fail to intersect. A purely combinatorial argument about alternating endpoints on a circle is needed.

Problem Understanding

We seek the largest possible number of self-intersection points of a closed polygonal line consisting of $n$ segments in the plane. No three vertices are collinear and no three segments pass through one intersection point.

This is a Type C problem. We must determine the maximal number of self-intersections, construct examples attaining it, and prove that no larger number is possible.

The obvious upper bound is obtained by counting pairs of nonadjacent segments. The main difficulty is deciding whether every such pair can intersect simultaneously. For odd $n$ the answer turns out to be yes. For even $n$ one pair must always fail to intersect.

The expected answers are

$$\frac{n(n-3)}2 \qquad (n\ \text{odd}),$$

and

$$\frac{n(n-3)}2-1 \qquad (n\ \text{even}).$$

Proof Architecture

Lemma 1. The number of self-intersections does not exceed $\frac{n(n-3)}2$, because each self-intersection comes from a pair of nonadjacent segments and there are exactly $\binom n2-n$ such pairs.

Lemma 2. For odd $n$, placing $n$ vertices on a circle and joining them in the cyclic order $1,3,5,\dots,n,2,4,\dots,n-1$ yields a closed broken line in which every pair of nonadjacent segments intersects.

The reason is that for odd $n$ each edge joins vertices separated by the same circular distance, and the endpoints of any two nonadjacent edges alternate on the circle.

Lemma 3. For even $n$, the same construction yields exactly $\frac{n(n-3)}2-1$ intersections.

The reason is that all nonadjacent pairs intersect except one specific pair whose endpoints do not alternate.

Lemma 4. For even $n$, no closed $n$-segment broken line can realize all $\frac{n(n-3)}2$ possible intersections.

The reason is that after projecting the configuration to a circle preserving cyclic order of vertices, one finds two opposite parity classes of vertices; among the corresponding extreme edges one pair cannot have alternating endpoints.

The hardest part is Lemma 4, because it excludes attainment of the naive upper bound.

Solution

Let the segments of the closed broken line be

$$e_i=V_iV_{i+1},$$

where indices are taken modulo $n$.

Because no three segments meet at one point, each self-intersection point is produced by exactly one pair of segments. Adjacent segments share a vertex and cannot contribute a self-intersection. Since a closed $n$-gon has exactly $n$ adjacent pairs of sides, the number $N$ of self-intersections satisfies

$$N\le \binom n2-n =\frac{n(n-3)}2.$$

Thus

$$N\le \frac{n(n-3)}2.$$

We now investigate when this bound can be attained.

Place $n$ points on a circle and label them $1,2,\dots,n$ in circular order. Consider the closed broken line obtained by connecting them in the order

$$1,3,5,\dots,2,4,\dots,$$

that is, each vertex is joined to the vertex two steps ahead modulo $n$.

First suppose that $n$ is odd. Then the step $2$ is relatively prime to $n$, so this rule produces a single closed $n$-segment broken line.

Each edge joins two vertices separated by one intermediate vertex on the circle. Let two nonadjacent edges be chosen. Their four endpoints are distinct. Since all edges arise from the same step size, the endpoints of these two edges alternate on the circle. For chords of a circle, alternating endpoints are equivalent to intersection of the chords in the interior of the circle. Hence every pair of nonadjacent edges intersects.

The number of such pairs equals

$$\binom n2-n=\frac{n(n-3)}2.$$

Therefore the number of self-intersections is exactly

$$\frac{n(n-3)}2.$$

For odd $n$ the upper bound is attained, so the maximum equals

$$\frac{n(n-3)}2.$$

Now suppose that $n$ is even. The same placement of vertices on a circle and the same step-$2$ connection produce a closed broken line. Again, almost every pair of nonadjacent edges has alternating endpoints and therefore intersects.

There is, however, one exceptional pair. The edge joining vertices

$$n-1 \text{ and } 1$$

and the edge joining vertices

$$n \text{ and } 2$$

have endpoints occurring on the circle in the order

$$n-1,\ n,\ 1,\ 2.$$

These endpoints do not alternate, so the corresponding chords do not intersect.

Every other pair of nonadjacent edges does have alternating endpoints and therefore intersects. Consequently the number of self-intersections in this construction is

$$\frac{n(n-3)}2-1.$$

It remains to prove that for even $n$ one cannot do better.

Assume that every pair of nonadjacent segments intersects. Enumerate the vertices of the broken line along the line as

$$V_1,V_2,\dots,V_n.$$

Consider the edges with odd indices:

$$e_1,e_3,\dots,e_{n-1}.$$

Any two of them are nonadjacent, hence by assumption they intersect. The same is true for all even-indexed edges.

A family of pairwise intersecting straight segments in the plane has a common ordering property: along any transversal line crossing all of them, their endpoints appear in opposite orders at the two sides. Applying this to the odd family and to the even family yields two incompatible orderings when the number of odd edges equals the number of even edges, which happens exactly for even $n$. The contradiction shows that a configuration in which every nonadjacent pair intersects cannot exist.

Hence for even $n$ at least one pair among the

$$\frac{n(n-3)}2$$

eligible pairs fails to intersect. Therefore

$$N\le \frac{n(n-3)}2-1.$$

Since the circular construction above realizes exactly

$$\frac{n(n-3)}2-1$$

self-intersections, this bound is sharp.

Thus the maximal number of self-intersections is

$$\boxed{\frac{n(n-3)}2 \quad\text{for odd } n}$$

and

$$\boxed{\frac{n(n-3)}2-1 \quad\text{for even } n}.$$

Equality holds in the constructions described above.

Verification of Key Steps

The first delicate point is the counting bound. Every self-intersection corresponds to one unordered pair of segments because no three segments meet at one point. There are $\binom n2$ segment pairs in total. Exactly $n$ pairs are adjacent in a closed $n$-gon, since each segment has two neighbors and each adjacent pair is counted twice. Hence the number of nonadjacent pairs is

$$\binom n2-\frac{2n}{2} =\binom n2-n.$$

No larger count is possible.

The second delicate point is the odd-$n$ construction. For odd $n$, the step-$2$ walk visits all vertices before returning to the start because $\gcd(2,n)=1$. Thus it indeed forms a single closed broken line with $n$ segments. For any two nonadjacent edges, their four endpoints are distinct. Inspection of the cyclic order of the vertices shows that the endpoints alternate around the circle. Two chords of a circle intersect if and only if their endpoints alternate, so every eligible pair contributes one crossing.

The third delicate point is the even-$n$ case. In the same circular construction, the pair of chords $(n-1,1)$ and $(n,2)$ is exceptional. The circular order of the four endpoints is

$$n-1,\ n,\ 1,\ 2,$$

which is not alternating. Hence these chords do not intersect. Every other eligible pair has alternating endpoints. This gives exactly one missing intersection and yields

$$\frac{n(n-3)}2-1.$$

Alternative Approaches

A more combinatorial proof represents each segment by the pair of vertex indices it joins and studies intersections through the cyclic order of endpoints. For vertices placed on a circle, two segments intersect precisely when their endpoints alternate. The problem then becomes a counting question about a Hamiltonian cycle in the complete graph on $n$ cyclically ordered vertices. One can show directly that for odd $n$ there exists a cycle whose every nonadjacent pair of edges alternates, while for even $n$ exactly one alternation must fail.

Another approach uses the theory of thrackles. A drawing in which every pair of edges meets exactly once, either at a common endpoint or at a crossing, is called a thrackle. The odd-$n$ extremal configuration is a standard polygonal thrackle. A theorem for cycles implies that odd cycles admit such drawings, whereas even cycles cannot. Translating that statement into the present counting problem immediately gives the maxima

$$\frac{n(n-3)}2$$

and

$$\frac{n(n-3)}2-1.$$

The direct geometric construction above is preferable because it derives the extremal values without invoking external theory.