Maths Olympiad Prep

Library / /25 of 52

Geometry Difficulty 8.1 Shortlist Prove it Romania

The infinite grid of lines of the form R×{m}\mathbb{R} \times \{m\} and {m}×R\{m\} \times \mathbb{R}, where mm runs through all integers, subdivide the Euclidean plane R×R\mathbb{R} \times \mathbb{R} into 1×11 \times 1 cells. Let SS be the set-theoretic union of a finite number of such cells, and let aa be a positive real number less than or equal to 1/41/4. Show that SS can be covered by a finite number of squares satisfying the following three conditions simultaneously:
(1) Each square in the cover is an array of 1×11 \times 1 cells;
(2) The squares in the cover have pairwise disjoint interiors; and
(3) For each square QQ in the cover, the ratio of the area of SQS \cap Q to the area of QQ is at least aa and at most aa1/22a\lfloor a^{-1/2} \rfloor^2.

Solution

Let n=a1/2n = \lfloor a^{-1/2} \rfloor and notice that n2n \ge 2, since a1/4a \le 1/4. Choose a large enough integer kk to cover SS by an nk×nkn^k \times n^k array QQ so that the ratio of the area of SS to the area of QQ is at most aa. Subdivide QQ into n2n^2 congruent square subarrays QQ', and notice that the ratio of the area of SQS \cap Q' to the area of QQ' does not exceed an2an^2. Remove the QQ' whose interiors are disjoint from SS. Continuing, each of the remaining QQ' for which (area(SQ))/(areaQ)<a(\text{area}(S \cap Q'))/(\text{area} Q') < a is then subdivided into n2n^2 congruent square subarrays, and so on and so forth all the way down, to stop at stage max{j:an2(kj)>1}k2\max\{j: an^2(k-j) > 1\} \le k-2 or earlier; this is because at stage jj, for each square Q(j)Q^{(j)} in the subdivision, whose interior is not disjoint from SS, the ratio of the area of SQ(j)S \cap Q^{(j)} to the area of Q(j)Q^{(j)} is at least n2(jk)n^{2(j-k)}, and of these Q(j)Q^{(j)} only those for which this ratio is less than aa are subject to further subdivision.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.