posted by Tyler on .
Suppose 100 dots are arranged in a square 10 × 10 array, and each dot is colored red
(a) Prove that this array must contain a “monochromatic” rectangle. That is, no matter
how the red and blue colors are assigned, there must be either a set of four red dots that
form a rectangle or else a set of four blue dots that form a rectangle.
[Don’t consider colors of the dots inside that rectangle. Just the four corner points.
Use only those rectangles having horizontal and vertical sides. ]
(b) Does this result remain true for smaller rectangular arrays of dots?
To begin, find a 4 × 5 array that admits no monochromatic rectangle.
Must a monochromatic rectangle exist in a 5 × 5 array? In a 4 × 6 array?