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 4²⁸⁹ 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).