uniolympiads Ελληνικά

IMC 2020, Day 1, Problem 3

Let d≥2d \ge 2 be an integer. Prove that there exists a constant C(d)C(d) such that the following holds: For any convex polytope K⊂RdK \subset \mathbb{R}^d, which is symmetric about the origin, and any ε∈(0,1)\varepsilon \in (0, 1), there exists a convex polytope L⊂RdL \subset \mathbb{R}^d with at most C(d)ε1−dC(d)\varepsilon^{1-d} vertices such that

(1−ε)K⊆L⊆K.(1 - \varepsilon)K \subseteq L \subseteq K.

(For a real α\alpha, a set T⊂RdT \subset \mathbb{R}^d with nonempty interior is a convex polytope with at most α\alpha vertices, if TT is a convex hull of a set X⊂RdX \subset \mathbb{R}^d of at most α\alpha points, i.e., T={∑x∈Xtxx∣tx≥0,∑x∈Xtx=1}T = \{\sum_{x \in X} t_x x \mid t_x \ge 0, \sum_{x \in X} t_x = 1\}. For a real λ\lambda, put λK={λx∣x∈K}\lambda K = \{\lambda x \mid x \in K\}. A set T⊂RdT \subset \mathbb{R}^d is symmetric about the origin if (−1)T=T(-1)T = T.)

Fedor Petrov, St. Petersburg State University

Original from the official PDFLet d ≥ 2 be an integer. Prove that there exists a constant C(d) such that the following holds: For any convex polytope K ⊂ R d , which is symmetric about the origin, and any ε ∈ (0, 1) , there exists a convex polytope L ⊂ R d with at most C(d)ε 1−d vertices such that Problem 3. (1 − ε)K ⊆ L ⊆ K. (For a real α , a set T ⊂ R d with nonempty interior is a convex polytope vertices , if P with at most α P d T is a convex hull of a set X ⊂ R of at most α points, i.e., T = { x∈X t x x | t x ≥ 0, x∈X t x = 1} . For a real λ , put λK = {λx | x ∈ K} . A set T ⊂ R d is symmetric about the origin if (−1)T = T .) Fedor Petrov, St. Petersburg State University

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

Fedor Petrov, St. Petersburg State University

Solution [in elementary terms] Let {p1,…,pm}\{p_1, \ldots, p_m\} be an inclusion-maximal collection of points on the boundary ∂K\partial K of KK such that the homothetic copies Ki:=pi+ε2KK_i := p_i + \frac{\varepsilon}{2}K have disjoint interiors. We claim that the convex hull L:=conv{p1,…,pm}L := \mathrm{conv}\{p_1, \ldots, p_m\} satisfies all the conditions.

First, note that by convexity of KK we have aK+bK=(a+b)KaK + bK = (a+b)K for a,b>0a, b > 0. It follows that Ki⊂(1+ε2)KK_i \subset (1 + \frac{\varepsilon}{2})K. On the other hand, if k∈Kk \in K, a>0a > 0 and and ak∈Kiak \in K_i, then

pi∈ak−ε2K=ak+ε2K⊂(a+ε2)K,p_i \in ak - \frac{\varepsilon}{2}K = ak + \frac{\varepsilon}{2}K \subset (a + \frac{\varepsilon}{2})K,
and since pip_i is a boundary point of KK, we get a+ε2⩾1a + \frac{\varepsilon}{2} \geqslant 1, a⩾1−ε2a \geqslant 1 - \frac{\varepsilon}{2}. It means that all KiK_i lie between (1−ε2)K(1 - \frac{\varepsilon}{2})K and (1+ε2)K(1 + \frac{\varepsilon}{2})K. Since their interiors are disjoint, by the volume counting we obtain
m(ε2)d⩽(1+ε2)d−(1−ε2)d⩽(3/2)dεm\left(\frac{\varepsilon}{2}\right)^d \leqslant \left(1 + \frac{\varepsilon}{2}\right)^d - \left(1 - \frac{\varepsilon}{2}\right)^d \leqslant (3/2)^d\varepsilon
(since F(ε)=(1+ε2)d−(1−ε2)dF(\varepsilon) = (1 + \frac{\varepsilon}{2})^d - (1 - \frac{\varepsilon}{2})^d is a polynomial in ε\varepsilon without constant term with non-negative coefficients which sum up to (3/2)d−(1/2)d(3/2)^d - (1/2)^d), therefore m⩽3dε1−dm \leqslant 3^d\varepsilon^{1-d}.

