A proof by Rutger M. Dijkstra and me.
Theorem. Consider the grid points, i.e. the points (x,y) with integer coordinates x and y, and let each grid point be painted with one of C distinct colours. For each X and Y, X distinct vertical grid lines and Y distinct horizontal grid lines exist such that their X.Y points of intersection have all the same colour.
Proof. Consider, for some k, the "strip" of points (x,y) with 0 ≤ x < k . In this strip the number of distinct possible colour patterns for a row is bounded (by Ck, to be precise). The number of rows in the strip being unbounded, at least one colour pattern occurs therefore in at least Y distinct rows. By choosing k larger than C.(X-1) we ensure that, in each and hence in this colour pattern, at least one colour occurs at least X times.
Acknowledgement. After having proved the theorem for X=Y=C=2 --that was the problem as originally posed-- my younger son, Rutger, removed during our discussion of the generalizations the last case analysis from the argument.
5671 AL NUENEN
23 November 1980
prof.dr. Edsger W. Dijkstra
Burroughs Research Fellow
Last revised on