Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
bonanova

Monochromatic rectangle on a two-colored plane

Question

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

  1. m = 1 or 2, and
  2. n <= 6.

Share this post


Link to post
Share on other sites

1 answer to this question

Recommended Posts

  • 0

post-52528-0-70226200-1427586901_thumb.p

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.

Share this post


Link to post
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...