Find all positive integers $n \geq 3$, for which it is possible to draw $n$ chords on a circle, with their $2n$ endpoints being pairwise distinct, such that each chords intersects exactly $k$ others for: (a) $k=n-2$, (b) $k=n-3$.
Problem
Source: MEMO 2023 I2
Tags: combinatorics, MEMO2023, geometry
MathGuy1729
26.08.2023 20:42
We will show that it is possible iff $n$ is even (and $n\geq 3$). First, we will prove that it is impossible for odd $n$. Construct a graph where each chord is a vertex and two vertices are connected iff the chords intersect. We know that each vertex has degree $n-2$, and there are $n$ vertices. Therefore, the sum of degrees of all vertices is $n(n-2)$. However, for odd $n$, this is an odd number, but it is also twice as big as the number of edges and therefore even, which is a contradiction. So no odd $n$ work.
To see that it is possible for all even $n$, just take $n/2$ pairs of chords parallel to each other and very close to the diameter parallel to them.
We will show that it is possible for all $n$ ($\geq 3$). If $n$ is divisible by $3$, just take $n/3$ triplets of parallel lines close to the diameter parallel to them. If $n$ is congruent to $1$ mod $3$, do the same as above, but replace one of the triplets with a quadruplet of lines which are all really close to being parallel to each other and some diameter, form $2$ pairs where each line intersects the other in the pair, and are really close to the diameter. If $n$ is congruent to $2$ mod $3$ and greater than $5$, do the same as above, but with $2$ quadruplets instead of $1$. And for $n=5$, form a regular pentagon with all vertices inside the circle, but really close to the boundary, and extend the sides.