Let $n$ be a positive integer. We are given a regular $4n$-gon in the plane. We divide its vertices in $2n$ pairs and connect the two vertices in each pair by a line segment. What is the maximal possible amount of distinct intersections of the segments?
Problem
Source: Slovenia IMO TST 2018, Day 1, Problem 5
Tags: combinatorics, geometry
ThE-dArK-lOrD
18.12.2017 15:34
Suppose our $2n$ diagonals formed by $2n$ pairs are $d_1,d_2,...,d_{2n}$.
For each $i\in \{ 1,2,...,2n\}$, for each diagonal $d_i$, suppose it partition the polygon to two sides, each with $a_i,b_i$ vertices where $a_i+b_i=4n-2$.
Note that the number of intersection point of $d$ and other formed diagonal is at most $\min \{ a_i,b_i\}$.
WLOG $a_i=\min \{ a_i,b_i\}$. We see that $a_i\leq 2n-1$.
Let $S$ denote $\{ i\in \{ 1,2,...,2n\} \mid a_i=2n-1\}$. Let $|S|=k$.
If $k\geq 2$.
Note that all diagonals $d_s$ where $s\in S$ is the longest diagonal of the polygon, so they intersect at one centre point.
Also, for each $s\not\in S$, we've $a_s\leq 2n-2$.
Hence, the number of intersection points between two of $2n$ diagonals is at most $$\frac{(2n-k)(2n-2)+k(2n-1)-k(k-1)}{2}+1=2n^2-2n+1-\frac{k^2-2k}{2}.$$Since $k\geq 2$, the number of those intersection points is at most $2n^2-2n+1$.
If $k\leq 2$, it's not possible for the centre point to be an intersection point, so this gives the number is at most $$\Big\lfloor \frac{(2n-1)(2n-2)+(2n-1)}{2}\Big\rfloor =2n^2-2n.$$In conclusion, the number of intersection points is at most $2n^2-2n+1$.
Let the vertices of polygon are $V_1,V_2,...,V_{4n}$ (in clockwise order).
To see that the $2n^2-2n+1$ bound is achievable, I guess the pairing $\{ V_1,V_{2n+1}\} ,\{ V_2,V_{2n+2}\}$ and $\{ V_{2i-1},V_{2n+2i}\} ,\{ V_{2i},V_{2n+2i-1}\}$ for $i\in \{ 2,3,...,n\}$.
I'm not sure this work yet but, if it work, it can be prove by some trig-Ceva that there’s no three such diagonals intersect at a point.
eisirrational
28.04.2019 08:39
Nice progress!
Indeed the pairing $\{ V_1,V_{2n+1}\} ,\{ V_2,V_{2n+2}\}$ and $\{ V_{2i-1},V_{2n+2i}\} ,\{ V_{2i},V_{2n+2i-1}\}$ for $i\in \{ 2,3,...,n\}$ does suffice.
Let $O$ be the circumcenter. We classify the first two pairs as diameters and all other pairs as diagonals $d$ away from the center, where $d$ is fixed for a fixed $n$. Note that for any point $P$ in the circle with $OP>d$, there are exactly two lines with distance $d$ from the center that pass through $P$; indeed if $M$ is the midpoint of the chord then $OM\perp MP$, giving a locus of a circle, and $OM=d$ so there are two possible positions of $M$. Thus the intersection of two diagonals cannot lie on another diagonal. It remains to check the case when for two diagonals and a diameter.
We claim that if a diameter concurs with two diagonals, then the diameter bisects the two diagonals. This follows from the above circle with diameter $OP$ and noting $OM_1=OM_2 \implies \angle OPM_1=\angle OPM_2$.
For diagonal $V_1V_{2n+1}$ then we wish to show there do not exist $i_1, i_2, j_1, j_2$ so that $V_1$ is the midpoint of arc $V_{i_1}V_{i_2}$ and $V_{2n+1}$ is the midpoint of arc $V_{j_1}V_{j_2}$. Then the line passing through $V_{2i}$ must correspond with $V_{4n+2-2i}$; however these vertices map to $V_{2n+2i-1}$ and $V_{n+1-i}$ with do not mach (i.e., midpoint $V_1$). The line passing through $V_{2i-1}$ must correspond with $V_{4n+3-2i}$; however these vertices map to $V_{2n+2i}$ and $V_{n-i+2}$ which do not match. We can do the same thing for the $V_2V_{2n+2}$ diagonal to finish.