IMO Team Selection Contest II

If $n$ is odd, one can select all $n-3$ diagonals connecting one fixed vertex to others. In order to prove that the conditions of the problem do not allow more, it suffices to show that no two diagonals are perpendicular. Fix one diagonal arbitrarily; it partitions the boundary of the polygon into two halves, out of which one contains an even number of vertices and the other contains an odd number of vertices. In the latter half, the side that connects two medium vertices is parallel to the chosen diagonal. Thus the existence of two perpendicular diagonals would imply the existence of two perpendicular sides. This is possible only if $n\equiv 0(\mathrm{mod}4)$, contradiction.

If $n\equiv 2(\mathrm{mod}4)$, one can select every second vertex on the boundary and select initially all diagonals that connect two consecutive selected vertices. Furthermore, select all $\frac{n}{2}-3$ diagonals connecting one fixed selected vertex to all other selected vertices that it is not connected to yet. Finally, select the diagonal connecting this very vertex to its opposite vertex of the original polygon. This way, one selects $n-2$ diagonals. If $n\equiv 0(\mathrm{mod}4)$ then one can initially select $\frac{n}{2}$ diagonals as in the previous case, and then select $\frac{n}{2}-2$ more diagonals in the $\frac{n}{2}$-gon formed by the selected diagonals according to the algorithm described in this paragraph.

Now prove that selecting more diagonals is impossible. At first we show that all selected diagonals that intersect some other selected diagonals must lie in two perpendicular directions. Indeed, consider one pair of mutually intersecting diagonals. The number of vertices of the polygon lying between two endpoints of distinct diagonals under consideration is less than half of the number of all vertices of the polygon. If one more pair of mutually intersecting diagonals is added, the same holds for it. This means that the other pair cannot be fit entirely in none of the windows left there by the initial pair of diagonals. Thus at least one diagonal from the first pair and one from the second pair intersect, which means that they all must lie in two perpendicular directions.

Let there be $d$ selected diagonals and $k$ intersection points of selected diagonals. Consider pieces of the plane into which the selected diagonals divide the interior of the polygon; all these pieces are polygons whose vertices coincide with vertices of the original polygon and the intersection points of selected diagonals. The sum of internal angles of all pieces is $(n-2)\cdot 180^{\circ }+k\cdot 360^{\circ }$. The sum of the numbers of vertices of these pieces is $n+2d+4k$, since the initial polygon has $n$ vertices, each diagonal adds 2 endpoints and each intersection of two diagonals adds 4. Let $w$ be the number of pieces; then $(n-2)\cdot 180^{\circ }+k\cdot 360^{\circ }=(n+2d+4k-2w)\cdot 180^{\circ }$, whence $n-2+2k=n+2d+4k-2w$, implying $w=d+k+1$.

Let $w^{\prime }$ be the number of pieces with at least 4 vertices. All pieces with at least two right angles have at least 4 vertices, whence every line segment connecting two neighbouring intersection points of any diagonal is a side of such piece. Let there be $a$ horizontal and $b$ vertical diagonals selected, w.l.o.g. $a\le b$. Then there are $k-a$ pieces whose two right angles are consecutive intersection points on some horizontal selected diagonal and which themselves lie above this diagonal. In addition, there are $b-1$ pieces whose two right angles are consecutive intersection points of some horizontal selected diagonal and which lie below this diagonal and below which there are no more horizontal diagonals. Hence $w^{\prime }\ge k-a+b-1\ge k-1$.

Consequently, $n+2d+4k\ge 4w^{\prime }+3(w-w^{\prime })=3w+w^{\prime }\ge 3w+k-1=3(d+k+1)+k-1=3d+4k+2$, whence $d\le n-2$.