This work is licensed under a
Creative Commons License.
|
Monday, November 30, 2009
The 17x17 challenge. Worth $289.00. This is not a joke.
Posted by GASARCH
The 17x17 challenge: worth $289.00. I am not kidding.
Definition: The n x m grid is c-colorable if there is a way to c-color the vertices of the n x m grid so that there is no rectangle with all four corners the same color. (The rectangles I care about have the sides parallel to the x and y axis.)
The 17x17 challenge: The first person to email me a 4-coloring of 17x17 in LaTeX will win $289.00. (I have a LaTeX template below.)
UPDATE: THE RESULTS ABOUT OBS4 HAVE CHANGED SINCE THE ORIGINAL POST SINCE BRAD LARSON EMAILED ME A 4-COL OF 21x10 and 21x11. UPDATE: BRAD LARSON EMAILED ME A 4-COL OF 22x10.
Why 17x17? Are there other grids I care about? We (We=Stephen Fenner and Charles Glover and Semmy Purewal) will soon be submitting a PAPER (see TALK for a superset of the slide-talk I've given on this paper) on coloring grids. Here are the results and comments:
- For all c there is a finite set of grids a1xb1, ..., akxbk such that a grid is c-colorable iff it does not contain any of the aixbi (n x m contains a x b if a &le n and b &le m). We call this set of grids OBSc (OBS for Obstruction Set).
- OBS2 = {3x7, 5x5, 7x3}
- OBS3 = {19x4, 16x5, 13x7, 11x10, 10x11, 7x13, 5x16, 4x19}
- OBS4 contains 41x5, 31x6, 29x7, 25x9, 23x10, 10x23, 9x25, 7x29, 6x31, 5x41
- Exactly one of the following sets is in OBS4: 21x13, 21x12.
- Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17.
- If 19x17 is in OBS4 then 18x18 might be in OBS4 . If 19x17 is not in OBS4 then 18x18 is not in OBS4 .
- A chart of what we do and do not know about 4-colorings of grids is here.
- A Rectangle Free Subset of a x b is a subset of a x b that has no rectangles. Note that if a x b is 4-colorable then there must be a rectangle free subset of a x b of size Ceil(ab/4). We actually have a rectangle free subset of 17x17 of size Ceil(289/4)+1. Hence we think it is 4-colorable. For the rectangle-free subset see here. For the original LaTeX (which you can use for a template when you submit yours) see here. THIS IS WHY I AM FOCUSING ON 17x17--- BECAUSE I REALLY REALLY THINK THAT IT IS 4-COLORABLE. I could still be wrong.
What if 17x17 is not 4-colorable? Then nobody will collect the $289.00. Even so, if you find this out I would very much like to hear about it. I don't want to offer money for that since if your proof is a computer proof that I can't verify then its not clear how I can verify it. I also don't want to offer money for a reasonable proof since this may lead to having the Supreme Court decide what is a reasonable proof.
Can I get a paper out of this? FACT: If you get me the coloring and want to use it in a publication then that is fine. OPINION: It would not be worth publishing unless you get all of OBS4. See next question.
What do you hope to get out of this? My most optimistic scenario is that someone solves the 17x17 problem and that the math or software that they use can be used to crack the entire OBS4 problem. If this happens and my paper has not been accepted yet then we could talk about a merge, though this is tentative on both ends.
Has there been any work done on this problem that is not in your paper?
- A Rutgers grad student named Beth Kupkin has worked on the problem: here.
- A high school student (member of my VDW gang) Rohan Puttagunta has obtained a 4-coloring of 17x17 EXCEPT for one square: here.
- SAT-solvers and IP-programs have been used but have not worked--- however, I don't think they were tried that seriously.
- Here are some thoughts I have had on the problem lately: here.
- There is a paper on the 3-d version of this problem: here.
Is Lance involved with this at all? When I gave a talk on grid colorings at Northwestern, Lance fell asleep.12:14 PM
# 137 comments
-
Here is a quick approach, I am not able to pin down why it would not work.
Since OBS3 = {19x4, 16x5, 13x7, 11x10, 10x11, 7x13, 5x16, 4x19}, I suppose a 8x8 grid is 3-colorable.
I think of the 17x17 grid as split into 4 8x8 grids (build them from the 4 corners) and there's the remaining cross (intersecting right in the middle).
Suppose I have a 3 coloring, let me call it C. Apply C on the top-left and bottom-right sub-grids, and a suitable of C[*] on the remaining two. I color the "cross" with the fourth color.
[*] A variation of C that might work is the following: suppose C used the colors black, white and gray. The variant of C is obtained by swapping black and white, and leaving gray as is. If I'm not mistaken, this is a valid coloring?
The fourth color doesn't create monochoromatic rectangles. There are no problems within the four grids. Only potential problem is with rectangles going across, but my intuition is that the swapping will take care of it.
Does this make any sense?
-
Whoops, sorry - there is definitely a problem with gray rectangles, and presumably with other cross-over rectangles too. Whew, I think I need a concrete 3-coloring before I go down this particular route.
The intuition was be to try and "mirror" the 8x8 colorings across and exploit the fact that they were proper colorings to begin with, but perhaps this is not quite correct. Yikes :)
-
Results #9,#10,#11 are in conflict.
The chart in #11 marks 19x17 as Non-4-colorable and 18x18 as Unknown.
But #10 suggests that one of those letters is wrong. Also, that would imply that #9 could be simplified to just being 17x18 or 17x17.
Which is right? The chart does make a visually compelling argument that it should be 17x17.
-
Unless I misunderstand this was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem
-
@Bruce:
The 4-color theorem refers to unique colors in adjacent regions. c-colorable configurations refers to corners on rectangles.
Note that the 17x16 clearly 4-colorable under Bill's definition (i.e., in the txt file example by the high school student you can simply delete the last row).
-
SKY: I don't see what the
problem is. Please elaborate so I can fix it
or clarify it.
19x17 is NOT 4-colorable.
17x17, 17x18, 18x17, 18x18
are NOT known.
To be in the OBS_4 a grid
has to NOT be 4-colorable
and have every proper subgrid BE 4-colorable.
-
Okay, I want to pursue the first approach I outlined just a little bit longer.
Let X be a 3-coloring of a 8x8 grid. Suppose the colors used are black, white and gray. Let Y be the coloring obtained from X by making all black nodes white, white nodes gray, and gray nodes black (a permutation, after all). It's clear that Y is also a 3-coloring.
Let the 4 8x8 sub-grids of the 17x17 grid (each obtained by starting at a corner and expanding inwards) have the names A,B,C,D in clockwise order (A == top left, and so on).
I color A and D with X and B and C with Y. And everything that's leftover is colored red (the fourth color).
It's clear that rectangles formed with vertices of the "cross", the red ones, are never monochromatic. Rectangles sitting inside A,B,C,D are also not monochromatic. So we worry about those that lie in, say, A and B. The left column of the rectangle is in A and the right column is in B. Clearly, if both columns of the rectangle identified are the i^th columns in their respective 8x8 grids (for the same i), then because of the change in coloring, it cannot be monochromatic. If it's the i^th and j^th column in their respective grids, i different from j, it still cannot be monochromatic, because if it was, look at the i^th and j^th columns *inside one of the grids* and note that that would have been monochromatic.
A similar argument takes care of rectangles across B and D, C and D and A and C. Luckily, we don't have to worry about A and D and C and B.
Now we look at rectangles with one endpoint in each of A, B, C and D. Here, treat "A and C" as one large properly colored unit and "B and D" as a large properly colored unit and repeat the argument above.
Does this make a little more sense than before?
-
@Neel, your approach would easily imply that 16x16 is 3-colorable.
@GASARCH, why isn't the grid in #11 symmetric? Why is 21x9 4-colorable but not 9x21?
-
@Neel: you can still have corners in each of A, B, C, D which are at different coordinates within each 8x8 quadrant, and therefore may be the same color. You must additionally devise a specific grid or set of grids which disallow this. Good luck!
-
Could someone verify this solution?
20022112200330023
00220022002200220
31133003311221132
13311331133113311
20022112200330023
20022002200220022
31133003311221132
13311331133113311
20022112200330023
02200220022002200
31133003311221132
31133113311331133
20022112200330023
02200220022002200
31133003311221132
13311331133113311
20022112200330023
-
@Ess: Look at the 5th and 6th rows of your so-called "solution":
20022112200330023
20022002200220022
These rows contain many monochromatic rectangles, such as the rectangle in columns 2 and 3 with all four corners colored 0. Remember, the problem is to color the grid such that no rectangles have all four corners the same color.
-
I probably misunderstood the problem but something doesn't make any sense. You say that the 3x7 grid is in OBS2. This just isn't possible. Why? Because:
1. If two the same patterns are used they will ALWAYS form a rectangle if the width > 2:
010
010
2. With two colors, you could see each line as a binary number. However, there are only 8 different combinations. 7 of these need to be used (see point 1), therefore you get the following solution (interchangeing lines and flipping all colors won't change anything):
000
001
010
011
100
101
110
Which would work perfectly if the first line wasn't necessary. But as there are no other permutations left, this HAS to be used!
Could you provide the 3x7 (or 7x3, it's almost the same) grid? I just don't see how it could be solved!
-
For the people who don't want to check their solution by hand, I've put a PHP script on pastebin that highlights all rectangles. It's not heavily optimized, but it should work with any size and number of colors.
-
20022112200330023
00220022002200220
31133003311221132
13311331133113311
20022112200330023
20022002200220022
31133003311221132
13311331133113311
20022112200330023
02200220022002200
31133003311221132
31133113311331133
20022112200330023
02200220022002200
31133003311221132
13311331133113311
20022112200330023
an attempt from Eric Purdy (too frantic to check!)
-
nope, not right
-
dutch, saying 7x3 is in OBS2 means it is NOT solvable.
I'd like to reiterate Anonymous #8, the grid given has multiple discrepancies: 21x9, 21x10, 21x11, 21x12
-
Oh, Ok, that explains why I couldn't get any further.
-
I'm probably making a simple arithmetic mistake here, but when I went into the paper to see the argument for 7x3, I calculated
z_{7,3} = floor(3/2+sqrt(57))+1 = 12
from Cor 2.4, which is not 11 as in the table in Section 6.
Is the "divided by n" inside the radical supposed to be dividing everything inside the radical?
-
Do I misunderstand the OBS or are you also interested in a 4-coloring of 21x10?
120010130231144221101
111203323023004323414
403011221233201140214
012334030223303131422
102322001304014413203
043104332322420204114
313023024012310444033
030224212130342011312
334420413400241402421
231130402114131320243
-
BTW 22x10 and 23x10 are also 4-colorable (if my program doesn't have bugs).
-
Jules, that's actually a 5-coloring.
-
Hah, good catch :)
-
12345678901234567
1 01230123012301230
2 12301230123012301
3 23012301230123012
4 30123012301230123
5 01230123012301230
6 12301230123012301
7 23012301230123012
8 30123012301230123
9 01230123012301230
0 12301230123012301
1 23012301230123012
2 30123012301230123
3 01230123012301230
4 12301230123012301
5 23012301230123012
6 30123012301230123
7 01230123012301231
My suggestion, contact uchiki86@gmail.com
-
@Anonymous:
12345678901234567
1 01230123012301230
2 12301230123012301
3 23012301230123012
4 30123012301230123
5 01230123012301230
6 12301230123012301
7 23012301230123012
8 30123012301230123
9 01230123012301230
0 12301230123012301
1 23012301230123012
2 30123012301230123
3 01230123012301230
4 12301230123012301
5 23012301230123012
6 30123012301230123
7 01230123012301231
-
21x10 is also shown as not solved, and has a smaller search space then 17x17. Would you be interested in its answer as well?
-
in http://www.cs.umd.edu/~gasarch/BLOGPAPERS/17x17chart.pdf
the chart is not symmetric.
Check 10x21 vs. 21x10.
Same for 11x21 and 12x21.
-
This post has been removed by the author.
-
uchiki86 - what about your rows 4 and 12
-
he most interesting part of the post
-- Why 289?
-
what's up with the 74 item rectangle free 17x17? is 74 provably the smallest, or could there be a 73 yet to be found?
-
@Anon: Of course! Should've occurred to me, thanks. I considered using the new color in the permutations - that seems to take care of all crossover rectangles (there was, actually, a more direct problem with my solution). However, coloring the cross in between becomes rather tricky!
@sep332: Thanks for pointing that out! I'm not sure I see why the one in each quadrant should be a problem (yet) - if you have shown it across the individual quadrant, like I was trying to say before, treat "A and C" as one large properly colored unit and "B and D" as a large properly colored unit and repeat whatever argument you have for, say, ruling out monochromatic rectangles across A and B. The coordinates cannot be too arbitrary since the rectangles have edges parallel to the axes?
-
It's impossible to solve by simply adding a row to the 16x17 solution as in the "EXCEPT for one square example" Any choice for the first 5 elements will lead to a rectangle.
-
i wrote my supercode which solved the problem but now i have no idea how to interpret the solution. my supercode is obviously coded in hard++.
any ideas?
-
What is the best shot rotation if your haste rating with ranged weapons is 1.72 and you are BM spec'd?
-
I'm pretty sure it's impossible.
Specifically, I posit that it's impossible to place 73 1s on a 17x17 matrix without creating a rectangle composed entirely of 1s.
To reduce the case-checking that would be required to test this, it's simple to prove that the four rows with the most 1s have between 20 and 23 1s in total.
I'm not too sure where to go past that, but if it can be proven that there exist four rows that span the column set with 1s, that makes things simpler. (Otherwise, if that can't be proven, it could lead to a way to construct the desired coloring!)
~scythe
-
anon to anon, the is a most formidable problem that lies at the very heart of this problem. If we solve your problem maybe we can solve the hardcode++ problem and maybe this will lead to a solution of the original problem ?
What a nice way of putting things.
Thank you.
-
01230012301230123
00000111122223333
01111122223333000
02222133320003111
03333100021113222
10123212332300301
11032221033210032
12301230130120123
13210203231030210
20231313002011312
21320320303101021
22013331200231130
23102302101321203
30312010212132320
31203023113022013
32130032010312102
33021001311202231
-
Previous Anonymous, you are wrong. At least test your proposed solution before posting it.
01230012301230123
00000111122223333
01111122223333000
02222133320003111
03333100021113222
10123212332300301
11032221033210032
12301230130120123
13210203231030210
20231313002011312
21320320303101021
22013331200231130
23102302101321203
30312010212132320
31203023113022013
32130032010312102
33021001311202231
-
For Anon #35: If its impossible, how can you explain the "74 items rectangle-free set" in the OP ?
-
The known results for 4-colorings claim that a 21 x 09 grid is colorable, but a 9 x 21 grid is not (reading the first value of the pair from the left column). There are other inconsistencies with some of the U cells close to this. I suppose a simple clerical error is to blame.
-
"Why 289?"
17*17
-
To Anon: yeah, rite who's gonna keep count of "For Anon #35"
what a joke.
-
Not a solution - but here's 74 zeros that seem to work (don't know how to specify a fixed width font, so the columns don't line up properly through blogger):
0...0....0......0
.0....0........00
..0.0..0......00.
...0.0.......00.0
....0.0.....00...
.......0..000...0
..0..00....0.....
.0...0.0.0.......
........00.0.0.0.
0..0..000........
......0..00...0..
....00..0.0......
.0.00......0.....
..00.....0..0....
000.......0..0...
.0......0...0.0..
0....0......0..0.
-
The chart had a typo which I have
now fixed. THANKS for catching it!
YES I am also interested in the status of 21x10, 21x11, 21x12, 22x10,
17x18, 18x18. However I am not putting a bounty on those. It IS my hope that whoever does 17x17 will then use the software or math on those.
Aaron Sterling- I will email you privatly on the mistake you may have found (fortunatly it does not affect the contest). Also, Aaron,
THANKS for posting with your name,
else I could not contact you.
-
Apologies for the post - was reading a thread on hacker news where they said you'd found a single colouring with 73 cells. Now I've checked it I see it was 74
-
It is claimed in the paper that exactly one of 19x17, 18x17, 17x17 is in OBS4 (This is close to a typo repeating that 22x10 is only 6 other unknown grids..).
We know that 17x17 in OBS4 => 18x17 in OBS4 => 19x17 in OBS4. Thus, according to the claim 19x17 can be the only one of the 3 to be in OBS4 and 17x17 is solvable..
But it seems clear that most of these claims are actually riddled with typos.
-
A valid coloring for a m x n grid can be turned into a valid coloring for a (m-1) x n grid (you just have to forget the last line of the grid). If there is
exactly one of the following sets in OBS4: 19x17, 18x17, 17x17, the 17 x 17 grid must have a valid coloring.
-
Scott and louif, it's apparent that OBS4 is only a list of the "smallest" unsolvable grids: i.e. if 17x17 is in OBS4 then 18x17 is not, even though both would be unsolvable.
-
It's trivial to see that if you populate the left and top rows then all the remaining cells can be filled by process of elimination (or using process of elimination will yield a contradiction).
Using this method I have a simple program that "proves" no solution, see here.
-
David Benson: Can you elaborate on your trivial "process of elimination" approach? I suspect you're making a silly mistake.
-
@David:
Remember, there are four colors. Let's test your "process of elimination" theory on a smaller grid, say 3x3. Pretend you fill in the top and left rows as follows:
123
2__
3__
The four _s can be any color as long as they are not all the same color. This leaves 4^4-4=252 possibilities. No process of elimination here.
-
I decided to try the brute force approach. Last night, I wrote a program that fills a 17x17 grid with random numbers between 1 and 4, then searches for rectangles. If it finds one, it changes three of the vertices to new random numbers. This process is repeated until no rectangles are found. It has checked more than 131 million grids so far, with no hits.
-
Sassan, you are rite i ran the same program(not even knowing what the program is and waht it really does) on my computer and nothing checked. so, the answer to the original problem is a big "-no-".
-
Sassan: It would be good to test your approach on 15x15 or 16x16, which do have solutions.
I also tried a Monte Carlo approach. I could get a 15x15 with a fair amount of computation, but I couldn't get a 16x16 even running on a grid for 12 hours. It seems like the state space is too large and/or complicated for my code. Thus I can't say that my not finding a 17x17 means that there isn't one.
-
Is there a LaTeX file of the alternate 74 Rectangle Free Set (there are only 2, apart from the trivial rearrangement of columns and rows).
-
Here's a 74 RF set I generated with an IP solver in python. I haven't verified that it's the alternate form though.
-
huh ? is sassan's code widely available or how did anon run it on his computer ?
-
Sassan,
Why do you change three of the vertices, and not one? Changing three seems like you are more likely to introduce additional collisions.
Brian
-
I myself tried various greedy-style local search approaches, where we start with a random coloring and repeatedly try to make a modification that reduces the number of bad rectangles by as much as possible. But for me no luck up till now either.
-
I found the coloring. There exists one. But i am unwilling to give away my solution for only 289.00.
-
I am skeptical of Annon #60's claim. It does, however, raise the interesting question can he convince us he has the correct answer with a zero knowledge proof for this particular problem?
-
well, i wouldn't be too sure of either now. #60 anon must certainly be a great card player.
-
I've tried the greedy and brute-force coloring approaches too without any luck so far. :(
Question: Would anyone want to join forces? Perhaps we can increase the bounty using anon #60's trick. (But to be honest I don't care about the money at this stage, and would prefer to do an open wiki/wave where one could gather programs/ideas/failed approaches.)
email: 289challenge@gmail.com
-
Suppose you have:
ab
cX
and you wish to know the value of X.
Since a,b,c touch you can assume they are three distinct elements; hence X is the unique {0,1,2,3} - {a,b,c}
So if you have
abcdefgh
q.....
r
s
t
you can compute the dots left-to-right -- or reach a contradiction.
-
whooops, reading your editted post i can see that i had the definition wrong.
-
I find the problem presentation confusing, and I would appreciate it if someone would verify whether or not I understand the correctly.
If I understand correctly, we are trying to create an N-coloring of an YxZ grid fitting constraints C. By grid, we mean the inset presence grid usually called a "checkerboard", where member cells, rather than member vertices, are considered, and where the member cells are not importantly different than squares.
The prize line is only satisfied for a coloring of four or fewer colors of a grid of exactly Y=17, Z=17, given C.
The constraints C are:
* From the grid, define the set of rectangles R such that every rectangle:
** Contains only inset unit cells, never fractions and never empty surrounding space
** Every rectangle position allowable by that constraint is represented, given a minimum dimension in either direction of two unit cells - that is, fit any rectangle you can along the border lines of the grid, and count it
*** We skip rectangles with dimension 1 because identical corners seem to violate the spirit of the search, and because 1x1 squares preclude a solution being possible
** By example, a grid of Y=2, Z=3 would have a set R of three rectangles: the two 2x2 squares and the master 2x3 rectangle. Similarly, a Y=3 Z=4 grid would have 17 rectangles.
** The 17x17 <= 4 coloring must therefore satisfy 18496 rectangle corner sets.
* For every rectangle in R, show that the histograph of the four corners' colors contains a minimum of two colors.
Is that a correct re-statement of the problem?
For reference, R is expressable as
rectlist(Width, Height) ->
lists:flatten( [ [ {{X,Y},{X+W-1,Y+H-1}} || X <- lists:seq(1,(Width+1-W)), Y <- lists:seq(1,(Height+1-H)) ] || W <- lists:seq(2,Width), H <- lists:seq(2,Height) ] ).
which is valid erlang that outputs
1> color17:rectlist(3,3).
[{{1,1},{2,2}},
{{1,2},{2,3}},
{{2,1},{3,2}},
{{2,2},{3,3}},
{{1,1},{2,3}},
{{2,1},{3,3}},
{{1,1},{3,2}},
{{1,2},{3,3}},
{{1,1},{3,3}}]
For the sake of ease, one may also
cornerlist(Width, Height) ->
[ { {A,B}, {A,D}, {C,B}, {C,D} } || {{A,B},{C,D}} <- rectlist(Width,Height) ].
-
This post has been removed by the author.
-
Um... color the first row ABABABetc, then the second row CDCDCDetc. Alternate rows in this fashion, no two letters will be adjacent. It's really late so maybe I'm missing something obvious.
-
@Neel:
here is a 8x8 grid colored with 3 colors:
1 1 2 2 2 2 2 2
2 2 0 0 1 1 0 1
2 1 0 2 0 0 1 1
2 1 1 0 0 1 2 0
2 0 1 1 0 2 0 1
0 2 0 1 2 1 1 0
2 0 1 0 1 0 1 2
1 2 2 1 1 0 0 0
-
Alexandru and Neel- the paper has a 3-coloring of 10x10.
bill
-
@Alexandru, @gasarch: Thanks! The explicit colorings should come in very handy, and I'm all inspired again.
By the way, coming up from the other side - what's the smallest number of colors with which one is able to color 17x17? The first trivial number that comes to mind is 17 (color each row with a different color). An application of the probabilistic method seems to yield a number more than this. Applying the Lovasz Local Lemma seems to give us 14 (worked this out in a discussion with a couple of interested/victimized colleagues here).
By looking at the 8x8 approach, I think getting a 7-coloring is quite easy, use a different set of 3 colors on the second set of quadrants, and yet another new color on the cross. I'm pretty sure it's not hard to bring this down to 6.
Anyone got a 5-coloring? Sorry if a 5-coloring is obvious or has been pointed out in the post/associated literature and I've missed it all along!
By the way, if you look at the 4x6 coloring, it has some very nice symmetry (mirror symmetry, across diagonals symmetry). It seems to reaffirm my hope to be able to go about this in a structural fashion, although I admit that I could be off on this by miles!
-
@neel The 17x17 grid can be 5-colored.
-
Has anyone tried using permutations of the rectangle-free set of 74 in order to reduce the complexity of a brute force approach? You might try to find as many rectangle-free sets of 73 as possible, find the 2 or even 3 that overlap least, and then randomly delete overlapping entries from all but one of the grids. That could reduce the overall complexity drastically.
-
I want to know if a 4x4 and 5x5 grid using 2 colors is possible, also whether a 9x9 and 10x10 grid of 3 colors is possible. If the 4x4 and 9x9 are possible while the 5x5 and 10x10 are not, I think it's reasonable that the 17x17 is not possible.
-
This post has been removed by the author.
-
@Brad: I see - nice! Did you work that out, or is it around in the blog post/paper/talk slides and I missed it?
@Anon 73: At least from the talk slides and the blog post, I figure that:
5x5, 2 colors - not possible,
4x4, 2 colors - possible (even 4x6 is possible)
10x10, 9x9, 3 colors - possible. In fact, it was pointed out to me that the paper has an explicit 10-coloring. Hope this helps!
-
Well if anyone wants a good starting point.
02231320323013110
31303221100023102
01322212013330001
22100030113112332
31131002221030322
20233230230311021
30120113233221100
20003322101230131
13202303012321310
11013200322212303
33220101301312032
32010332011021223
03012011130233212
00311301232102231
12021123112003033
21320133320100210
13332020001102123
My algorithm only finds 18 problem rectangles in that (and my algorithm can find the 20x10 and 17x17 (5 color) in under 30 seconds.
-
This post has been removed by the author.
-
This post has been removed by the author.
-
Michael,
I think 4-Coloring 2 x n is trivial:
12
34
12
34
....
-
@neel
I constructed a 5-coloring of the 17x17:
14115523345324421
32355445114232225
25145411123345522
32414423225455135
42545342512354351
41152422443133552
54243124455432351
35552131341113324
55132144512221335
22222414335134531
31234254145511121
12441235544531542
11544555252335423
14254543512143144
53425252421323234
51211513411544312
23333333233512443
-
Edward - Any adjustment to your grid will introduce new monochrome rectangles as it goes. Taking an incorrect solution as a starting point is not going to make finding a solution any easier, it's just going to force a similarly huge amount of computations but in a different way.
-
For what its worth I found this which only has 8 rectangles in it using simulated annealing on GPUs.
00130231113223103
21310021323230310
03321322010103210
30311130101322220
32132113300210202
02323003201021113
13012223213311000
10133301221302302
21222010011332033
03203230321110231
12330212132002031
33002011132101323
21020200330313122
30203102210233021
30012312023020131
21101333232031201
11200123002123332
-
FWIW, the GPU simulated annealing has now found a tiling with just 7 bad rectangles and one with just 6. If it is of any use to anyone I can post these here.
-
@Brad: Woah, how do you come up with things like that? :)
@kanodonkey: I'm sure you haven't missed this, but just in case, the post has a coloring that has only one bad rectangle... if your algorithm runs better on initial configurations with a small number of rectangles, then that would be the one to start off with :)
-
Esad: it's even more trivial than that :p
01
01
01
01
01
..
..
..
-
@neel It's a secret, at least for now. :-)
-
I was curious if anyone has pondered a lower granularity approach. That is to say, attempting to enumerate all of the 4-colorable 4x4 squares (or, even better, all of the 8x8 squares), and searching a space composed of these pieces.
Intuitively, we should appreciate by now that it is reasonably easy to come up with a 17x17 with only a few errors - and that the number of these is probably massive compared to the number with no errors. Further, there is little to no guarantee that the edit distance between the 17x17s with no errors and those with few errors is small. I appreciate that simulated annealing and GA both have tricks to get around these local maxima, but why not just decrease the total search space first?
I appreciate that enumerating all of the acceptable 4x4s will not be easy - and that there will probably still be many of them. However, there are a lot of tricks involving the symmetries and permutabilities of the problem that should allow them to both be both computed and stored in a reasonable amount of space and time. Also, I would be willing to believe that, if you get the 4x4s, that the number of 8x8s would not be so large (at some point the constraints will overwhelm the size of the search space, though exactly when is unknown).
Well, best of luck to all!
-
@neel Not sure I saw that. There is a link to a solution with just one missing "square" but as far as I can see whatever number/color you put into that missing square there are 4 bad rectangles not one. Maybe there was a different post I was missing.
-
@Brad: Heh! Link to an explanation when it's ready for the public domain, will you? I'm just generally mystified. :)
@kanodonkey: You're absolutely right! My bad, sorry. I imagined that any color in the missing spot causes one violation, for no earthly reason at all.
So, well, is 4 rectangles still better than 6 for a starting point, from the point of view that you were suggesting?
-
#35 has only 4 rectangles, nice one
i'm interested in the algorithm used to create the grid
-
#37 not #35 :-)
-
Sorry, i've not read all the comments of this post, so i don't know if the problem has been already solved, but I don't think it is posible to get that 17x17 square.
Thinking backwards, how far can you get with a 2-colorable problem? You could get 4x4, 4x5 or 5x4 colorable grids, but not 5x5. Why? Since you have two elements and 5 positions in each row you will have at least 3 positions with the same color in any row. There can't be any other rows which have that color repeated in those 3 positions. So there are only 3 (= 2^2 - 1)posibilities in 4 rows, f.e:
11122
221XX
122XX
212XX
???XX
Any combination you could think in substitution of the question marks will create a non-colarable grid.
The same thing happens with the 3-colarable problem. You could get a 9x9, 9x10 or 10x9 colorable grid, but no 10x10 posible, since any row would have at least one color repeated 4 times. You can think in only 8 (= 3^3 - 1) posible distributions but 9 more rows to get.
The last step would be applying the same to the 4-colorable problem. At least a color would be repeated 5 times per row. So only 16x16, 16x17 or 17x16 colorable grids could be found, but no 17x17 posible.
-
Miguel, a 10x10 is 3-colorable; see the pdfs in the OP.
-
There are 7 unique (up to re-ordering the rows and columns) rectangle free arrangements on 21x12 of cardinality 63--and none of any greater cardinality. Proof forthcoming just as soon as I get it written up.
-
I believe it's easy.
1x1 -> 1 colour
from 2x2 to 4x4 -> 2 colours
from 5x5 to 8x8 -> 3 colours
from 9x9 to 16x16 -> 4 colours
17x17 -> 5 colours
18x18 -> 5 colours
How do I now? Easy. For example, an 8x8 square. 7 in binary is 111, there are three characters on '111'. So you can do it with 3 colours.
For 8x8, 8 is 1000, you'll say 4 characters, let me explain.
The theory is:
1 - 1
2 - 10
3 - 11
4 - 100 -> From 4 to above 3 colours and 4 is not included on that rule!!! 4 will be included on the rule of 2 colours.
5 - 101
6 - 110
7 - 111
8 - 1000 -> From 8 to above 4 colours and 8 is not included on that rule!!! 8 in 3 colours
9 - 1001
10 - 1010
11 - 1011
12 - 1100
13 - 1101
14 - 1110
15 - 1111
16 - 10000 -> From 16 to above 5 colours and 16 is not included on that rule!!! 16 in 4 colours
Sooooooooo...
17 - 10001 -> 5 colours
18 - 10010 -> 5 colours
Sorry about my explanation, i'm spanish and my English is a little bit...... you know....
-
Ruben, 8x8, 9x9, and 10x10 can all be done with 3 colors.
-
#37's grid is very interesting. there are 72 ones, 72 twos, 72 threes and 73 zeros. there are 4 rectangles, all with zero-corners and all can be removed by switching the colour of point (4,0). the problem is, switching the colour of this point doesn't make things better. who made the grid, machine or human? it looks to synthetic to be a random guess and the probability of guessing a 4-rectangle grid is very low. i'm looking forward to hearing from the grid's creator.
-
there is no 17x17 solution.
i proved it.
generally speaking, for any n x n matrix whose cell has 1 <= value <= k, any matrix whose n > k*k cannot have solution.
proof itself is quite simple. smart middle school student is enough to understand.
-
Nara, if you really have that proof, post it! It's just wrong, as a 3-coloring of 10x10 matrix possible and 10 < 3*3 is not true.
-
Dude, the green background on your blog is killing me.
-
Am I totally missing what a strong c-coloring is? In the grid.pdf paper, Lemma 8.3, page 40: rows 4,8, columns 1,6? All colored R?
-
ZAC- THANKS- you have found a typo in the paper---
I will fix soon.
bill gasarch
-
ZAC: I have fixed it. THANKS!
Bill G.
-
This post has been removed by the author.
-
-
Sorry, I made a mistake in my previous comment. However, I do believe that the 17x19 case is impossible ... but I will not venture stating that I have proven it (yet).
-
Andre - 17x19 already known to be
not 4-colorable. See original paper
that is linked to
bill gasarch
-
Hi to everyone,
I've tried to solve the problem with a SAT solver, and couldn't yet.. I've written a Python script which translate the coloring problem to an equivalent Sat problem in the cnf file format, then I manually try to solve it with WinSAT and the script reads back the solution and checks if it works with the php script which has been posted..
The Python script is now at https://code.launchpad.net/~sir-rainbow/+junk/4col , feel free to experiment with it(GPL code), I think someone with more knowledge of SAT solver might crack it :) it's also useful to generate grid of which we know there is a solution :)
-
I've tried solving the problem with a SAT solver based on WalkSAT. Since WalkSAT is an incomplete procedure, it can't prove unsatisfiability in general. For nxn puzzles, I managed to find a solution to 16x16 but no solution to 17x17.
-
Dear Gasarch,
Thanks ever so much for bringing a truly fascinating problem to the world. It has kept me stimulated during the christmas holidays!
First of all, I have not solved it. However, I have tried a number of approaches and thought I would share my experience just in case it should inspire someone else.
I notice that the problem is highly symmetrical. If a single colouring is found for an mxn grid then then must be many others, since (I believe) the rows and columns can be permuted in any order, which leads to m!n! alternatives. Also, the 4 colours can be permuted and the grid itself can be rotated/reflected.
An exhaustive search may not be so hard, because the vast majority candidates can be avoided by building up from smaller grids that have solutions, i.e. starting at 1x1, extending and backtracking (plus a few heuristics to avoid unnecessary attempts). Using this approach I can find 16x20 grids quite easily, e.g.
0123012301230123
1230123012301230
2301230123012301
3012301230123012
0123123023013012
1230230130120123
2301301201231230
3012012312302301
0123200232101331
3012133121030220
2301022010323113
1230311303212002
0123331110322200
1230002221033311
2301113332100022
3012220003211133
0000121233332121
1111030322223030
2222303011110303
3333212100001212
Considering the number of vertices and colours, it is clear that if a solution for a 17x17 exists then at least one colour must occur >=73 times. So my next attempt involves searching for arrangements of single colour vertices (the remaining ones are blank) that has no monochromatic rectangles and then adding the second colour and so on. Using this technique it is possible to find grids with 74 zeros and 74 ones, e.g.
1___0____11_100_0
__100_1_1_100__0_
1__1_1_0_0__010__
___01101001__0__1
10__001__001___11
__011___10_11__00
_01__100_1_1__10_
00_1______1_0011_
010_0_0___11_1___
_000____11___10_1
_0__1_1_0__0_11_0
__01__11010_0____
11___0011___0_1_0
_10_10_0_1_0_0_1_
0111_0__0_____001
01_0_110__0_1___0
__1___01__001101_
I'm using a GA approach here, but the last two colours are proving difficult (as one would expect). I was very impressed with kanodonkey's approach, since the best I can do with the remaining colours is 14 monochromatic rectangles.
@kanodonkey, which GA library are you using?
Best of luck everyone and a happy new year!
baz
-
@baz: Care to share the bruteforce code?
-
@baz I coded the simulated annealing using a combination of java, C (jni) and CUDA (http://www.nvidia.com/object/cuda_home.html) to use the graphics cards. The code itself is pretty simple so I did not need to use any third party library for the annealing.
-
@baz I put a more detail on my implementation in the comments for Chris Taylor's excellent blog post here http://crntaylor.wordpress.com/2009/12/10/17-x-17-challenge/
-
@kanodonkey, no problem, the (embarrassingly simple) code for searching and backtracking I put here: http://www.sti2.at/~barryb/four_colour.zip
It's Java and should be easy to import in to eclipse.
The search is done in the ExhaustiveSearch class. All I did was play around with different implementations of ColourOrderer and saved some interesting combinations, e.g. class Exp_16x20. Have fun!
-
(Sorry, that was a reply to Anonymous 112. @kanodonkey, I have been meaning to get in to this CUDA stuff, perhaps now is my chance)
-
Hello,
I am guessing that the majority of posters on this blog have never solved an NP-Complete computer science problem before.
I have published a solution to the "10 most point dense 5x5 Boggle boards" problem. Starting from any initial board, the best ten boards will arise during a run of DeepSearch.c on a quad-core running over night.
This kind of solution required 3 months focused effort.
Deep Search Documentation
As demonstrated, if a single non-monochromatic coloring exists, then many of them exist. Therefore, we are not searching for a global optimal value in the traditional sense.
THE UNDERLYING ALGORITHM PRINCIPLE:
Many roads lead to Rome, but when do we know that we are 1 step away from Rome?
It seems that there are 2 important metric values that belong to this problem...
1) The number of monochromatic rectangles.
2) The minimum number of positions to be erased for a partial solution.
Integrating these two values along with custom meticulous-record-keeping, to avoid cyclic-redundant behavior, will allow an adaptation of the DeepSearch.c framework to either find a working coloring, or provide solid evidence to call off the search.
Obviously, when altering one position in the coloring at a time, shortcuts can be taken to reduce the analysis time required. This is the segment that I am investigating right now.
Please contact me if you are serious about solving this problem,
logarithm69@hotmail.com
-
Ok,
I've now spent some time with the problem.
The program I am writing will find a coloring with zero monochromatic rectangles if any exist, and further, it will be finding it roughly over night.
If my program is unable to find the zero-coloring over night, the evidence will be so convincing to anybody who reads the WideSearch.c documentation that a reward of $289,000,000 will not convince any legit computer programmer to work on this problem.
The solution that I am developing is far from trivial, includes advanced data structures / algorithms, and is based on POSIX pthreads parallel batch processing.
An enormous number of 16x16 zero-colorings can be generated with a pencil, and a piece of paper.
Get back to me if you want progress reports:
logarithm69@hotmail.com
All the very best,
JohnPaul Adamovsky
-
I think that it would be nice to set up a clean place where everyone could put the best configuration he got, with a brief description of the method used - it is quite a pain to go through the hundreds of non-organized comments.
Does it sound doable ?
-
for those interested, I just set up a place where everyone can put the best result he obtained + brief description of the method:
http://linbaba.wordpress.com/17x17-challenge/
I hope to have nice chats about ways of attacking the challenge ...
-
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 17x17 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 16x16 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: 16x16 - 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 16x20 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 17x17 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 - 0123 X
* L = Last Row Number 17
Please do not give up hope just yet. If somebody would like to show me a 16x21 perfect 4-colouring, this might open the gates to the 17x17 perfect 4-colouring, because the 16x21 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 17x17 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 5x5 Boggle Boards - TWL06
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 17x17 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 16x16 perfect 4-Colouring. This represents a "Minimal Constraint Condition" for 16x16 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 16x16 grid, and trivial for a 16x20 grid.
T1 - Any 4-Colouring can only contain a maximum of 4 rows with nothing in common.
PROOF BY CONTRADICTION:
Proposition: A Perfect 17x17 4-Colourings Does Exist
Thus, this Colouring must contain a perfect 16x16 Colouring.
By T1, and demonstrated in above post, the Optimal 16x16 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 17x17 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
Get back to me please:
logarithm69@hotmail.com
-
Typo correction:
"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.
Replace *Colour* with "of each Colour".
It's 2 small words, and it doesn't sound as good, but it is correct.
I hope that this slip-up can be overlooked.
All the very best,
JohnPaul Adamovsky
-
Hello Gasarch,
Did you go to Law School?
It sounds like your unwillingness to pay out the imaginary $289 is a clear indication that you have never studied mathematics!
In simple Mathematics, a proof falls under only 2 categories:
1) VALID
2) INVALID
My proof, although the syntax does have typos, is logically airtight, and thus falls into category #1.
Please do the honorable thing, and pay out the Challenge Prize.
Without the $289, this so called Challenge is a lot of hot air. It's a novelty act, like Topo Gigio.
Mathematics, in its very nature is self-consistent, and thus not open to subjective interpretation. In other words, there is no room for debate using simple mathematics, and hence, it will never see the inside of a court room.
Given a valid proof, the honorable man must pay out the $289, in order to remain consistent.
Deciding not to pay the $289 for a VALID proof is what ultimately fails the "Reasonable Test".
Does that seem clear to you?
-
1) I have looked over your proof and I do not find it convincing.
2) You claim that a 4-coloring of 16x16 MUST have a certain form.
There are MANY 4-colorings of 16x16 with different forms.
I recommend that you use your computer programs to find a 16x16
that is NOT of that form. If you find one then you will know your
approach cannot work. If you do not find one then you can try to
make your approach work.
3) MANY people have worked on the problem using computers. I have not
kept any results secret. They have all posted on either my blog
(Probably THIS posting) or on Brian Hayes Blog of Dec 2, 2009.
4) I set it up so that only a VALID coloring gets the money to
avoid getting into lawsuits--- what if someone emailed me or posted
an incorrect proof that they insisted was correct.
And then sued for the money. Do we really want
the supreme court deciding on what a valid proof is?
(I don't think any of them have any mathematics training.)
GASARCH
-
JohnPaul,
I didn't go to Law School, but I do know how to read. Your proof states: "Therefore, A Perfect 17x17 4-Colourings Does NOT Exist." I will not comment on whether your proof is "VALID" or "INVALID." But if it is valid, as you claim it is, then you have proven that 17x17 is not 4-colorable.
Now refer back to Gasarch's original blog post:
What if 17x17 is not 4-colorable? Then nobody will collect the $289.00. Even so, if you find this out I would very much like to hear about it. I don't want to offer money for that since if your proof is a computer proof that I can't verify then its not clear how I can verify it. I also don't want to offer money for a reasonable proof since this may lead to having the Supreme Court decide what is a reasonable proof.
-
Hello Gasarch,
Here is a great idea...
You claim that 16x16 perfect colourings exist in many different forms, so why don't YOU produce some of these imaginary-fantasy-grids and elevate your comment from anecdotal jibber-jabber self-defense to something more scientific and systematic.
It is not my job to validate your weak comments.
You say that you have seen one, so produce it! Please!
If it does exist, I will work it into my proof because my humble intuition tells me that the logic is airtight. I certainly don't trust your intuition.
I am using my time to work on your problem, and not the other way around.
Let me show you a little magic-trick:
Your dear-boy, Rohan Puttagunta produced this 17x17 4-colouring with 4 monochromatic rectangles:
11112222333300000
12222333300011110
13332000311122220
10002111322233330
21233230030101231
22103321003210321
23013012012323011
20323103021032101
31300201131202312
32030310102113202
33120023113020132
30210132120331022
01021213232003123
02311302201312033
03201031210221303
00131120223130213
012301230123123+0
Flip some of the rows and columns, and what do we get? a 16x16 colouring with four sets of 4 rows with nothing in common. BOOM:
Does this look vaguely familiar to you, Gasarch?
0123012301230123 0
1230301223011230 0
2301123030122301 0
3012230112303012 0
0123123012301230 1
1230230130120123 1
2301012323013012 1
3012301201232301 1
0123230123012301 2
1230123001233012 2
2301301212300123 2
3012012330121230 2
0123301230123012 3
1230012312302301 3
2301230101231230 3
3012123023010123 3
0000111122223333 +
Sets A, B, C, and D are the same, and the beyond that, there is some superficial shuffling of relative locations.
AAAA 0
BDCB 0
CBDC 0
DCBD 0
ABBB 1
BCDA 1
CACD 1
DDAC 1
ACCC 2
BBAD 2
CDBA 2
DADB 2
ADDD 3
BABC 3
CCAB 3
DBCA 3
0123 +
Patterns do exist in the 16x16 perfect colourings.
Please show me the magical-mystery-imaginary 16x16 colourings with radically different formats to the one demonstrated in my proof, or just be a man and pay out the prize money.
$289 isn't going to ruin you, but it will save you from a competition that simple mathematics will not allow you to win. Also, being unemployed, I have 24 hours a day to work on this. It makes a lot of sense for you to just do the honorable thing here, and pay this man his money.
All the very best,
JohnPaul Adamovsky - TRUE until proven FALSE.
PS - No more superficial anecdotes please. Systematic, hard-evidence only.
Nobody cares whether a cheap-lazy-slob, with $289 to lose, is convinced by my proof. Mathematics is entirely self-consistent. There is no debate here, Gasarch. I win. Period.
-
JohnPaul Adamovsky:
INNOCENT until proven GUILTY.
TRUE until proven FALSE.
-
Gasarch,
You say:
"There are MANY 4-colorings of 16x16 with different forms."
Is this based on your keen scientific intuition?
Have you actually seen one? Were you awake at the time?
Work with me here, pal, I am trying to help you out, so please show us even just 1 16x16 perfect 4-coulouring with a different form than the one I use in my proof.
anecdotal: based on personal observation, case study reports, or random investigations rather than systematic scientific evaluation
Please at least show us your personal observations. I can't see inside of your head and I don't want to.
All the very best,
JohnPaul Adamovsky
PS - The 16x16 4-colouring in Rohan's example has four sets of four rows with nothing in common just like mine, and if your blog worked properly, it would be posted here.
-
I am making good progress in my attempt to enumerate all possible Perfect 16x16 4-colourings so as to complete my proof.
So far, any 16x16 4-colouring, which emerges from a 16x20 Perfect colouring with the "Apex Constraint Condition" will not fit into a 17x17 perfect colouring.
There is a good chance that all 16x16 Perfect colourings can be obtained in this manner, and hence my proof is complete.
Help out if you understand what I am trying to do.
All the very best,
JohnPaul Adamovsky
-
JohnPaul,
I'm having trouble following your quick proof sketch thing. Would you mind explaining the following further?
"Four sets of 4 rows with nothing in common is an absolute hard limit for a 16x16 perfect 4-Colouring."
If it's as simple as I believe it to be, could you explain why such a coloring is necessary as a basis for a valid 17x17 coloring?
Thanks,
Dumb Anonymous Reader
-
JohnPaul,
I think you deserve $289 just for the pure entertainment value of your posts. Thanks for brightening my day!
-
@JohnPaul Is there something special about 4, or does your argument show that (k+1)x(k+1) can never have a perfect k-coloring?
-
@Anonymous poster #133:
The special boundary cases of interest for k colors occur at dimensions (k^2+1)x(k^2+1).
5x5 - not 2-colorable
10x10 - 3-colorable
17x17 - ??
This brings up an interesting point for JohnPaul: You claim that a valid 4-coloring of a 17x17 grid requires a 16x16 subgrid of a specific form. If this is true, I would hazard to guess that it would also be true for a 3-coloring of a 10x10 grid - specifically, that it would need a 9x9 subgrid of the same restricted form.
Of course, if that were true, 10x10 would not be 3-colorable, but we know[1] it is.
So, to JohnPaul: What about your proof holds in the 17x17 case, but allows the 10x10 to remain 3-colorable under the same arguments?
[1] See slide 44 of Bill's Rectangle-Free presentation:
http://www.cs.umd.edu/~gasarch/papers/gridtalk.pdf
-
Hello Michael,
Thank you for pointing me to the Perfect 10x10 3-colouring.
My initial conjecture was that every Perfect (K^2)x(K^2) colouring was a subset of an "Apex Constraint" colouring.
Investigating the 10x10 colouring will certainly aid in my enumeration analysis.
I've got some thinking to do.
All the very best,
JohnPaul Adamovsky
-
The imaginary 17x17 Perfect colouring must contain within it, a 17x16 Perfect colouring with four independent sets of rows, which are missing at least one colour in common.
This is a much looser form than the one contained in my proof.
All the very best,
JohnPaul Adamovsky
-
Hello,
I could use some help here.
I have an idea, which I am fairly certain is a good idea:
The 17x17 grid search-space can be reduced to a static row and column, with a 16x16 dynamic grid.
Observe:
00000111122223333
0YYYYxxxxxxxxxxxx
0YYYYxxxxxxxxxxxx
0YYYYxxxxxxxxxxxx
0YYYYxxxxxxxxxxxx
1xxxxxxxxxxxxxxxx
1xxxxxxxxxxxxxxxx
1xxxxxxxxxxxxxxxx
1xxxxxxxxxxxxxxxx
2xxxxxxxxxxxxxxxx
2xxxxxxxxxxxxxxxx
2xxxxxxxxxxxxxxxx
2xxxxxxxxxxxxxxxx
3xxxxxxxxxxxxxxxx
3xxxxxxxxxxxxxxxx
3xxxxxxxxxxxxxxxx
3xxxxxxxxxxxxxxxx
I am thinking that any candidate 17x17 Perfect Colouring can be converted into this format using row/col switches, and colour flip-flops.
The "Y" positions can only take on 3 colours.
Please let me know if you have anything to add...
Along with my enumeration investigation, I am going to write a program that uses this format, along with massive pre-allocated arrays, and POSIX threads, which will hopefully start from a mono-colouring, and bounce around to colourings with the HARD-LIMIT minimum RANK. It will be extremely greedy, keep trie-compressed records, and have deviations confined to single rows to reduce the analysis time required.
All the very best,
JohnPaul Adamovsky - logarithm69@hotmail.com
PS - I've decided to solve this problem if it is possible, and there is a very good chance that it is possible.
Links to this post:
Weblog Home
Archives
