A recent post on bit-player drew my attention to William Gasarch’s 17 x 17 rectangle challenge. In short, Gasarch is offering $289 (289 = 17 x 17) for the solution to the following puzzle.

The problem is to take a rectangular n x m grid, and color each of the squares with one of four colors, so that there are no rectangles in the grid whose corners all have the same color. For example, on the right you can see a 6 x 6 grid which satisfies this constraint.

It turns out that if the size of the grid is 19 x 19 or bigger, then you can prove that it’s impossible to color the grid without creating a rectangle. In all cases up to a 16 x 16 grid, Gasarch has an example of a coloring that satisfies the no-rectangles constraint. However, the 17 x 17 and 18 x 18 cases are still open. To win the $289, you need to send Gasarch an example of a rectangle-free coloring of the 17 x 17 grid.

If it turns out that it’s possible to color the grid in this way, then the proof that you can do so is simple — you just draw a picture of the coloring (it’s easy to get a computer to check that it doesn’t have any rectangles). However, if it turns out to be impossible then it can be very hard (read: long and ugly) to prove that that’s the case. This is why the problem is so appealing to people with very little experience in mathematics: to solve the problem, all you have to do is draw a picture!

Of course, it’s easier said than done. There are different ways to color a 17 x 17 grid, and very few of them will be rectangle free. If you were to write a computer program to check all possible colorings, it would take longer than the age of the universe to run.

My first thought after reading the bit-player post was that a simulated annealing algorithm might do the trick. Simulated annealing is a computational technique which is based on the way that metals can be cooled slowly in order to minimize the number of defects, effectively finding a minimal energy solution to the problem of arranging the atoms in the metal. Simulated annealing tends to work well in situations that have a large number of possible states, and a large number of local minima — just as the rectangles problem does.

I’m working on this algorithm at the moment, and hopefully I’ll have a post about that in the near future. But while I was thinking about the problem, I became distracted by another question: if you color the grid randomly, how many same-color rectangles do you create on average? It’s easy to write a compute program that uses Monte Carlo to approximate this number, but I wanted to do it analytically.

It seems to be a difficult problem, because each cell in the grid can potentially be part of many rectangles. It seems as though there’s a lot of interdependence between the colors of different cells, which will make the calculation very difficult indeed.

Undeterred, I decided to try a naive calculation, in the hope that even though it was wrong, it wouldn’t be too wrong, and it would give me some insight into how to do the full calculation. First I worked out how many rectangles it’s possible to make on an n x n grid by joining corners. After some thought, you can see that this number N is given by:

For each potential rectangle, to be counted it needs all four of its corners to be the same color to be included in our count. Each cell has a probability of 1/4 of being any particular color, so the probability of getting all four the same is , but this could happen with any of the four possible colors, giving a total probability of . Therefore, according to this dodgy calculation, the average number of rectangles R in an n x n grid is

So how does this rough calculation compare with the numerically computer results? Take a look for yourselves. The dots are the numerical approximations (which should be pretty accurate) and the dashed line is the formula I derived above:

It turns out that this formula gives precisely the right value for the expected number of rectangles in a random coloring! So now my question is: is it actually the case that, for some subtle reason, the calculation I did above is valid after all, even though intuitively it seems that it should be completely wrong? Or is it just a coincidence that it comes out with exactly the right answer? I may be thinking about this one for a while.

## 17 comments

Comments feed for this article

December 10, 2009 at 5:53 pm

Robert CrowstonI can’t immediately think of a reason why the calculation seems right, but the calculation seems intuitively correct to me. That is, I can’t see any reason why the relationship between different rectangles would actually cause any trouble (I know it could, but my intuition says it probably won’t).

I do like this problem though, it is so easy to explain.

December 11, 2009 at 10:56 am

Chris TaylorThanks for the comment Rob. Here’s how I thought about it. Consider the six grid squares arranged in the following pattern:

* * *

* * *

Clearly there are three possible rectangles that can exist here. However, their existence isn’t independent: It’s impossible to have two rectangles without also having a third. The way that I did the calculation doesn’t take this into account. As George points out below, though, expectation is linear (in the sum over all possible rectangles) even when the random variables aren’t independent — a thought that didn’t occur to me. Maybe that’s why I’m not a probabilist ;)

December 10, 2009 at 11:23 pm

George KangasThe reason your “naive” resoning is valid, is that the expectation operator is linear: E[X + Y] = E[X] + E[Y], whether or not the random variables X and Y are independent.

December 11, 2009 at 8:24 am

KanodonkeyHi Chris,

nice post, thanks very much for that. I have tried the simulated annealing approach with mixed results. Its pretty easy to code this up in CUDA and run over GPUs. I have 5 GTX 295 graphics cards which I can occasionally throw at this problem (2400 processors) and I tried a few cooling schedules, epochs etc over random start conditions. Typically I anneal for 10 million epochs. Throwing the 16×16 case at this setup finds solutions almost instantly. It also finds solutions to the (until recently unknown grids) such as 21×11 pretty quickly. So far the 17×17 has eluded it (and in fact the best it has done on a 17×16 still has one bad rectangle in it).

All the best

December 11, 2009 at 11:01 am

