The 17x17 challenge: worth $289.00. I am not kidding.
Definition: The n x m grid is
ccolorable
if there is a way to ccolor 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 17x17 challenge: The first person to email me
a 4coloring of 17x17 in LaTeX will win $289.00.
(I have a LaTeX template below.)
Why 17x17? Are there other grids I care about?
We (We=Stephen Fenner and Charles Glover and Semmy Purewal) will soon be submitting a
PAPER
(see
TALK for
a superset of the slidetalk I've given on this paper)
on coloring grids.
Here are the results and comments:

For all c there is a finite set of grids
a_{1}xb_{1}, ...,
a_{k}xb_{k} such that
a grid is ccolorable iff it does not contain any of the
a_{i}xb_{i}
(n x m contains a x b if a &le n and b &le m).
We call this set of grids OBS_{c}
(OBS for Obstruction Set).

OBS_{2} = {3x7, 5x5, 7x3}

OBS_{3} = {19x4, 16x5, 13x7, 11x10, 10x11, 7x13, 5x16, 4x19}

OBS_{4} contains
41x5, 31x6, 29x7, 25x9, 9x25, 7x29, 6x31, 5x41

Exactly one of the following sets is in OBS_{4}: 23x10, 22x10, 21x10.

Exactly one of the following sets is in OBS_{4}: 22x11, 21x11, 21x10.

Exactly one of the following sets is in OBS_{4}: 22x11, 22x10, 21x10.

Exactly one of the following sets is in OBS_{4}: 21x13, 21x12, 21x11, 21x10.

Exactly one of the following sets is in OBS_{4}: 19x17, 18x17, 17x17.

If 19x17 is in OBS_{4} then 18x18 might be in OBS_{4} .
If 19x17 is not in OBS_{4} then 18x18 is not in OBS_{4} .

A chart of what we do and do not know about 4colorings of grids is
here.

A Rectangle Free Subset of a x b is a subset of a x b that has no rectangles.
Note that if a x b is 4colorable then there must be a rectangle free subset of a x b of
size Ceil(ab/4). We actually have a rectangle free subset of 17x17 of size Ceil(289/4)+1.
Hence we think it is 4colorable.
For the rectanglefree subset see
here.
For the original LaTeX (which you can use for a template when you submit yours)
see
here.
THIS IS WHY I AM FOCUSING ON 17x17 BECAUSE I REALLY REALLY
THINK THAT IT IS 4COLORABLE. I could still be wrong.
What if 17x17 is not 4colorable?
Then nobody will collect the $289.00. Even so, if you find this out I would
very much like to hear about it. I don't want to offer money for that
since if your proof is a computer proof that I can't verify then its not clear
how I can verify it. I also don't want to offer money for a
reasonable proof since this may lead to having the Supreme Court
decide what is a reasonable proof.
Can I get a paper out of this?
FACT: If you get me the coloring and want to use it in a publication then
that is fine.
OPINION: It would not be worth publishing unless you get all of OBS
_{4}.
See next question.
What do you hope to get out of this?
My most optimistic scenario is that someone solves the 17x17 problem and
that the math or software that they use can be used to crack the entire OBS
_{4} problem.
If this happens and my paper has not been accepted yet then we could talk about a merge,
though this is tentative on both ends.
Has there been any work done on this problem that is not in your paper?
A Rutgers grad student named Beth Kupkin has worked on the
problem: here.

A high school student (member of my VDW gang) Rohan Puttagunta
has obtained a 4coloring of 17x17 EXCEPT for one square:
here.

SATsolvers and IPprograms have been used but have not worked however,
I don't think they were tried that seriously.

Here are some thoughts I have had on the problem lately:
here.

There is a paper on the 3d version of this problem:
here.
Is Lance involved with this at all?
When I gave a talk on grid colorings at Northwestern, Lance fell asleep.

Posted By GASARCH to
Computational Complexity at 11/30/2009 12:14:00 PM