A rectangle of one colour is unavoidable

Question

Every point with whole-number coordinates in the plane is coloured either red or blue, in any pattern whatsoever, as chaotic as you like.

Prove that there is always a rectangle, with sides parallel to the axes, whose four corner points all have the same colour. How small a region of the grid is guaranteed to contain one?

Accepted Answer

A one-colour rectangle always exists, and you can find one inside any 3-row by 9-column block. Patterns in a column. Take any three rows and look at a column: its three points form a colour pattern such as red-red-blue. With two colours and three positions there are 2 × 2 × 2 = 8 possible patterns. Nine columns. Look at 9 consecutive columns across those three rows. Nine columns, only 8 patterns: by pigeonhole, two columns have the same pattern. Two points of one colour. Any pattern of three points in two colours has at least two points of the same colour (three points cannot all differ). Say…

A rectangle of one colour is unavoidable

Your answer

Discussion

Learn the concepts

Related questions