Maths Olympiad Prep

Library / Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads /16 of 80

Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

Geometry Difficulty 7.8 National Olympiad, round 2 Prove it Romania

Given an integer number n≥3n \ge 3, consider nn distinct points on a circle, labeled 1 through nn. Determine the maximum number of closed chords [ij][ij], i≠ji \neq j, having pairwise non-empty intersections.

Solution

We shall prove that any such configuration contains at most nn chords and the upper bound is achieved, so the required maximum is nn.

To this end, fix an orientation of the circle and relabel the points 11 through nn in the corresponding circular order. Consider a configuration of chords [ij][ij], i≠ji \neq j, with pairwise non-empty intersections. Assign to each point ii, which is an endpoint of at least one chord, the first point i′i' following ii, to which it is connected. We now show that by deleting the chords [ii′][ii'], no chord is left, so the number of chords in the configuration does not exceed nn.

Suppose, if possible, that some chord [ij][ij] is left. Then i,i′,j,j′i, i', j, j' are in circular order around the circle, so the chords [ii′][ii'] and [jj′][jj'] do not meet – a contradiction.

A maximal configuration is given by the nn chords [1i][1i], i=2,3,…,ni = 2, 3, \dots, n, and [2n][2n].

(The nn points could be located anywhere in the plane, or the chords could be Jordan arcs; the topic is related to John Conway's thrackle conjecture.)

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.