THE 68th NMO SELECTION TESTS FOR THE BALKAN AND INTERNATIONAL MATHEMATICAL OLYMPIADS

Begin by noticing that a regular polygon with an odd number of vertices has no perpendicular diagonals. Suppose, if possible, that $u,v,x,y$ are vertices, and $uv$ and $xy$ are perpendicular. Consider the vertex $w$ on the perpendicular bisectrix of the segment $uv$, and its antipode $w^{\prime }$ on the circumcircle. Since the segments $wx$ and $w^{\prime }y$ have equal lengths, and $w,x,y$ are vertices of the regular polygon, so is $w^{\prime }$, contradicting the fact that a regular polygon with an odd number of vertices contains no pair of antipodes on the circumcircle.

Since the maximum number of pairwise non-crossing diagonals of a convex $k$-gon is $k-3$, this solves the problem if $n$ is odd.

We now show by induction on $n$ that a cyclic $n$-gon has at most $n-2$ pairwise non-crossing or perpendicular diagonals.

The base case $n=3$ holds vacuously, so let $n\ge 4$, assume the upper bound for any cyclic polygon with less than $n$ vertices, and consider a set $S$ of pairwise non-crossing or perpendicular diagonals of a cyclic $n$-gon.

Assume first that some diagonal in $S$ is crossed by no other diagonal in $S$. That diagonal splits the $n$-gon into an $\ell$-gon and an $m$-gon, where $\ell +m=n+2$, and splits $S$ into corresponding diagonals of the two. Since one of these polygons, say, the $\ell$-gon, lies in a half-circumdisc, no pair of diagonals of the $\ell$-gon cross orthogonally. Consequently, the diagonals in $S$ joining vertices of the $\ell$-gon are pairwise non-crossing, so there are at most $\ell -3$ such. By the induction hypothesis, the $m$-gon has at most $m-2$ pairwise non-crossing or perpendicular diagonals, so $|S|\le (\ell -3)+(m-2)+1=n-2$.

We are left with the case where each diagonal in $S$ is crossed by, and hence perpendicular to, at least one other diagonal in $S$. Fix two crossing, hence orthogonal, diagonals $d$ and $d^{\prime }$ in $S$. Their endpoints split the circumcircle into four non-overlapping arcs, none of which exceeds a semicircle.

We show that any diagonal in $S$ is parallel to one of these two diagonals. Suppose, if possible, that $\delta$ is a diagonal in $S$ parallel to neither. Then one of the four non-overlapping arcs above contains both endpoints of $\delta$. The diagonal ${\delta }^{\prime }$ in $S$, crossing $\delta$ orthogonally, crosses at least one of $d$ and $d^{\prime }$, and since $\delta$ is parallel to neither, ${\delta }^{\prime }$ is orthogonal to neither – a contradiction.

Consequently, at most two diagonals in $S$ may emanate from a vertex of the $n$-gon. Further, no other diagonal in $S$ may emanate from either vertex of the longest diagonal in $S$ parallel to $d$ — otherwise, such a diagonal would be orthogonally crossed by a longer diagonal in $S$. The same holds for the longest diagonal in $S$ parallel to $d^{\prime }$. To conclude, $|S|\le \frac{1}{2}(2(n-4)+4)=n-2$.