Quick, what’s special about the following picture?

As just announced by Bill Gasarch, this is a 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 , 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.

39.953605
-75.213937

##
About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

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

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

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

Regards,

Martin

Yes, that’s the one, thanks!

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