Let $n$ points be given on a circle, and let $nk + 1$ chords between these points be drawn, where $2k+1 < n$. Show that it is possible to select $k+1$ of the chords so that no two of them intersect.
Problem
Source: 17-th Iranian Mathematical Olympiad 1999/2000
Tags: combinatorics proposed, combinatorics
16.12.2005 04:21
Number the points clockwise from $1$ to $n$. Then each chord is a pair $(a, b)$ with $1 \leq a < b \leq n$. We'll show the problem for $k=1$ first: in this case, we want to prove that there are no $n+1$ chords such that any two of them intersect. Let $(a, b), (c, d)$ be any two chords with $a \leq c$. Then they intersect iff $c \leq b \leq d$. Now, take a $2 \times n+1$ board; write a chord on each column with the smaller number on top. Order the chords by smaller first element, from left to right (if $a \leq c$, then $(a, b)$ goes first), and order those with equal first element by smaller second element. Now note that no number on the second row can be smaller than a number on the first row (as otherwise the corresponding chords would be disjoint). Also, for two chords with different 1st element, the one on the right must have greater or equal 2nd element (as otherwise the second would be contained in the first, and they wouldn't intersect). So the second row is ordered as well. Let the first row be $a_1, \ldots, a_{n+1}$ and the second be $b_1, \ldots, b_{n+1}$. We know that $a_1 \leq \ldots \leq a_{n+1} \leq b_1 \leq \ldots \leq b_{n+1}$. Consider $b_{n+1}-a_1$. Clearly this number is $>0$ and $\leq n-1$. On the other hand, each chord has greater sum of elements than the one to the left, so that $a_{i+1}+b_{i+1}-a_i-b_i \geq 1$ for $i=1, \ldots, n$. Now consider the sum of the terms $a_{i+1}+b_{i+1}-a_i-b_i$ for $i=1, \ldots, n$. It is at least $n$, but it telescopes to $a_{n+1}+b_{n+1}-a_1-b_1 \leq b_{n+1}-a_1<n$, absurd. The problem is done for $k=1$. But now it's easy to do it for any $k$: for any set of intersecting chords, we can order them by first element from smaller to larger. If we order those with equal first element by the second element, then it is clear that the ordering contains no cycles, so we're looking at a partially ordered set. Since it's a poset, there's either a chain of length $n+1$ (that is, $n+1$ pairwise intersecting chords) or an antichain of length $k+1$ (disjoint chords). But we've already proved that there were no $n+1$ pairwise intersecting chords. Thus we're done.
09.10.2012 13:01
See also this http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2782715&sid=0b5d42e0500b3977698e32a4e49c7df8#p2782715 for the very case $k=1$.
11.06.2024 17:01
Interesting problem