bonanova Posted March 28, 2015 Report Share Posted March 28, 2015 This problem is adapted from a problem given in the 1976 USA Mathematics Olympiad. Prove or disprove: Any 2-colored plane contains an m x n monochromatic rectangle (4 vertices of same color) such that m = 1 or 2, and n <= 6. Quote Link to comment Share on other sites More sharing options...

0 Rainman Posted March 29, 2015 Report Share Posted March 29, 2015 Consider coloring the corners and intersections in this figure, either red or blue. Suppose it can be done so that no monochromatic rectangle exists. Let (a,b) denote column a, row b, according to the numbers in the figure. If any column has all three points of the same color, change one of them to the other color. For example, if (3,0), (3,1), and (3,2) are all red, change one of them into blue. This change can never result in a new monochromatic rectangle appearing, so we still have no monochromatic rectangles. Repeat this process until all columns have both colors. There are six possible coloring patterns for a column: RRB, RBR, RBB, BBR, BRB, and BRR. However, there are seven columns, so two of them must have the same pattern. This will yield a monochromatic rectangle. For example, if columns 2 and 5 are both RRB, then taking the two red points from each column yields the rectangle (2,0),(2,1),(5,1),(5,0) which is all red and is of size 1x3. So there will always be a monochromatic rectangle in this figure. Finally note that any monochromatic rectangle from this figure is of requested size. Quote Link to comment Share on other sites More sharing options...

## Question

## bonanova

This problem is adapted from a problem given in the 1976 USA Mathematics Olympiad.

Prove or disprove:Any 2-colored plane contains an

monochromatic rectangle (4 vertices of same color) such thatmxn= 1 or 2, andm<= 6.n## Link to comment

## Share on other sites

## 1 answer to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.