62nd Ukrainian National Mathematical Olympiad

Question

11 points are given on a circle. Petrik numbered them by the numbers

1, 2, \dots, 11

. After that, pairs of points were connected by segments:

1

and

2

,

2

and

3

,

\dots

,

10

and

11

,

11

and

1

. What is the largest possible number of intersection points of these segments? The given 11 points are not counted as intersection points.

Fig. 4

Accepted Answer

Consider one of the drawn segments. It cannot intersect itself, nor the adjacent segments on either side, e.g., the segment 3–4 does not intersect the segments 2–3, 3–4, and 4–5. Thus the maximum number of possible intersection points occurs when each of the segments intersects all the other 8 non-adjacent segments. This can be achieved by numbering the points around the circle in the following way (see Fig. 4): 1 - 3 - 5 - 7 - 9 - 11 - 2 - 4 - 6 - 8 - 10 - 1. The number of intersection points is equal to 12 11 8 = 44.