Problem:
Can 1965 points be arranged inside a square with side 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 points in equally spaced rows and columns, so that each point is a distance from its nearest neighbours (or from the edge). This blocks all rectangles except those slimmer than . Those slimmer than must have length at least , so we can block them with a smaller set of rows and columns containing more finely spaced points.
Label the rows -. In each of the rows , , , , , , place an additional points, so that each of these rows has equally spaced points at a spacing of . Similarly for the columns. So in total we are placing an additional points. Any rectangle of length must encounter one of these rows (or columns) and hence must have width less than . This blocks any rectangle except those with width .
In each of the rows , , place an additional points, so that each of these rows has equally spaced points at a spacing of . Similarly for the columns. So in total we are placing an additional points. Any rectangle of length must encounter one of these rows (or columns) and hence must have width less than . This blocks any rectangle except those with width and hence length .
In row place an additional points, so that it has a total of equally spaced points at a spacing of . Similarly for column . This requires an additional points. Any rectangle which can fit through these gaps has area at most . So we have blocked all rectangles with area or more and used 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: for ; for , ; for , . The diagonals are spaced apart, so the biggest rectangle that can be fitted between two diagonals has sides less and less . For example, take the vertices as , , , . 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 rectangles will fit. But one can add an additional point on each of the lines, keeping the points on each line evenly spaced. That blocks rectangles without boundary and still has only points.