17×17 4-coloring with no monochromatic rectangles

Quick, what’s special about the following picture?

As just announced by Bill Gasarch, this is a 17 \times 17 grid which has been four-colored (that is, each point in the grid has been assigned one of four colors) in such a way that there are no monochromatic rectangles, that is, no four grid points forming the corners of an axis-aligned rectangle are all of the same color. For example, if we change the top-left grid point to red, we can see several monochromatic rectangles pop up:

Or here’s another version where I randomly picked a grid point in the middle, changed its color, and sure enough, more monochromatic rectangles result:

As you can try verifying for yourself (and as I also verified using a computer program), there are no such monochromatic rectangles in the four-coloring at the top of this post! (If you want to play with the four-coloring yourself, here it is in a simple data format.)

For several years no one knew if this was possible, and Bill had offered a prize of $289 (that’s \$17^2, of course) to anyone who could find such a four-coloring. The prize will be collected by Bernd Steinbach and Christian Posthoff—you can find more details in Bill’s post. No one yet knows exactly how they found their four-coloring, but apparently they will be presenting a paper about it in May. I’ll try to write more about it then (if I understand it at all)!

If you’re interested in reading more about the history and math behind this problem (and to get some intuition for why it is difficult), take a look at these posts by Brian Hayes on his blog, bit-player: The 17×17 challenge and 17 x 17: A nonprogress report. I also remember seeing Here’s a fun interactive applet where you can play around with the problem, created by Martin Schweitzer.

About these ads
This entry was posted in open problems, pattern, people, pictures and tagged , , , , , . Bookmark the permalink.

5 Responses to 17×17 4-coloring with no monochromatic rectangles

  1. Pingback: A Page For Folks Who Like Math « GFBrandenburg's Blog

  2. Pingback: How Deep is Your Coloring? « Gödel’s Lost Letter and P=NP

  3. martin says:

    Hi, I think the applet you were looking for is this one: http://www.martinschweitzer.com/squaregame.html


  4. Pingback: Puzzleclopedia › Rectángulos monocromáticos, no! › Enigmas y juegos de ingenio

Comments are closed.