THE 17x17 PROBLEM HAS BEEN SOLVED!!!!!
On Nov 30, 2009 I posted here the following challenge:
If someone emails me a 4-coloring of 17x17 with no monochromatic rectangles then I will give you $289.00Bernd Steinbach (Institute of Computer Science, Freiberg University of Mining and Technology, Freiberg (Saxony), Germany) and Christian Posthoff (retired from Department of Computing and Information Technology, The University of the West Indies, Trinidad and Tobago, but now in Germany) have found a 4-coloring of 17x17 without monochromatic rectangles!! The coloring is here. I have verified it (actually I asked Daniel Apon and Jim Purtilo to separately verify it, and they have. Also, Semmy Purewal and Brian Hayes did later.) The methods Steinbach and Posthoff used to obtain the coloring will appear in their paper
Most Complex Four-Colored Rectangle-free Grids - Solution of an Open Multiple-Valued Problem (ISMVL 2012. ISMVL stands for International Symposia on Multiple-Valued Logic). They will present this paper on May 14, 2012 during session B1 of ISMVL in Victoria, Canada.)Once the paper appears there will be a post (with their help, perhaps guest posted by them) on the techniques they used.
- Some very serious people had worked very hard on this. I actually began thinking that 17x17 is NOT 4-colorable.
- CONGRATULATIONS to Bernd Steinbach and Christian Posthoff!
- They also found a 4-coloring of 18x18.
- The only grid that we do not know if it is 4-colorable is 12x21. This is still open and you are URGED to work on it. Sorry, no cash on this one. Do it for the glory!
- If you are going to ISMVL 2012 then find Bernd and Christian and say hello. More important, talk to them about there work. (I won't be there alas.)
- The reason I thought that 17x17 was 4-colorable is that there is a rectangle free subset of size 74, so I assumed that one of the colors would appear 74 times. WRONG- The max number of times a color appears is 73.
- I thought that each color would appear 4 or 5 times in each row and column. WRONG- some appear 3 times in a row or column.
- I am DELIGHTED to pay out the $289.00.
- I asked them if they did it for the money (which I doubted). No, but the money made them more aware of the problem.
- How did they do it? I do not know, but I am looking forward to reading their paper in May when it is available and blogging about it.