William Gasarch is not the Clay Mathematics Institute. He isn’t paying a million bucks for proofs of famous conjectures. But Gasarch is putting up 172 of his own dollars for the solution to an intriguing little stumper. And the prize problem appears to be somewhat easier than the Riemann hypothesis or the P=NP question. (Unless it’s impossible!)
Gasarch sets forth his prize challenge in a blog post, with further background in a paper and in the slides from a talk. All of those works are well worth reading, but for those who don’t want to chase down the references, here’s the gist. Our mission, should we choose to accept it, is to color the nodes of an n-by-m grid, using only a specified number of colors, and observing a particular constraint: Nowhere in the grid may the four corners of a rectangle all have the same color. (Only rectangles with sides parallel to the x and y axes are considered.) For example, here is a four-colored 15-by-15 grid that satisfies the no-monochromatic-rectangles constraint:
In this array of dots there are \( {15 \choose 2}^2=11025\) distinct rectangles. If you care to check through all of them one by one, you’ll find that in no case do all four corners have the same color. In contrast, here is a 16-by-16 grid that is almost but not quite rectangle-free:
Gasarch offers his $289 bounty for any four-colored 17-by-17 grid with no monochromatic rectangles. Why is that grid of particular interest? It’s a border case. Among square grids, all those up through 16-by-16 have been shown to have rectangle-free four-colorings. For the 18-by-18 grid and all larger squares, rectangle-free four-coloring has been proved impossible. For squares larger than 18-by-18, four-coloring has been proved impossible. The status of the 17-by-17 and 18-by-18 grids remains unsettled, but Gasarch believes that both are four-colorable.
Gasarch has much more to say about the mathematics behind this problem. Here I would like to muse on some computational aspects of searching for a 17-by-17 four-coloring.
To state the obvious first, this is not a problem we can expect to solve by exhaustive enumeration. There are 4289 possible colorings of the grid. Casting out symmetries brings that down only to 2 × 4287. There’s not world enough or time for checking them all.
Testing grids at random is also hopeless in the 17-by-17 case. This nonstrategy actually works quite well for small grids. For example, you can readily find a four-coloring of an 8-by-8 grid just by generating a few hundred thousand random colorings. But the method fails for larger grids because the proportion of all colorings that are rectangle-free falls steeply with grid size. (Consider the 2-by-2 grid: There are 256 four-colorings, and all but four of them are rectangle-free.)
To make any progress toward the 17-by-17 case, we’ll have to do at least a little thinking, rather than expecting the computer to do all the work. Here’s one idea that’s very easy to implement: Find a monochrome rectangle somewhere within the grid, change the color of one of its corners, and repeat until you can’t find any more rectangles. This algorithm works reasonably well for grids up to about 12-by-12, but then it runs out of steam. On larger grids, changing the color of a node to eliminate one rectangle is likely to create another rectangle elsewhere (or several more of them). As a result, the system merely takes a random walk, with trendless fluctuations in the number of rectangles at any given moment. You discover a rectangle-free coloring only if the walk happens to stumble on the zero point.
I found the 15-by-15 four-coloring shown above with an algorithm that’s a little more effective even thought it’s no more sophisticated than the corner-twiddling method. The program repeatedly chooses a node at random and tries assigning it all four possible colors, tallying up the number of rectangles for each color choice. Some color or set of colors must minimize the rectangle count; from among these optimal colors the program chooses one at random and sets the node to that color before repeating the loop. This is a “greedy” method: At each step the number of rectangles can decrease or remain constant but can never increase. Greedy methods are notorious for getting stuck in local optima that are inferior to the global optimum. Maybe that’s what happens to my program when I try it on 16-by-16 and 17-by-17 grids. Or maybe the search space is just too large. In any case, when I woke up this morning and checked the results of an overnight run, I did not find a rectangle-free four-colored 17-by-17 grid awaiting me.
Of course I really didn’t have to do any algorithm analysis at all to know that I wasn’t going to win $289 and eternal fame with a day or two of idle hacking. If the problem were that easy, Gasarch and his students would have solved it for themselves long ago.
In spite of these various failures and frustrations, the grid-coloring problem still looks tantalizingly solvable. If a four-coloring of the Gasarch grid exists, it seems like we should be able to find it by some practical computation.
There are certainly lots of approaches more powerful than the blind dart game I’ve been playing. For example, if local optima are the major impediment, some variation on simulated annealing might help.
A more radical possibility is to try to construct an instance rather than merely search for it. If we assume that the four colors are represented as evenly as possible, then the 17-by-17 grid must have 72 nodes in each of three colors and 73 nodes in the fourth color. Starting from a blank grid, it’s easy to mark off 73 nodes in a single color without creating a forbidden rectangle. Adding 72 nodes of a second color is only a little harder. But then the job gets tricky. When you try to fill in a third color, you also by default choose nodes for the fourth color at the same time, and conflicts pile up in a hurry. Some kind of backtracking approach is probably needed here. Gasarch links to a paper by Elizabeth Kupin of Rutgers that explores these ideas in more detail. (If you want to prove the nonexistence of a four-coloring, this is presumably the way to go.)
Gasarch mentions two other promising avenues: integer programming (the discrete variant of linear programming) and SAT solvers–algorithms for the satisfiability problem. Having spent some time hanging out with a few master SAT solvers, I’m intrigued by the latter possibility. You can almost encode the grid-coloring problem as an instance of NAE-SAT, or not-all-equal SAT. Each node of the grid is represented by a variable that can take on any of four values. We group subsets of variables four at a time into clauses, where each clause includes the variables representing the four corners of a rectangle somewhere in the grid. For the 17-by-17 grid there are \({17 \choose 2}^2=18496\) clauses of this kind. The entire formula is satisfied if we can assign values to the 289 variables in such a way that none of the 18496 clauses has all four of its variables with the same value. After 40 years of work on SAT, there’s a highly developed technology for solving such problems. However, there’s a hitch. SAT problems are formulated in terms of boolean variables, with just two values each, but the grid-color variables have four values. Thus a further layer of encoding is likely to be needed, bringing a further explosion in the size of the problem instance.
One final hackerish note: What’s the best way to detect the presence of a monochromatic rectangle in a grid? My candidate goes like this. We encode the rows of the grid in a set of bit vectors–four vectors for each row, representing the four possible colors. For example, the red vector for a row has a 1 at each position where the corresponding node is red, and zeroes elsewhere. The blue vector has 1s for blue nodes, and so forth. Now we can detect a rectangle merely by taking the logical AND of two rows (an operation that could be a single machine instruction). A rectangle exists if and only if the result of the AND is nonzero. at least two bits are set in the resulting vector.
[Thanks to all the commenters for corrections and elaborations.]
Update: If you are coming late to this topic, please note there are three later posts discussing it, the last of which gives a solution: 22 December 2009, 13 November 2010, and 8 February 2012.
@Barry Cipra, my bad. I misread paddy’s comment (#2405). Then it really means the correlation is one-way only. One last idea: if we could find a 19×19 grid with as little as 4 monochromatic rectangles, we would instantly have a 17×17 grid that has no monochromatic rectangles.
The 17×17 with 4 colors is mathematically impossible.
Pingback: Programming conundrum « Logic Fragments
Pingback: Let’s Join O.R. Forces to Crack the 17×17 Challenge « O.R. by the Beach
I will also share my code. It probably has at least one bug in it (or else it’s a lot slower then I think it should be). It attempts to build outwards from a small seed rectangle.
http://codepad.org/38QprPCI
When considering the sub group colorings, for example 16X16, I think there needs to be 4 distinct 16X16 coloring inside the 17X17. (need they be distict, I think so) In addition these have union of a 15X15. This must have a 4 unique 14X14 which have a union of a 13X13,…. 4)12, 1U11, 4)10, 1U9……4)2, 1U1. (need better notation)
So can we work backwards, set the center point color, choose 4 unique 2X2 colorings (how many are there? Is the solution limited by this? i.e. have we just limited the center 3X3 to be constructed of these possible 2×2′s?) These then need to form a 3X3 (How many ways are there to do this from unique 2X2?) Now we need 4 distinct 4X4. ………….
I am missing something, Is it possible to constrain the construction in this way?
Pingback: Challenge – Announcement « Journey into Randomness
Hello,
Let’s not beat around the bush here… I like doing my mathematics by hand.
Computers only need to be used when the paperwork becomes overwhelming. Computers should not be used when a pencil and paper will get the job done.
By hand, a high-school student should understand how to generate an enormous number of 17×17 4-colourings with FOUR monochromatic rectangles. There may be a proof that FOUR is a hard limit, so find it in this essay, and get your $289. It may also be possible that no such limit exists.
Allow me to demonstrate:
Step 1) Define 4 colour sets { A, B, C, D }, where each set contains each colour, but has nothing in common with the other sets. There are many such sets.
Example:
A = 0123
B = 1230
C = 2301
D = 3012
Step 2) Using { A, B, C, D }, construct a perfect 16×16 4-colouring, where each row has nothing in common with 3 rows, and ( 1 of each colour ) in common with the remaining 12 rows.
Example: 16×16 - A perfect 4-colouring.
0 - AAAA
1 - BBBB
2 - CCCC
3 - DDDD
4 - ABCD
5 - ACDB
6 - ADBC
7 - BADC
8 - BCAD
9 - BDCA
a - CABD
b - CBDA
c - CDAB
d - DACB
e - DBAC
f - DCBA
* I am ashamed about how long it took me to formalize these simple permutations.
Step 3) Group the rows with nothing in common together. There will be 4 groups, each containing 4 rows. This will guide Step 4.
Gp0 = { 0, 1, 2, 3 }
Gp1 = { 4, 7, c, f }
Gp2 = { 5, 9, a, e }
Gp3 = { 6, 8, b, d }
Step 4) Build a 17th column by assigning 1 colour to each Group. Simply choose the corresponding Gp#. Note that a perfect 16×20 colouring can easily be generated using this method.
Step 5) Build a 17th row by assigning 1 colour to each Column-Group with nothing in common. In the 17th row, each number represents 4 identical numbers. Notice how there will be a single position, which has not been assigned a colour, marked by X. When it gets assigned, it introduces exactly 4 mono-chromatic rectangles into an otherwise perfect 17×17 colouring. Behold the result:
0 - AAAA 0
1 - BBBB 0
2 - CCCC 0
3 - DDDD 0
4 - ABCD 1
5 - ACDB 2
6 - ADBC 3
7 - BADC 1
8 - BCAD 3
9 - BDCA 2
a - CABD 2
b - CBDA 3
c - CDAB 1
d - DACB 3
e - DBAC 2
f - DCBA 1
L - 0 1 23 X
* L = Last Row Number 17
Please do not give up hope just yet. If somebody would like to show me a 16×21 perfect 4-colouring, this might open the gates to the 17×17 perfect 4-colouring, because the 16×21 grid is the first format not easily plotted perfect by hand.
Mathematical Aside:
The “Apex Constraint Condition” - I define this condition to be a colouring where each row has exactly one position, of each colour, in common with EVERY other row.
I conjecture that an analytical proof for the (existence / non-existence) of a perfect 17×17 4-colouring will arise from a thorough investigation of colourings having the “Apex Constraint Condition”.
Here is the solution to an NP-Complete problem, known to actually have a valid solution: 10 Best 5×5 Boggle Boards - TWL06
http://www.pathcom.com/~vadco/deep.html
All the very best,
JohnPaul Adamovsky
PS - Contact me if you have questions - logarithm69@hotmail.com
Perhaps Rohan equates “unknown” with “by-hand”.
Here is the most simple explicit case:
01230123012301230
12301230123012300
23012301230123010
30123012301230120
01231230230130121
01232301301212302
01233012123023013
12300123301223011
12302301012330123
12303012230101232
23010123123030122
23011230301201233
23013012012312301
30120123230112303
30121230012323012
30122301123001231
0000111122223333X
* Think of a professional way to say: “Suck on it… Suck it long, and suck it hard.”
* The metric system, that’s right, I don’t have a job.
————————————————————————————-
Proof
————————————————————————————-
Hello People,
Is the money real, or did I fall for a hoax?
Long story short. I’ve stumbled into a proof that 4 Monochromatic rectangles is the HARD-LIMIT minimum for a 17×17 4-Colouring.
Mathematics Required: High School - Basic Enumeration Techniques
STATEMENT: It is impossible to construct 5 rows in any 4-Colouring, which have nothing in common with each other.
PROOF:
r1 - 0
r2 - 1
r3 - 2
r4 - 3
r5 - X
* Filling X with any Colour will introduce a commonality in the set.
CONCLUSION:
Four sets of 4 rows with nothing in common is an absolute hard limit for a 16×16 perfect 4-Colouring. This represents a “Minimal Constraint Condition” for 16×16 Colourings. It can also be shown that the “Apex Constraint Condition” where every row has 1 position of each Colour in common with each other row is impossible to construct for a 16×16 grid, and trivial for a 16×20 grid.
T1 - Any 4-Colouring can only contain a maximum of 4 rows with nothing in common.
PROOF BY CONTRADICTION:
Proposition: A Perfect 17×17 4-Colourings Does Exist
Thus, this Colouring must contain a perfect 16×16 Colouring.
By T1, and demonstrated in above post, the Optimal 16×16 Perfect Colouring has 4 sets of 4 rows with nothing in common.
Even with this optimal arrangement, there will be 4 sets of columns with nothing in common, and there will be 4 row sets with nothing in common.
Each row and column set can therefore be assigned a unique Colour, which will be added to the 17th row and column respectively. Adding the 16-element-row and 16-element-column will then introduce ZERO monochromatic rectangles.
The final element in the Bottom-Right corner is marked with an “X”.
Leaving the “X” blank, even in the most optimal case, the 17th row, and 17th column have exactly 1 Colour in common with each other corresponding row or column.
Filling any Colour into position X will thus introduce exactly 4 monochromatic rectangles. Simply inspect the Enumeration examples in the post directly above this one…
The proposition is a logical flaw, because assuming it to be true, PROVES THAT IT IS FALSE!
Therefore, A Perfect 17×17 4-Colourings Does NOT Exist
PS - I prefer cash, so please find a colleague of yours that lives in Toronto, who can hand it to me, and then you can wire them the money.
PPS - I prefer not to deal with banks until I get a sincere-written-apology from CIBC for claiming that they saved my life by emptying the $5000 in my account, while I was in a 25 day-long coma. I saved up that money working construction to pay for a trip to find a merit-based Aerospace Engineering job. I’m pretty sure that bankers aren’t in the business of saving lives, and I don’t give up, so I am still unemployed.
PPPS - I’m thinking this was a hoax, because I doubt that a tenured computer scientist would have any trouble putting together this bush-league high-school proof after a thorough and systematic investigation. I’ve recovered from massive head trauma, so even if it was a hoax, I’d at least like some peer review, and then my money in cash.
PPPPS - I also wrote an extremely powerful search algorithm in C with meticulous and space-saving record keeping, so as to completely eliminate cyclic redundant analysis, while being extremely greedy. Row isolated deviations allowed my quad core to analyse 2,733,499,642,000 of the best colourings in 9 hours and change. The program tanks out at 4 monochromatic rectangles, moves around the 6 to 10 space, and finds the next closest 4-mono-Colourings (typically 20 of them).
5 Monochromatic Rectangles are never found.
Maybe put out a bounty to prove that they don’t exist.
Either your intuition was way off, and-or you’re a stooge.
All the very best,
JohnPaul Adamovsky