Let $ n $ and $ r $ be positive integers and $ A $ be a set of lattice points in the plane such that any open disc of radius $ r $ contains a point of $ A $. Show that for any coloring of the points of $ A $ in $ n $ colors there exists four points of the same color which are the vertices of a rectangle.
Problem
Source: Romanian IMO Team Selection Test TST 1996, problem 10
Tags: geometry, rectangle, combinatorics proposed, combinatorics
28.09.2005 20:32
Here, a row will be a horizontal line passing through a lattice point, while a column will be a vertical line passing through a lattice point. We can rephrase the given condition as follows: there is some $k$ s.t. for every $k$ rows and every $k$ columns, there is at least one point of $A$ among their intersections. Partition the lattice into $k\times k$ squares, and regard each such square as a lattice point in another, coarser lattice. To each such square associate a point of $A$ among the intersections of the $k$ rows and $k$ columns, and give the square the color $(u,i),\ u\in\overline{1,k^2},\ i\in\overline{1,n}$, where $u$ represents the position of the chosen point of $A$, while $i$ represents the color that we assign to this point. Clearly, a monochromatic rectangle ("rectangle" means "rectangle with sides parallel to the axes") in this new lattice corresponds to a monochromatic rectangle in the old lattice, so all we have to prove is this: Given a coloring with $n$ colors of the points of the lattice, we can find a monochromatic rectangle. Consider an $(n+1)\times\left(n\cdot\dfrac{n(n+1)}2+1\right)$ rectangle made up of points in this lattice. Each column contains a pair of points with the same color, so select such a pair for each column. There must be $\dfrac{n(n+1)}2+1$ columns for which the selected pairs have the same color, and since a column with $n+1$ points has $\dfrac{n(n+1)}2$ pairs of points, there must be two columns having the same selected pair with the same color. The four points in the two mentioned pairs are the vertices of a monochromatic rectangle.
03.09.2024 08:02
Nice solution.Instructively