uniolympiads English

IMC 1996, Ημέρα 1, Θέμα 6

Upper content of a subset EE of the plane R2\mathbb{R}^2 is defined as

C(E)=inf⁡{∑i=1ndiam⁡(Ei)}\mathcal{C}(E) = \inf\left\{ \sum_{i=1}^{n} \operatorname{diam}(E_i) \right\}

where inf⁡\inf is taken over all finite families of sets E1,…,EnE_1, \dots, E_n, n∈Nn \in \mathbb{N}, in R2\mathbb{R}^2 such that E⊂⋃i=1nEiE \subset \bigcup_{i=1}^{n} E_i.

Lower content of EE is defined as

K(E)=sup⁡{lenght⁡(L):L is a closed line segment onto which E can be contracted}.\mathcal{K}(E) = \sup\{\operatorname{lenght}(L) : L \text{ is a closed line segment onto which } E \text{ can be contracted}\}.

Show that

(a) C(L)=lenght⁡(L)\mathcal{C}(L) = \operatorname{lenght}(L) if LL is a closed line segment;

(b) C(E)≥K(E)\mathcal{C}(E) \ge \mathcal{K}(E);

(c) the equality in (b) needs not hold even if EE is compact.

Hint. If E=T∪T′E = T \cup T' where TT is the triangle with vertices (−2,2)(-2, 2), (2,2)(2, 2) and (0,4)(0, 4), and T′T' is its reflexion about the xx-axis, then C(E)=8>K(E)\mathcal{C}(E) = 8 > \mathcal{K}(E).

Remarks: All distances used in this problem are Euclidian. Diameter of a set EE is diam⁡(E)=sup⁡{dist⁡(x,y):x,y∈E}\operatorname{diam}(E) = \sup\{\operatorname{dist}(x, y) : x, y \in E\}. Contraction of a set EE to a set FF is a mapping f ⁣:E↦Ff\colon E \mapsto F such that dist⁡(f(x),f(y))≤dist⁡(x,y)\operatorname{dist}(f(x), f(y)) \le \operatorname{dist}(x, y) for all x,y∈Ex, y \in E. A set EE can be contracted onto a set FF if there is a contraction ff of EE to FF which is onto, i.e., such that f(E)=Ff(E) = F. Triangle is defined as the union of the three segments joining its vertices, i.e., it does not contain the interior.

Πρωτότυπο από το επίσημο PDF(25 points) Upper content of a subset E of the plane R 2 is defined as C(E) = inf ( n X i=1 diam(E i ) ) where inf is taken over all finite families of sets E 1 , . . . , E n , n ∈ N , in R 2 n such that E ⊂ ∪ E i . i=1 7 Lower content of E is defined as K(E) = sup {lenght(L) : L is a closed line segment onto which E can be contracted} . Show that (a) C(L) = lenght(L) if L is a closed line segment; (b) C(E) ≥ K(E); (c) the equality in (b) needs not hold even if E is compact. Hint. If E = T ∪ T 0 where T is the triangle with vertices (−2, 2), (2, 2) and (0, 4), and T 0 is its reflexion about the x-axis, then C(E) = 8 > K(E). Remarks: All distances used in this problem are Euclidian. Diameter of a set E is diam(E) = sup{dist(x, y) : x, y ∈ E}. Contraction of a set E to a set F is a mapping f : E 7→ F such that dist(f (x), f (y)) ≤ dist(x, y) for all x, y ∈ E. A set E can be contracted onto a set F if there is a contraction f of E to F which is onto, i.e., such that f (E) = F . Triangle is defined as the union of the three segments joining its vertices, i.e., it does not contain the interior.

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

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

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

Επίσημη λύση

Hint. If E=T∪T′E = T \cup T' where TT is the triangle with vertices (−2,2)(-2, 2), (2,2)(2, 2) and (0,4)(0, 4), and T′T' is its reflexion about the xx-axis, then C(E)=8>K(E)\mathcal{C}(E) = 8 > \mathcal{K}(E).

Solution.

