$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.

Question

$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least $10000$ others.

There was no information about $n$ in a original problem.

Attempt: Choose at random and uniform a diagonal with a probability $p={1\over 200n}$ and let $X$ be a number of diagonals that choosen one intersect. Then $X=X_1+X_2+...+X_{200n}$ where $X_i$ is an indicator for $i$-th diagonal to cut choosen diagonal. So $$E(X) = E(X_1) +E(X_2)+...= P(X_1 = 1)+...$$

I don't know how to calculate/estimate $P(X_i=1)$.

Any (non)probabilistic solution?

Answer 1

In case anyone is still interested in the question, here is an approach that does not use probability.

Let $A$ denote the set of diagonals. Take a potential ``minimal counterexample" with the smallest $n$. We need to argue a contradiction. Define the length of a diagonal as the number of edges on the minor arc between the two vertices.

The idea is to consider a particular diagonal. We take a parameter $\ell_0$, and consider the shortest diagonal $D$ in $A$ with length at least $\ell_0$. Suppose $D$ has length $\ell \geq \ell_0$. Then

1. This arc divides the polygon into two smaller polygons, with $\ell + 1$ and $n - \ell + 1$ vertices respectively.

2. By the minimal length condition, each member of $A$ that is a diagonal in the polygon with $\ell + 1$ edge must have length at most $\ell_0$. Thus, there are at most $$(\ell - 1) + \cdots + (\ell - \ell_0 + 1) = (\ell_0 - 1)(2\ell - \ell_0+2) / 2$$ such diagonals.

3. By the minimal counterexample condition, less than $200(n - \ell + 1)$ diagonals of $A$ can be a diagonal in the the polygon with $n - \ell + 1$ edges.

4. All the other diagonals in $A$ intersect $D$.

Thus, the number of diagonals intersecting $D$ is at least $$200n - 1 - (200(n - \ell + 1) - 1) - (\ell_0 - 1)(2\ell - \ell_0+2) / 2 = 200(\ell - 1) - (\ell_0 - 1)(2\ell - \ell_0+2) / 2$$ We can optimize over $\ell$. In particular, taking $\ell_0 = 201$ shows the desired result. In fact, this same argument shows that there is one diagonal in $A$ that intersects at least $19700$ other diagonals.