Maths Olympiad Prep

Library / /24 of 70

Geometry Difficulty 8.1 Shortlist Prove it Romania

Let nn be an integer number greater than or equal to 22, and let KK be a closed convex set of area greater than or equal to nn, contained in the open square (0,n)×(0,n)(0, n) \times (0, n). Prove that KK contains some point of the integral lattice Z×Z\mathbb{Z} \times \mathbb{Z}.

Solution

Transform KK by a suitable two-step Steiner-Edler symmetrization. First, perform a horizontal translation of each slice K∩(R×y)K \cap (\mathbb{R} \times y) to place it symmetrically about the vertical line x=12x = \frac{1}{2}. It is readily checked that the image K′K' of KK under this transformation is a closed convex subset of the open square (1/2−n/2,1/2+n/2)×(0,n)(1/2 - n/2, 1/2 + n/2) \times (0, n), symmetrical about the vertical line x=1/2x = 1/2, and area K′=area K≥n\text{area } K' = \text{area } K \ge n. (Also, the transformation does not increase perimeters, a fact which will not be used in the sequel.) In addition, if KK contains no lattice point, so does K′K'. Indeed, if K′K' contained one such, say i×ji \times j, then the line y=jy = j would intersect K′K' in a closed line segment of length at least 11, so it would also intersect KK in a closed line segment of the same length; the latter, in turn, would contain at least one lattice point – a contradiction.

Next, apply the pattern vertically to further symmetrize K′K' about the horizontal line y=1/2y = 1/2. The resulting image K′′K'' is a closed convex subset of the open square (1/2−n/2,1/2+n/2)×(1/2−n/2,1/2+n/2)(1/2 - n/2, 1/2 + n/2) \times (1/2 - n/2, 1/2 + n/2), symmetrical about both lines x=1/2x = 1/2 and y=1/2y = 1/2 – whence centrally symmetric about the point 1/2×1/21/2 \times 1/2 – and of course area K′′=area K′=area K≥n\text{area } K'' = \text{area } K' = \text{area } K \ge n. Then if KK contains no lattice point, so does K′′K''.

Now let a=sup⁡{x:x×1/2∈K′′}a = \sup\{x : x \times 1/2 \in K''\} and b=sup⁡{y:1/2×y∈K′′}b = \sup\{y : 1/2 \times y \in K''\} and notice that a−1/2<n/2a - 1/2 < n/2 and b−1/2<n/2b - 1/2 < n/2 – both inequalities are strict, for K′′K'' is closed. Let further K0=K′′∩{x×y:x≥1/2 and y≥1/2}K_0 = K'' \cap \{x \times y : x \ge 1/2 \text{ and } y \ge 1/2\} be the upper right quarter of K′′K''. Clearly, K0K_0 is a closed convex set, and area K0=(area K′′)/4≥n/4\text{area } K_0 = (\text{area } K'')/4 \ge n/4. Suppose, if possible, that KK contains no lattice point. Then so does K0K_0, so by convexity it must lie below some line through the lattice point 1×11 \times 1 with a non-positive slope; that is,
K0⊂H={x×y:α(x−1)+β(y−1)<0}, K_0 \subset H = \{x \times y : \alpha(x - 1) + \beta(y - 1) < 0\},
where α\alpha and β\beta are non-negative real numbers such that α+β>0\alpha + \beta > 0. Notice that K0⊂H∩([1/2,a]×[1/2,b])K_0 \subset H \cap ([1/2, a] \times [1/2, b]), so max⁡{a,b}>3/2\max\{a, b\} > 3/2, for otherwise
1/2≤n/4≤area K0<area(H∩([1/2,3/2]×[1/2,3/2]))=1/2, 1/2 \le n/4 \le \text{area } K_0 < \text{area}(H \cap ([1/2, 3/2] \times [1/2, 3/2])) = 1/2,
which is a contradiction – the strict inequality above is due to the fact that K0K_0 is closed. Without loss of generality, assume that a>3/2a > 3/2, so β≠0\beta \ne 0 and
area K0<area(H∩([1/2,a]×[1/2,∞)))=12(a−12)(1−αβ(a−32))≤12(a−12); \begin{aligned} \text{area } K_0 < \text{area}(H \cap ([1/2, a] \times [1/2, \infty))) \\ &= \frac{1}{2} \left(a - \frac{1}{2}\right) \left(1 - \frac{\alpha}{\beta} \left(a - \frac{3}{2}\right)\right) \le \frac{1}{2} \left(a - \frac{1}{2}\right); \end{aligned}
as before, the inequality is strict because K0K_0 is closed. Finally, recall that a−1/2<n/2a - 1/2 < n/2 and area K0≥n/4\text{area } K_0 \ge n/4 to derive a contradiction.

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.