Mathematics
Mathematics
Problem
A lattice point is a point that has integer coordinates. Suppose each lattice point in the cartesian plane is colored either red or blue. Let be a rectangle whose sides are parallel to the axes and corners are lattice points. (That is contains three lattice points on one side and seven on the other). A monochromatic rectangle is a rectangle whose sides are parallel to the axes and whose four corners are lattice points having same color. Prove that must contain a monochromatic rectangle.Intuitive explanation
This problem hinges on the pigeonhole principle applied to rows and columns. The key insight is that with only two colors and enough rows, two rows must have matching color patterns in at least two columns—and those matching patterns guarantee a monochromatic rectangle. Think of each row as a sequence of colored points: if you have three rows and only two colors, by pigeonhole, two rows must agree on the colors in at least two of the same columns, giving you four corners of the same color.
Intuitive explanation
This problem hinges on the pigeonhole principle applied to rows and columns. The key insight is that with only two colors and enough rows, two rows must have matching color patterns in at least two columns—and those matching patterns guarantee a monochromatic rectangle. Think of each row as a sequence of colored points: if you have three rows and only two colors, by pigeonhole, two rows must agree on the colors in at least two of the same columns, giving you four corners of the same color.