Problem of the Week

This problem was provided by Dr. Tony Bedenikovic. No matter how the vertices of the 3 by 7 lattice on the left are colored with the colors black and red, is it always possible to find a rectangle all four of whose corners are of the same color?   Is the same true of a 3 by 6 lattice? Be sure to explain your answer. (Note: The vertices of the rectangle cannot all lie in the same row or column. It wouldn't be a rectangle then, would it?) For a more challenging problem: Given a positive integer n is it always possible to find a positive integer m so that no matter how the vertices of an n by m lattice are colored with two colors, there is always a rectangle all four of whose corners are of the same color? If so, can you give an upper bound for the smallest value of m for a given n?

You are visitor number  10062 to this page.
ã2001 Alberto L. Delgado