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×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∈¯1,k2, i∈¯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)×(n⋅n(n+1)2+1) 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 n(n+1)2+1 columns for which the selected pairs have the same color, and since a column with n+1 points has 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