Friday, December 25, 2009

The 17x17 challenge

In a recent blog post, William Gasarch issued a challenge: find a 17x17 four-colour grid for which there are no rectangles with 4 corners of the same colour.  If you can do this, Gasarch will give you $289.  For a more detailed explanation, you can either read Gasarch's post, or this post which contains a slightly friendlier explanation of the problem.

This problem, which is fairly easy to state, is extremely hard to solve as the number of possible grid configurations is 4289 which is a number much too large to solve by random searches or by naive methods.  As can be seen from the comments of the posts mentioned above, many people have devoted a lot of cpu cycles in an attempt to find a solution, but with no success.  Like others, I have tried to write programs to solve it ... but with no luck.  In a future post, I may write about the various strategies I have implemented in Python in an attempt to solve this problem.

Gasarch mentions that it is not known if a solution can be found for a 17x18 four-colour grid or even an 18x18 grid or a 17x19 one.  (Note that because of symmetry, an MxN solution can be rotated to give an NxM solution.)  While the number of configurations is large, the larger the grid is, I believe I have found a proof demonstrating that no solution can be found for a 17x18 grid.  This proof builds on the work of Elizabeth Kupin who has found the largest "colour class" i.e. the number of single-colour points on a 17x17 grid which is rectangle-free.  A generic solution found by Kupin is reproduced below:



Consider a 17x18 grid (17 rows and 18 columns).  Such a grid has 306 points.  Using the pigeonhole principle, one can easily show that, for any colouring, at least one colour must cover 77 points.  (Indeed, the most symmetric colouring would be 77, 77, 76, 76.)  Also, if a 17x18 rectangle-free solution exist, it must contain a 17x17 rectangle-free subset, which we take to be the above solution (other solutions for the 17x17 grid can be derived from this one using interchanges of rows and/or columns).

Let us attempt to add points in an additional column. First, we can try to add points in a row with 4 elements.  Without loss of generality, we can take this row to be the first one (row A).  Once we do this, we can not add any more points to row 3-17 without creating a rectangle.  The only row to which we can add a point is the second (row B) bringing the total number of points to 76 - one short of what we need.

Perhaps we can first remove a point from the 17x17 solution and then add a new column.  There are three cases we must consider: 1) that of a point belonging to a row with 5 points and a column with 5 points; 2) that of a point belonging to a row with 5 points and a column with 4 points; 3) that of a point belonging to a row with 4 points and a column with 5 points.

Case 1) Without loss of generality, let us move the point on row F in the first column to a new additional column, keeping the number of points at 74.  It is easy to show that the only rows to which we can then add an additional point without creating a rectangle are rows A, C, D, E. Once we add such a point (say on row A), we can no longer add a point on any of the remaining rows (C, D, E) without creating a rectangle.

Case 2) Without loss of generality, let us move the left-most point on row Q to a new column.  The only row to which we can then add a point in this new column is row A, bringing the total to 75.  We can't add another point without creating a rectangle.

Case 3) Again, without loss of generality, let us remove the top-left element (A) and move it to a new column added to the above solution.  We can add one more point, bringing the total to 75, to that new column (in row B) without creating a rectangle; any other addition of a point on that new column will result in a rectangle.


This concludes the sketch of the proof. 

UPDATE: Instead of adding a column, we can add a row (R) with 3 points located in the 9th, 12th and 17th column, bringing the total to 77 points and keeping the grid rectangle-free.  So the 17x18 case is still open... but I can't see how one could add a row with an extra 4 points to build a "single-colour" rectangle-free 17x19 grid.  (However, I won't venture again to say it is a proof until I have looked at all cases exhaustively.)

Note that construction of solutions for a 17x17 grid such as those found by Kupin, even for a single colours, can possibly be used to restrict the search space for the more general problem and help find a solution.  Unfortunately, no one has been able to do this (yet).

2 comments:

EOL (Eric O LEBIGOT) said...

Interesting discussion! You had me stop everything else I was doing, when I started reading this post! Thank you for sharing. :)

JohnPaul Adamovsky said...

I've successfully enumerated every possible perfect 10x10 3-Coloring, using a novel and dazzling algorithm, as a Proof-Of-Concept for solving the 17x17 problem. In response to my proposal, requiring a 24 thread machine, William Gasarch said it was long, so he wasn't interested in reading it.

When my work is long, it can be more accurately described as:

RIGOROUS, EXACT, DETAILED, CONSISTENT, THOROUGH, CONSCIENTIOUS,
METICULOUS, COMPREHENSIVE, PAINSTAKING, RELENTLESS, PROVEN, UNCOMPROMISING, DILIGENT, SYSTEMATIC, DEDICATED, CONVICTION, VIGILANT, METHODICAL, TESTED, DISCIPLINED, ALL THE VERY BEST, PERFECT.

In one word: SCIENTIFIC.

I will now give you a link to the entire email I send to William Gasarch with my proposal, so you can judge for yourself, if the program, I took it upon myself to write for him, is the most powerful algorithm ever coded to solve this class of problem.

My program finds the first perfect coloring is seconds, and enumerates all of them, over night.

Proposal-Email.zip

Explain this:

A Perfect 10x10 3-Coloring -

0|000|111|222|
-?---?---?---?-
0|211|221|020|
0|212|012|101|
0|221|100|211|
-?---?---?---?-
1|012|120|002|
1|022|201|110|
1|101|212|200|
-?---?---?---?-
2|102|001|021|
2|120|102|102|
2|110|020|210|
-?---?---?---?-

Each row-col has a (3, 3, 4) color distribution, but the square as a whole, has the following color spread:

34 0's
34 1's
32 2's

Pick up on this pattern: Of the 2 colors with a 34 count, each (4-count) row intersects with a (4-count) col of the same color.

From the top-left to bottom right, there are 9 enumerated sets, which must be internally rectangle free, and must not rectangle with the static row and column. Further, set 0, 4, and 8 are limited to an in-order "Permutation 0" configuration.

Bottom line, 864 configurations are found using the above template, and 864 = 3^3x2^5, there are many less unique configurations.

You got valid color-swaps, valid column shuffles, valid (4-4 Intersect) flips, and row-col exchange. Testing for uniqueness is not a trivial exercise, so I am leaving for each, his own.

I consider myself something of an Oracle-Machine-Automaton, so I need Gasarch for NOTHING.

I will use the Proof-Of-Concept template to solve the 17x17 problem in my own time, and share the solution with Gasarch, NEVER.


All the very best,

JohnPaul Adamovsky

PS - Gasarch, you have been weighed, you have been measured, and you have been found wanting.

PPS - If you want to know who I am, look me up on Google, you genius. Then READ.

PPPS - You are now playing "THE MANS GAME". Investigate and produce something of value, or finish crumbling.