uniolympiads Ελληνικά

IMC 1996, Day 1, Problem 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.

Original from the official 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.

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

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.

Transcribed from the official solutions, pages 8–9. 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?