uniolympiads Ελληνικά

IMC 2014, Day 1, Problem 5

Let A1A2…A3nA_1A_2 \dots A_{3n} be a closed broken line consisting of 3n3n line segments in the Euclidean plane. Suppose that no three of its vertices are collinear, and for each index i=1,2,…,3ni = 1, 2, \dots, 3n, the triangle AiAi+1Ai+2A_iA_{i+1}A_{i+2} has counterclockwise orientation and ∠AiAi+1Ai+2=60∘\angle A_iA_{i+1}A_{i+2} = 60^\circ, using the notation A3n+1=A1A_{3n+1} = A_1 and A3n+2=A2A_{3n+2} = A_2. Prove that the number of self-intersections of the broken line is at most 32n2−2n+1\frac{3}{2}n^2 - 2n + 1.

The statement has a figure; the original:

Let A 1 A 2 . . . A 3n be a losed broken line onsisting of 3n line segments in the Eu lidean plane. Suppose that no three of its verti es are ollinear, and for ea h index i = 1, 2, . . . , 3n , the triangle A i A i+1 A i+2 has ounter lo kwise orientation and ∠A i A i+1 A i+2 = 60 ◦ , using the notation A 3n+1 = A 1 and A 3n+2 = A 2 . Prove that the 3 number of self-interse tions of the broken line is at most n 2 − 2n + 1 . 2 A 3 A 6 A 4 A 1 A 5 A 2

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Martin Langer)

Solution. Place the broken line inside an equilateral triangle TT such that their sides are parallel to the segments of the broken line. For every i=1,2,…,3ni = 1,2,\ldots,3n, denote by xix_i the distance between the segment AiAi+1A_iA_{i+1} and that side of TT which is parallel to AiAi+1A_iA_{i+1}. We will use indices modulo 3n3n everywhere.

It is easy to see that if i≡j(mod3)i \equiv j \pmod 3 then the polylines AiAi+1Ai+2A_iA_{i+1}A_{i+2} and AjAj+1Aj+2A_jA_{j+1}A_{j+2} intersect at most once, and this is possible only if either xi<xi+1x_i < x_{i+1} and xj>xj+1x_j > x_{j+1} or xi<xi+1x_i < x_{i+1} and xj>xj+1x_j > x_{j+1}. Moreover, such cases cover all self-intersections. So, the number of self-intersections cannot exceed number of pairs (i,j)(i,j) with the property

(∗)  i≡j(mod3),and(xi<xi+1 and xj>xj+1)or(xi>xi+1 and xj<xj+1).(*)\ \ i \equiv j \pmod 3, \quad \text{and} \quad (x_i < x_{i+1} \text{ and } x_j > x_{j+1}) \quad \text{or} \quad (x_i > x_{i+1} \text{ and } x_j < x_{j+1}).

[Figure in the original PDF.]

Grouping the indices 1,2,…,3n1,2,\ldots,3n, by remainders modulo 3, we have nn indices in each residue class. Altogether there are 3(n2)3\binom n2 index pairs (i,j)(i,j) with i≡j(mod3)i\equiv j \pmod 3. We will show that for every integer kk with 1≤k<n21 \le k < \frac n2, there is some index ii such that the pair (i,i+6k)(i, i+6k) does not satisfy (∗)(*). This is already [n−12]\left[\frac{n-1}{2}\right] pair; this will prove that there are at most

3(n2)−[n−12]≥32n2−2n+13\binom n2 - \left[\frac{n-1}{2}\right] \ge \frac32 n^2 - 2n + 1
self-intersections.

Without loss of generality we may assume that x3n=x0x_{3n} = x_0 is the smallest among x1,…,x3nx_1,\ldots,x_{3n}. Suppose that all of the pairs

(−6k,0),(−6k+1,1),(−6k+2,2),…,(−1,6k−1),(0,6k)(∗∗)(-6k,0), \quad (-6k+1,1), \quad (-6k+2,2), \quad \ldots, \quad (-1,6k-1), \quad (0,6k) \tag{$**$}
satisfy (∗)(*). Since x0x_0 is minimal, we have x−6k>x0x_{-6k} > x_0. The pair (−6k,0)(-6k,0) satisfies (∗)(*), so x−6k+1<x1x_{-6k+1} < x_1. Then we can see that x−6k+2>x2x_{-6k+2} > x_2, and so on; finally we get x0>x6kx_0 > x_{6k}. But this contradicts the minimality of x0x_0. Therefore, there is a pair in (**) that does not satisfy (∗)(*).

Remark. The bound 3(n2)−[n−12]=[32n2−2n+1]3\binom n2 - \left[\frac{n-1}{2}\right] = \left[\frac32 n^2 - 2n + 1\right] is sharp.

Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?