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 Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
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.