(a) The choice E1=LE_1 = L gives C(L)≤lenght⁡(L)\mathcal{C}(L) \leq \operatorname{lenght}(L). If E⊂∪i=1nEiE \subset \cup_{i=1}^n E_i then ∑i=1ndiam⁡(Ei)≥lenght⁡(L)\displaystyle\sum_{i=1}^n \operatorname{diam}(E_i) \geq \operatorname{lenght}(L): By induction, n=1 obvious, and assuming that En+1E_{n+1} contains the end point aa of LL, define the segment Lε={x∈L:dist⁡(x,a)≥diam⁡(En+1)+ε}L_\varepsilon = \{x \in L : \operatorname{dist}(x, a) \geq \operatorname{diam}(E_{n+1}) + \varepsilon\} and use induction assumption to get ∑i=1n+1diam⁡(Ei)≥lenght⁡(Lε)+diam⁡(En+1)≥lenght⁡(L)−ε\displaystyle\sum_{i=1}^{n+1} \operatorname{diam}(E_i) \geq \operatorname{lenght}(L_\varepsilon) + \operatorname{diam}(E_{n+1}) \geq \operatorname{lenght}(L) - \varepsilon; but ε>0\varepsilon > 0 is arbitrary.

(b) If ff is a contraction of EE onto LL and E⊂∪n=1nEiE \subset \cup_{n=1}^n E_i, then L⊂∪i=1nf(Ei)L \subset \cup_{i=1}^n f(E_i) and lenght⁡(L)≤∑i=1ndiam⁡(f(Ei))≤∑i=1ndiam⁡(Ei)\operatorname{lenght}(L) \leq \displaystyle\sum_{i=1}^n \operatorname{diam}(f(E_i)) \leq \sum_{i=1}^n \operatorname{diam}(E_i).

(c1) Let E=T∪T′E = T \cup T' where TT is the triangle with vertices (−2,2)(-2, 2), (2,2)(2, 2) and (0,4)(0, 4), and T′T' is its reflexion about the xx-axis. Suppose E⊂⋃i=1nEiE \subset \bigcup\limits_{i=1}^n E_i. If no set among EiE_i meets both TT and T′T', then EiE_i may be partitioned into covers of segments [(−2,2),(2,2)][(-2, 2), (2, 2)] and [(−2,−2),(2,−2)][(-2, -2), (2, -2)], both of length 4, so ∑i=1ndiam⁡(Ei)≥8\displaystyle\sum_{i=1}^n \operatorname{diam}(E_i) \geq 8. If at least one set among EiE_i, say EkE_k, meets both TT and T′T', choose a∈Ek∩Ta \in E_k \cap T and b∈Ek∩T′b \in E_k \cap T' and note that the sets Ei′=EiE_i' = E_i for i≠ki \neq k, Ek′=Ek∪[a,b]E_k' = E_k \cup [a, b] cover T∪T′∪[a,b]T \cup T' \cup [a, b], which is a set of upper content at least 8, since its orthogonal projection onto yy-axis is a segment of length 8. Since diam⁡(Ej)=diam⁡(Ej′)\operatorname{diam}(E_j) = \operatorname{diam}(E_j'), we get ∑i=1ndiam⁡(Ei)≥8\displaystyle\sum_{i=1}^n \operatorname{diam}(E_i) \geq 8.

(c2) Let ff be a contraction of EE onto L=[a′,b′]L = [a', b']. Choose a=(a1,a2)a = (a_1, a_2), b=(b1,b2)∈Eb = (b_1, b_2) \in E such that f(a)=a′f(a) = a' and f(b)=b′f(b) = b'. Since lenght⁡(L)=dist⁡(a′,b′)≤dist⁡(a,b)\operatorname{lenght}(L) = \operatorname{dist}(a', b') \leq \operatorname{dist}(a, b) and since the triangles have diameter only 4, we may assume that a∈Ta \in T and b∈T′b \in T'. Observe that if a2≤3a_2 \leq 3 then aa lies on one of the segments joining some of the points (−2,2)(-2, 2), (2,2)(2, 2), (−1,3)(-1, 3), (1,3)(1, 3); since all these points have distances from vertices, and so from points, of T2T_2 at most 50\sqrt{50}, we get that lenght⁡(L)≤dist⁡(a,b)≤50\operatorname{lenght}(L) \leq \operatorname{dist}(a, b) \leq \sqrt{50}. Similarly if b2≥−3b_2 \geq -3. Finally, if a2>3a_2 > 3 and b2<−3b_2 < -3, we note that every vertex, and so every point of TT is in the distance at most 10\sqrt{10} for aa and every vertex, and so every point, of T′T' is in the distance at most 10\sqrt{10} of bb. Since ff is a contraction, the image of TT lies in a segment containing a′a' of length at most 10\sqrt{10} and the image of T′T' lies in a segment containing b′b' of length at most 10\sqrt{10}. Since the union of these two images is LL, we get lenght⁡(L)≤210≤50\operatorname{lenght}(L) \leq 2\sqrt{10} \leq \sqrt{50}. Thus K(E)≤50<8\mathcal{K}(E) \leq \sqrt{50} < 8.

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

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

Πώς πήγε;