$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least 10000 others. proposed by D. Karpov, S. Berlov
Problem
Source: 239MO 2004, grade 8-9, problem 8, grade 10-11, problem 7
Tags: induction, combinatorics unsolved, combinatorics
14.12.2004 14:50
Obviously $200n\leq \frac {n(n-3)}2$ so $n\geq 403$. More generally, we prove that if $n>150$ and if no diagonal intersects more than $10000$ others, we have drawn at most $200(n-51)$ diagonals. Proof If $n<350$ we have $\frac {n(n-3)}2\leq 200(n-51)$ and it's obvious. Now if $n>350$ and we have drawn more than $200(n-51)$ diagonals then we have a vertex from which exit at least $350$ diagonals. Take the $200$th diagonal. Now it breaks the polygon into two smaller ones. Let the polygons have sides $k,l$($k+l=n+2)$. We note $k,l>150$ Then by induction hypothesis the number of diagonals in first polygon is at most $200(k-51)$ and in second at most $200(l-51)$. Summing since we have at least $200(n-51)$ diagonals we get at least $10000$ diagonals intorsecting the $200th$ diagonal contradiction QED
15.12.2004 18:52
iura wrote: If $n<350$ we have $\frac {n(n-3)}2\leq 200(n-51)$ and it's obvious. For $n=349$ it is wrong. But I think that this solution may be corrected, though we did not know such solution.
16.12.2004 16:51
Well, we can replace that $n=348$ and do a little bit corrections. But I think this doesn't matter much..
16.12.2004 16:52
What's the official solution?
16.12.2004 16:54
I think, it is quite incorrect question on the forum, which is devoted to problem solving...