Suppose 100 dots are arranged in a square 10 × 10 array, and each dot is colored red
or blue.
(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?
qweqwe
To answer part (a), we will use the Pigeonhole Principle. The Pigeonhole Principle states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with more than one pigeon.
In this problem, each dot represents a pigeon, and the colors red and blue represent the pigeonholes. We have 100 dots and only 2 colors, so by the Pigeonhole Principle, there must be at least one color with more than 50 dots.
Now let's consider the row and column pairs in the 10x10 array. Each pair consists of one row and one column. Since there are 10 rows and 10 columns, we have 100 row-column pairs. Again, applying the Pigeonhole Principle, we know that at least one row-column pair must contain the same color dots.
Let's assume that the color red appears in the same row-column pair. Now, we can select two different columns from this pair, let's call them column A and column B. In these two columns, we have the same color dots (red) in the same row. Now, consider any two distinct rows in these columns, let's call them row R1 and row R2. In these two rows, we have the same color dots (red) in the same column.
So, we have four red dots forming a rectangle: the dots in row R1 and columns A, and the dots in row R2 and column B. Therefore, we have proved that there must be either a set of four red dots that form a rectangle or a set of four blue dots that form a rectangle.
Now let's move on to part (b). The result does not remain true for smaller rectangular arrays of dots. In a 4x5 array, we can find a coloring that does not have a monochromatic rectangle. For example:
Red Blue Red Blue Red
Blue Red Blue Red Blue
Red Blue Red Blue Red
Blue Red Blue Red Blue
In this case, there is no set of four dots with the same color forming a rectangle.
However, in a 5x5 array, we can prove that there must be a monochromatic rectangle. By applying a similar argument as in part (a), we can show that at least one color must have three dots in the same row or three dots in the same column. By selecting two distinct rows or two distinct columns with three dots of the same color, we can find a monochromatic rectangle.
In a 4x6 array, there must also be a monochromatic rectangle. The proof is similar to the 5x5 case, and we can show that at least one color must have three dots in the same row or three dots in the same column. By selecting two distinct rows or two distinct columns with three dots of the same color, we can find a monochromatic rectangle.
In conclusion, for the original 10x10 array, there must always be a monochromatic rectangle. However, for smaller rectangular arrays, the existence of a monochromatic rectangle depends on the dimensions of the array.