\section*{Problem 9}

Can 1965 points be arranged inside a square with side 15 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?


\section*{Solution}

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

Label the rows 1-30. In each of the 7 rows \(3,7,11,15,19,23,27\) place an additional 31 points, so that each of these rows has 61 equally spaced points at a spacing of \(15 / 62\). Similarly for the columns. So in total we are placing an additional 2.7.31 \(=434\) points. Any rectangle of length \(>2\) must encounter one of these rows (or columns) and hence must have width less than \(1 / 4\). This blocks any rectangle except those with width \(4\) must encounter one of these rows (or columns) and hence must have width less than \(1 / 8\). This blocks any rectangle except those with width \(8\).

In row 15 place an additional 124 points, so that it has a total of 247 equally spaced points at a spacing of 15/247. Similarly for column 15. This requires an additional 248 points. Any rectangle which can fit through these gaps has area at most 15 x \(15 / 247<1\). So we have blocked all rectangles with area 1 or more and used \(900+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: \((\mathrm{k} / 15\), \(\mathrm{k} / 15)\) for \(\mathrm{k}=1,2, \ldots, 224 ;((28 * \mathrm{n}+\mathrm{k}) / 15, \mathrm{k} / 15)\) for \(\mathrm{n}=1,2, \ldots, 7, \mathrm{k}=1,2, \ldots, 224-28 * \mathrm{n} ;(\mathrm{k} / 15\),
\((28 * \mathrm{n}+\mathrm{k}) / 15)\) for \(\mathrm{n}=1,2, \ldots, 7, \mathrm{k}=1,2, \ldots, 224-28 * \mathrm{n}\). The diagonals are spaced 28/15 apart, so the biggest rectangle that can be fitted between two diagonals has sides \(15 / 15\) less epsilon and 15/15 less epsilon. For example, take the vertices as (14/15 + e, e), (29/15 - e, e), (14/15 + e, 15/15 - e), (29/15 - e, 15/15 - e). 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 \times 1 / 15\) rectangles will fit. But one can add an additional point on each of the 15 lines, keeping the points on each line evenly spaced. That blocks rectangles without boundary and still has only 1821 points.

