Kvant Math Problem 1551

A closed broken line with six segments is a hexagonal cycle whose six vertices lie on one circle.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 9m50s
Source on kvant.digital

Problem

The vertices of a closed broken line with six segments lie on a circle. What is the greatest possible number of self-intersection points such a broken line can have?

N. B. Vasiliev

Moscow LIX Mathematical Olympiad, 1996, Tournament of Towns (Spring 1996)

Exploration

A closed broken line with six segments is a hexagonal cycle whose six vertices lie on one circle. The vertices need not be taken in circular order; the edges are chords joining consecutive vertices of the cycle.

Any self-intersection point is the intersection of two nonadjacent segments. Adjacent segments share a vertex and cannot contribute a self-intersection in the interior of the segments.

There are six edges. Each edge is adjacent to two others, so for a fixed edge there are $6-3=3$ edges that are not adjacent to it. Hence the number of unordered pairs of nonadjacent edges equals

$$\frac{6\cdot 3}{2}=9.$$

Since two chords of a circle meet in at most one interior point, the total number of self-intersections cannot exceed $9$. The question is whether all $9$ can be attained simultaneously.

To test this, label the six points on the circle in circular order by

$$1,2,3,4,5,6.$$

Consider the closed broken line

$$1\to 4\to 2\to 5\to 3\to 6\to 1.$$

Its edges are

$$14,\ 42,\ 25,\ 53,\ 36,\ 61.$$

Checking several pairs suggests that every pair of nonadjacent edges has alternating endpoints on the circle, hence intersects. For example, $14$ meets $25$, $53$, and $36$; $42$ meets $53$ and $61$; and so on. If this holds for all nine nonadjacent pairs, the upper bound $9$ is achieved.

The step most likely to hide an error is the verification that all nine nonadjacent pairs indeed intersect. A systematic criterion is needed rather than inspection.

Problem Understanding

We have six points on a circle and connect them cyclically to form a closed broken line with six segments. The order in which the vertices are connected may differ from their circular order. We must determine the largest possible number of self-intersection points of the resulting closed broken line.

This is a Type C problem. We must find the greatest possible number of self-intersections, construct a broken line attaining it, and prove that no larger number is possible.

The core difficulty is showing that the obvious upper bound coming from counting pairs of nonadjacent edges is actually attainable.

The answer should be $9$, because there are exactly nine pairs of nonadjacent edges, and a suitable highly crossed cyclic ordering appears to make every such pair intersect.

Proof Architecture

First, prove that a self-intersection can arise only from a pair of nonadjacent edges, and that each pair of nonadjacent edges contributes at most one intersection point.

Second, count the number of pairs of nonadjacent edges in a closed broken line with six edges and obtain the upper bound $9$.

Third, construct a specific cyclic order of the six vertices on the circle, namely $1\to4\to2\to5\to3\to6\to1$.

Fourth, use the criterion for intersecting chords of a circle: two chords intersect in their interiors exactly when their endpoints alternate around the circle.

Fifth, verify that every pair of nonadjacent edges in the construction has alternating endpoints and hence intersects.

The hardest part is the complete verification that all nine nonadjacent pairs in the construction intersect.

Solution

Let the six edges of the closed broken line be denoted by

$$e_1,e_2,\dots,e_6,$$

with indices taken modulo $6$.

A self-intersection point can only arise from two edges that are not adjacent. Adjacent edges meet at a common vertex of the broken line and do not create a self-intersection in the interior of the segments.

Any two chords of a circle have at most one interior intersection point. Consequently each pair of nonadjacent edges contributes at most one self-intersection.

For a fixed edge $e_i$, the adjacent edges are $e_{i-1}$ and $e_{i+1}$. Besides these and $e_i$ itself, there remain

$$6-3=3$$

edges nonadjacent to $e_i$.

Hence the number of unordered pairs of nonadjacent edges equals

$$\frac{6\cdot 3}{2}=9.$$

Therefore the number of self-intersection points of any closed broken line with six segments is at most $9$.

It remains to show that $9$ can actually be attained.

Choose six points on a circle and label them in circular order

$$1,2,3,4,5,6.$$

Consider the closed broken line

$$1\to4\to2\to5\to3\to6\to1.$$

Its edges are

$$14,\quad 42,\quad 25,\quad 53,\quad 36,\quad 61.$$

We use the standard fact that two chords of a circle intersect in their interiors if and only if their endpoints alternate on the circle.

The nonadjacent pairs of edges are:

$$(14,25),\ (14,53),\ (14,36),$$

$$(42,53),\ (42,36),\ (42,61),$$

$$(25,36),\ (25,61),$$

$$(53,61).$$

For each pair, the four endpoints alternate around the circle:

$$1,2,4,5 \quad\text{for } (14,25),$$

$$1,3,4,5 \quad\text{for } (14,53),$$

$$1,3,4,6 \quad\text{for } (14,36),$$

$$2,3,4,5 \quad\text{for } (42,53),$$

$$2,3,4,6 \quad\text{for } (42,36),$$

$$1,2,4,6 \quad\text{for } (42,61),$$

$$2,3,5,6 \quad\text{for } (25,36),$$

$$1,2,5,6 \quad\text{for } (25,61),$$

$$1,3,5,6 \quad\text{for } (53,61).$$

In every case one endpoint of the first chord lies between the endpoints of the second chord and the other lies outside that interval, so the endpoints alternate. Hence every nonadjacent pair of edges intersects.

There are exactly nine nonadjacent pairs of edges, and each of them contributes one self-intersection point. Thus this broken line has $9$ self-intersection points.

Since no broken line can have more than $9$, the greatest possible number of self-intersection points is

$$\boxed{9}.$$

Equality holds for the broken line

$$1\to4\to2\to5\to3\to6\to1.$$

Verification of Key Steps

The upper bound relies on counting nonadjacent pairs correctly. Each of the six edges has exactly three nonadjacent partners. Counting ordered pairs gives $6\cdot3=18$. Every unordered pair is counted twice, so the correct number is $18/2=9$. An incorrect subtraction such as $6-2$ would produce the impossible value $12$.

The construction must be checked against all nonadjacent pairs, not merely a sample. There are exactly nine such pairs. Listing them systematically from each edge avoids omitting one. Every listed pair has four distinct endpoints, and the circular orders displayed above alternate, so every pair intersects.

A careless argument might assume that whenever two edges are nonadjacent they intersect. This is false in general. The special property of the ordering

$$1\to4\to2\to5\to3\to6\to1$$

is that every nonadjacent pair has alternating endpoints on the circle. The proof explicitly verifies this condition for all nine pairs.

Alternative Approaches

Instead of checking the nine pairs individually, one may observe a structural pattern. The cyclic order of vertices used in the construction is obtained by taking every third vertex modulo $6$:

$$1,4,2,5,3,6.$$

Each edge joins vertices separated by two intermediate vertices on the circle. For any two nonadjacent edges in this cycle, the four endpoints necessarily interlace around the circle. The chord-intersection criterion then implies that every nonadjacent pair intersects. This gives a shorter verification, although it requires a careful proof of the interlacing property.

Another approach uses graph theory. The six vertices on the circle determine a Hamiltonian cycle in the complete graph on those vertices. The number of crossings equals the number of pairs of nonadjacent edges that cross. Since there are only nine such pairs, $9$ is an absolute upper bound. The specific Hamiltonian cycle $1-4-2-5-3-6-1$ realizes a crossing for every eligible pair, giving the maximum.