IMC 2014 · Day 1 · P5

Place the broken line inside an equilateral triangle $T$ such that their sides are parallel to the segments of the broken line. For every $i = 1, 2, \dots, 3n$, denote by $x_i$ the distance between the segment $A_i A_{i+1}$ and that side of $T$ which is parallel to $A_i A_{i+1}$. We will use indices modulo $3n$ everywhere.

It is easy to see that if $i \equiv j \pmod 3$ then the polylines $A_i A_{i+1} A_{i+2}$ and $A_j A_{j+1} A_{j+2}$ intersect at most once, and this is possible only if either $x_i < x_{i+1}$ and $x_j > x_{j+1}$, or $x_i > x_{i+1}$ and $x_j < x_{j+1}$. Moreover, such cases cover all self-intersections. So, the number of self-intersections cannot exceed number of pairs $(i, j)$ with the property $$(*) \qquad i \equiv j \pmod 3, \text{ and } (x_i < x_{i+1} \text{ and } x_j > x_{j+1}) \text{ or } (x_i > x_{i+1} \text{ and } x_j < x_{j+1}).$$

Grouping the indices $1, 2, \dots, 3n$ by remainders modulo 3, we have $n$ indices in each residue class. Altogether there are $3 \binom{n}{2}$ index pairs $(i, j)$ with $i \equiv j \pmod 3$. We will show that for every integer $k$ with $1 \le k < \frac{n}{2}$, there is some index $i$ such that the pair $(i, i + 6k)$ does not satisfy $(*)$. This is already $\left[ \frac{n-1}{2} \right]$ pair; this will prove that there are at most $$3 \binom{n}{2} - \left[ \frac{n-1}{2} \right] \ge \frac{3}{2} n^2 - 2n + 1$$ self-intersections.

Without loss of generality we may assume that $x_{3n} = x_0$ is the smallest among $x_1, \dots, x_{3n}$. Suppose that all of the pairs $$(**) \qquad (-6k, 0), \ (-6k+1, 1), \ (-6k+2, 2), \ \dots, \ (-1, 6k-1), \ (0, 6k)$$ satisfy $(*)$. Since $x_0$ is minimal, we have $x_{-6k} > x_0$. The pair $(-6k, 0)$ satisfies $(*)$, so $x_{-6k+1} < x_1$. Then we can see that $x_{-6k+2} > x_2$, and so on; finally we get $x_0 > x_{6k}$. But this contradicts the minimality of $x_0$. Therefore, there is a pair in $(**)$ that does not satisfy $(*)$.

Remark. The bound $3 \binom{n}{2} - \left[ \frac{n-1}{2} \right] = \left[ \frac{3n^2}{2} - 2n + 1 \right]$ is sharp.