Chris TaylorThanks for the comment. It’s good to know that someone has made a serious attempt at a simulated annealing solution. I read (in a comment on bit-player, I think) a conjecture that perhaps it’s impossible to k-color a grid that’s larger than x . This hold true for k=2 and 3 (you can 2-color a 4×4 but not 5×5, and you can 3-color a 9×9 but not 10×10) and it’s certainly an appealing result. Of course, two data points do not a theory make…

Out of interest, what’s the best solution you’ve found on a 17×17 grid?

December 11, 2009 at 11:43 am

KanodonkeyThe best result on a 17×17 grid had 6 bad rectangles in it. On Gasarch’s website he has a result for 17×17 where there is just one missing square. Whatever colour you put in that square you end up with 4 bad rectangles, which means that there is at least one better solution to the 17×17 than the simulated annealing has brought up. That solution was obtained by taking a 16×16 solution and trying to pad the edges. One idea that I had was to generate 17×16 solutions (if possible) by simulated annealing and then throwing these at a brute force type technique to try to fill in the edge.

An interesting note on the simulated annealing is what one uses as the Energy function or Hamiltonian. The obvious candidate is the number of bad rectangles but one can also throw in other terms. For instance one can penalize rectangles with 3 corners the same colour — but with a much lower penalty than all 4 corners the same colour. I have tried that but so far no joy. You could also reward rectangles with all 4 corners the same colour.

An interesting observation. If I run simulated annealing from multiple random start positions I can build up a histogram of count vs final number of bad rectangles. This distribution is roughly normal — with a fatter tail on the upside. Looking at the mean and variance of the distribution I can estimate how many standard deviations I am away from a solution, and a bit of math will show me roughly how long I would have to run to stand a chance of hitting a solution. So far the mean has been around 12 and the standard deviation around 1.6. Even on GPUs that amounts to a large number of years to get lucky! Playing with the annealing schedule might allow one to shift the mean and the standard deviation although of course its possible there is no solution!

Hope this helps.

December 11, 2009 at 12:33 pm

Chris TaylorI realised I made a mistake as well – the paper by Gasarch will have a 3-coloring of a 10×10 grid. Oh well!

December 11, 2009 at 11:55 am

KanodonkeySorry I of course mean to say reward rectangles with 4 different colours for the 4 corners

January 9, 2010 at 6:48 pm

roulette spielenSometimes it’s really that simple, isn’t it? I feel a little stupid for not thinking of this myself/earlier, though.

June 6, 2010 at 12:51 pm

Challenge – Announcement « Journey into Randomness[…] also here,here,here,here and . Possibly related posts: (automatically generated)Advertising: Take heed from the tactical […]

July 15, 2010 at 7:14 pm

JohnPaul AdamovskyHello,

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.

——————————————————————————-

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

March 19, 2011 at 7:20 pm

AnonThis “proof” ended up being incorrect, right? A retraction here would be nice.

March 20, 2011 at 9:48 pm

JohnPaul AdamovskyListen Anon, you worthless piece of shit:

If you want to read my work and isolate the logical error, then I suggest that you go ahead and do so.

The next time that you want to bless us with you mediocrity, I will enforce that you to do it as a form of SCIENTIFIC peer-review, while it is still fresh.

If you don’t follow this command, I will humble you with the programs that I write, and if you persist with being an ignorant lightweight, I will publicly humiliate you.

It is not my job to be a “NICE GUY”. I am one smart motherfucker, and you are NOTHING.

Did you even run the “Proof-Of-Concept.c” program, which I published?

The next time you speak up without doing thorough investigation, I will take the truth, and Sodomize it into you. Do I make myself clear?

All the very best,

JohnPaul Adamovsky

PS – I consider myself an Oracle-Machine-Automaton, and I need you for NOTHING.

March 20, 2011 at 10:00 pm

Chris TaylorJohnPaul, let’s try to keep it civil, huh?

Did you ever contact William Gasarch with your solution? He’s the one who offered the prize.

March 20, 2011 at 10:28 pm

JohnPaul AdamovskyChris,

I contacted William Gasarch with a proposal to solve the 17×17 problem, but it was too comprehensive for him to read. Go to his blog to read the most recent comments, because I published my work there.

The last time I checked, civilized people use the tools of reading and writing to investigate bodies of work, before they run their mouths about it.

In the realm of the 17×17 problem, I’m doing all of the investigation plus reading. There is literally nothing of value coming from anyone else, including Gasarch himself.

If you don’t read, expect me to set you straight. I am the one trying to keep things civilized, but I do it with personal style. If you want your blog to be boring, then ask me to leave, and I will.

All the very best,

JohnPaul Adamovsky

PS – READ, READ, READ.

February 12, 2012 at 11:32 pm

Chris TaylorThis problem has now been solved – a 4-coloring of the 17 x 17 rectangle *is* possible. You can read about it here: http://blog.computationalcomplexity.org/2012/02/17×17-problem-solved-also-18×18.html and you can see the solution here: http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17.txt

November 7, 2011 at 10:26 am

Richard Snape (@snapey1979)@JohnPaul A colouring with only 3 bad rectangles seems to have been found – http://linbaba.wordpress.com/2011/11/06/a-new-record/

#justsaying