Easy to state, hard to solve problem

One of the authors of the blog "Computational Complexity," William Gasarch, posted a computational challenge on November 30 and he is offering $17*17 = $289 if someone comes up with a solution. I like this problem because it is easy to state and hard to solve.

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.

For some good pictures of the definition see the blog: this blog posting.

Conjecture: the 17x17 grid is 4-colorable. (worth $289 if you prove this conjecture, worth nothing if you disprove it)

Theorem: the nxn grids for 1<=n<=16 are 4 colorable

Theorem: the nxn grids for n>=19 are not 4 colorable

William Gasarch is offering the $289 because "I REALLY REALLY THINK THAT IT IS 4-COLORABLE. I could still be wrong."

Here is a possible way to get students started on this problem:
1. Show that the 4x5 grid is 2 colorable. Here are some examples of the 2x2, 3x3, 4x4 grids.



Notice that once you have a c-coloring of an nxm grid then any subgrid of this gives a coloring of a smaller grid. Show that the 5x5 grid is not 2 colorable (hmmm, there are only 2^24 ways of coloring a 5x5 grid with white in the upper left corner).

2. Some extensions: How many ways are there of coloring the 2x2 grid with 2 colors? with 3 colors? with 4 colors? up to rotation and other symmetry? up to switching colors? Extend this to the 3x3. Can you extend it to the 4x4?

3. Find the mistake in the 17x17 grid below:



Hint: This 17x17 coloring was taken from here so this will give away where the mistake is.

4. Write a function (pick your favorite computer language) that tests if a c-coloring of an nxm grid is valid.

Any other ideas?