uniolympiads English

IMC 2014, Ημέρα 1, Θέμα 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.

Η εκφώνηση έχει σχήμα· το πρωτότυπο:

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

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

(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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;