Kvant Math Problem 815

Verified: no
Verdicts: FAIL + FAIL
Solve time: 32m37s
Source on kvant.digital

Problem

On a circle, $4k$ points are marked and numbered in an arbitrary order with the numbers 1, 2, $\ldots$, $4k$.

1. Prove that these points can be connected pairwise by $2k$ nonintersecting segments so that the difference between the numbers at the endpoints of each segment does not exceed $3k-1$.
2. Construct an example of a numbering arrangement showing that the number $3k-1$ in part (a) cannot be replaced by a smaller one.

A. A. Razborov

Step 1. Reformulation and base case

Place the $4k$ points on a circle in their cyclic order and denote their labels by $a_1,a_2,\ldots,a_{4k}$. A noncrossing perfect matching is equivalent to choosing $2k$ disjoint chords so that no two chords intersect in the interior of the circle.

The problem is purely combinatorial in the cyclic order, since any noncrossing matching depends only on the circular ordering, not on geometric lengths or coordinates.

For $k=1$, four points carry the labels $1,2,3,4$ in some cyclic order. Among all noncrossing perfect matchings, at least one matching contains a chord joining two vertices whose labels are at distance at most $2$. Indeed, consider the three possible noncrossing matchings of four cyclically ordered points; each matching consists of two disjoint chords, and each chord corresponds to one of the three pairings of opposite or adjacent vertices in the cyclic order. Since the labels $1,2,3,4$ form a permutation of consecutive integers, some pair of adjacent vertices on the circle must have labels differing by at most $2$, because if every adjacent pair differed by at least $3$, then summing the four cyclic differences around the circle would give a total increase of at least $12$, contradicting that the total variation of a permutation of ${1,2,3,4}$ around a cycle is $0$. Using this adjacent pair as a chord yields a valid matching satisfying the bound $3k-1=2$.

Step 2. Existence of a bounded chord