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.