Maths Olympiad Prep

Library / /183 of 196

Geometry Difficulty 6.6 National Olympiad Prove it Soviet Union

Problem:
Can 1965 points be arranged inside a square with side 1515 so that any rectangle of unit area placed inside the square with sides parallel to its sides must contain at least one of the points?

Solution

Solution:
Yes. Place a grid of 900900 points in 3030 equally spaced rows and columns, so that each point is a distance 15/3115/31 from its nearest neighbours (or 15/3115/31 from the edge). This blocks all rectangles except those slimmer than 1/21/2. Those slimmer than 1/21/2 must have length at least 22, so we can block them with a smaller set of rows and columns containing more finely spaced points.

Label the rows 11-3030. In each of the 77 rows 33, 77, 1111, 1515, 1919, 2323, 2727 place an additional 3131 points, so that each of these rows has 6161 equally spaced points at a spacing of 15/6215/62. Similarly for the columns. So in total we are placing an additional 2×7×31=4342 \times 7 \times 31 = 434 points. Any rectangle of length >2>2 must encounter one of these rows (or columns) and hence must have width less than 1/41/4. This blocks any rectangle except those with width <1/4< 1 / 4.

In each of the 33 rows 77, 1515, 2323 place an additional 6262 points, so that each of these rows has 123123 equally spaced points at a spacing of 15/12415/124. Similarly for the columns. So in total we are placing an additional 2×3×62=3722 \times 3 \times 62 = 372 points. Any rectangle of length >4>4 must encounter one of these rows (or columns) and hence must have width less than 1/81/8. This blocks any rectangle except those with width <1/8< 1 / 8 and hence length >8>8.

In row 1515 place an additional 124124 points, so that it has a total of 247247 equally spaced points at a spacing of 15/24715/247. Similarly for column 1515. This requires an additional 248248 points. Any rectangle which can fit through these gaps has area at most 15×15/247<115 \times 15 / 247 < 1. So we have blocked all rectangles with area 11 or more and used 900+434+372+248=1954900 + 434 + 372 + 248 = 1954 points.

Ilan Mayer, who seems to solve these problems effortlessly, came up with a neater arrangement of points. He used narrowly spaced points along widely spaced diagonals: (k/15,k/15)(k/15, k/15) for k=1,2,,224k = 1,2,\ldots ,224; ((28n+k)/15,k/15)((28n+k)/15, k/15) for n=1,2,,7n = 1,2,\ldots ,7, k=1,2,,22428nk = 1,2,\ldots ,224 - 28n; (k/15,(28n+k)/15)(k/15, (28n + k)/15) for n=1,2,,7n = 1,2,\dots,7, k=1,2,,22428nk = 1,2,\dots,224 - 28n. The diagonals are spaced 28/1528/15 apart, so the biggest rectangle that can be fitted between two diagonals has sides 15/1515/15 less ε\varepsilon and 15/1515/15 less ε\varepsilon. For example, take the vertices as (14/15+ε,ε)(14 / 15 + \varepsilon,\varepsilon), (29/15ε,ε)(29 / 15 - \varepsilon,\varepsilon), (14/15+ε,15/15ε)(14 / 15 + \varepsilon, 15 / 15 - \varepsilon), (29/15ε,15/15ε)(29 / 15 - \varepsilon,15 / 15 - \varepsilon). If one allows a rectangle to touch points (in other words if one took the rectangles to exclude their boundaries) then this does not work - many 15×1/1515 \times 1 / 15 rectangles will fit. But one can add an additional point on each of the 1515 lines, keeping the points on each line evenly spaced. That blocks rectangles without boundary and still has only 18211821 points.

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.