Given an integer number $n \geq 3$, consider $n$ distinct points on a circle, labelled $1$ through $n$. Determine the maximum number of closed chords $[ij]$, $i \neq j$, having pairwise non-empty intersections. János Pach
Problem
Source: Romania TST 1 2010, Problem 1
Tags: pigeonhole principle, combinatorics proposed, combinatorics
26.08.2012 07:35
Note that we can assume that the $n$ distinct points on the circle form a regular polygon, without changing the problem. Introduce the points $1.5$, $2.5$, ..., $n+\frac{1}{2}$, where $1.5$ is the midpoint of the minor arc $1, 2$ etc. Consider the $n$ diameters $k, k+\frac{n}{2}$ where $k$ is an integer multiple of $\frac{1}{2}$ and $1 \le k \le \frac{n+1}{2}$. Observe that any chord connecting two of the original $n$ distinct points on the circle is perpendicular to exactly one of the $n$ diameters outlined above, and that the chords connecting two of the original $n$ distinct points on the circle which are perpendicular to the same diameter are non-intersecting. Thus, by the Pigeonhole Principle, there are at most $n$ chords. Construction of $n$ chords: Draw the $n-1$ chords connecting $1$ to another vertex. Then draw chord $2, n$ and we have a desired construction.
27.08.2012 12:51
23.11.2014 14:26
The answer is $n$.Construction:Have all cords from $1$ and chord $2,n$.Now,just divide the set of all diagonals in $n$ sets such than in every set no $2$ diagonals intersect.For odd $n$,divide it like in each set $(n-1)/2$ parallel diagonals(cause of orientation assume that these $n$ points form a regural $n$-gon),and for even $n$ divide it in sets off parallel diagonals in a bit different way but it is easy so I won't explain,so we are finished.