The 17×17 challenge: worth $289.00. I am not kidding.
Definition: The n x m grid is c-colorable if there is a way to c-color the vertices of the n x m grid so that there is no rectangle with all four corners the same color. (The rectangles I care about have the sides parallel to the x and y axis.)
The 17×17 challenge: The first person to email me a 4-coloring of 17×17 in LaTeX will win $289.00. (I have a LaTeX template below.)
This challenge was started a few months ago (November 30, 2009) and I think that no solution has been founded yet. A straighforward adaptation of this exercice shows that a 19×19 cannot be colored with only 4 colors while many examples of 16×16 grids have been exhibited: the question thus only remains for size 17 and 18. One can read about this challenge at quite a few places
- William Gassarch blog: it all started over there,
- an excellent article in bit-player blog: nice pictures, link to relevant articles, some background on the problem, some ways of attacking the problem,
- Chris Taylor computes the expected number of rectangles in the 17×17 grid, and discuss some possible attacks,
- Andre Roberge also mentioned the challenge.
Quite a lot of people have implemented their ideas and very promising results have been obtained. Nevertheless, perhaps surprisingly, there is no place where one can find a clear summary of all the failed attempts, with a brief description of the method used. Here is an attempt to remedy to this situation:
|9||Alex Thiery||Parallel Tempering
|16||Alexandros Marinos||tree search,
|26||Thomas Levy||Genetic Algorithms||
To share your results and method, send an email at alek.thiery.blog(-AT-)gmail.com. It could be interesting to have a brief description of the approach used, or a link towards something related.