It is clear that L⊆KL \subseteq K, so it remains to prove that (1−ε)K⊆L(1-\varepsilon)K \subseteq L. Assume the contrary: there exists a point p∈(1−ε)K∖Lp \in (1-\varepsilon)K \setminus L. Separate pp from LL by a hyperplane: Choose a linear functional ℓ\ell such that ℓ(p)>max⁡x∈Lℓ(x)=max⁡iℓ(pi)\ell(p) > \max_{x \in L} \ell(x) = \max_i \ell(p_i). Choose x∈Kx \in K such that ℓ(x)=:a\ell(x) =: a is maximal possible. Note that by our construction x+ε2Kx + \frac{\varepsilon}{2}K has a common point with some KiK_i: there exists a point z∈(x+ε2K)∩(pi+ε2K)z \in (x + \frac{\varepsilon}{2}K) \cap (p_i + \frac{\varepsilon}{2}K). We have

ℓ(pi)+ε2a⩾ℓ(z)⩾ℓ(x)−ε2a,\ell(p_i) + \frac{\varepsilon}{2}a \geqslant \ell(z) \geqslant \ell(x) - \frac{\varepsilon}{2}a,
and therefore ℓ(pi)⩾a(1−ε)\ell(p_i) \geqslant a(1-\varepsilon). Since p∈(1−ε)Kp \in (1-\varepsilon)K, we obtain ℓ(p)⩽a(1−ε)\ell(p) \leqslant a(1-\varepsilon). A contradiction.

Solution [in the language of Banach spaces] Equip Rd\mathbb{R}^d with the norm ∥⋅∥\|\cdot\|, whose unit ball is KK, call this Banach space VV. Choose an inclusion maximal set X⊂∂KX \subset \partial K whose pairwise distances are ≥ε\ge \varepsilon. Put L=convXL = \mathrm{conv}X.

The inclusion L⊆KL \subseteq K follows from the convexity of KK. If the inclusion (1−ε)K⊆L(1-\varepsilon)K \subseteq L fails then the Hahn–Banach theorem provides a unit linear functional λ∈V∗\lambda \in V^* such that max⁡{λ(L)}=max⁡{λX}≤1−ε\max\{\lambda(L)\} = \max\{\lambda X\} \le 1 - \varepsilon. Then the point x∈Kx \in K, where the maximum max⁡{λ(K)}=1\max\{\lambda(K)\} = 1 is attained (thanks to the finite dimension and compactness) is in ∂K\partial K and, as λ\lambda witnesses, at distance ≥ε\ge \varepsilon from all other points of LL and XX, contradicting the inclusion-maximality of XX.

The upper bound for the cardinality ∣X∣|X| is obtained by noting that the ε/2\varepsilon/2 balls centered at the points of XX are pairwise disjoint and lie in the difference of balls (1+ε/2)K∖(1−ε/2)K(1+\varepsilon/2)K \setminus (1-\varepsilon/2)K, whose volume is ((1+ε/2)d−(1−ε/2)d) volK\big((1+\varepsilon/2)^d - (1-\varepsilon/2)^d\big)\,\mathrm{vol}K, the volume of each of the small balls being εd/2dvolK\varepsilon^d/2^d\mathrm{vol}K. Hence

∣X∣≤(2+ε)d−(2−ε)dεd=O(ε1−d).|X| \le \frac{(2+\varepsilon)^d - (2-\varepsilon)^d}{\varepsilon^d} = O(\varepsilon^{1-d}).

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