Maths Olympiad Prep

Library / /9 of 18

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 KK' of KK under this transformation is a closed convex subset of the open square (1/2n/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 Kn\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 KK'. Indeed, if KK' contained one such, say i×ji \times j, then the line y=jy = j would intersect KK' 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 KK' about the horizontal line y=1/2y = 1/2. The resulting image KK'' is a closed convex subset of the open square (1/2n/2,1/2+n/2)×(1/2n/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 Kn\text{area } K'' = \text{area } K' = \text{area } K \ge n. Then if KK contains no lattice point, so does KK''.

Now let a=sup{x:x×1/2K}a = \sup\{x : x \times 1/2 \in K''\} and b=sup{y:1/2×yK}b = \sup\{y : 1/2 \times y \in K''\} and notice that a1/2<n/2a - 1/2 < n/2 and b1/2<n/2b - 1/2 < n/2 – both inequalities are strict, for KK'' is closed. Let further K0=K{x×y:x1/2 and y1/2}K_0 = K'' \cap \{x \times y : x \ge 1/2 \text{ and } y \ge 1/2\} be the upper right quarter of KK''. Clearly, K0K_0 is a closed convex set, and area K0=(area K)/4n/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,
K0H={x×y:α(x1)+β(y1)<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 K0H([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/2n/4area 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(a12)(1αβ(a32))12(a12); \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 a1/2<n/2a - 1/2 < n/2 and area K0n/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 and solution reproduced as published; topic and difficulty added by this site.