This work is licensed under a
Creative Commons License.
|
Wednesday, December 02, 2009
17x17: Comments on your comments
Posted by GASARCH
One of the comments on my last post, the 17x17 post, inquired if I am also interested in the other unknown grids (NOW just 17x18, 18x18,21x12, 22x10). I AM. In fact, Brad Larson emailed me a 4-coloring of 21x10. Here it is. He does not get $289.00 but he does get my eternal gratitude. (ADDED LATER: BRAD LATER GOT A 4-COL OF 21x11. I ADDED IT TO THE LINK THAT GAVE THE 21x10 COLORING. I WILL SOON UPDATE MY LAST POST ABOUT POSSIBLE OBSTRUCTION SETS, AND MY CHART.) (ADDED EVEN LATER: BRAD GOT A 4-COL OF 22x10 ALSO.)
One of my former high school students emailed me because he was excited that my 17x17 posting was picked up by another blogger: here Is that worth being excited about? Will it make me a celebrity? Will it get me on THE COLBERT REPORT or THE DAILY SHOW? I doubt it.
Many readers commented on my last post. These comments have lead to two corrections- my chart had typos, and the paper had a typo in an equation. The other objections raised were (I think) incorrect; however, I could be wrong. In THIS post I will answer all of the questions in the last post. If there are remaining questions, please post.
- The typos in the chart were fixed. THANKS for the corrections.
- The equation that Aaron Sterling pointed out was incorrect had a typo. THANKS Aaron. That should be fixed soon.
- The Obstruction set raised alot of questions. OBSc is NOT the set of all non-c-colorable grids. It is the set of all MINIMAL non-c-colorable grids. More precise: if nxm is in OBSc then nxm is NOT c-colorable but both (n-1)xm and nx(m-1) are c-colorable.
- Sky thinks 9,10,11 are in conflict. I corrected the chart so that may no longer be an issue, but if it is, please comment.
- Grid coloring is not related to coloring planar graphs. Grid coloring problems can be rephrased at hypergraph coloring problems. I doubt this is helpful, but I could be wrong.
- Why $289.00? Because 17x17=289. I originally thought I would offer $2.89 but Lance pointed out that that might not be enough to generate interest. Then I thought $28.90, but Lance again thought that would not get people interested. $289.00 seems just about right to get people interested but not break the bank of Gasarch. The person who won't give away the answer fo $289.00--- will you take $2.89 instead? How about $28.90?
- dut asks if the 74-sized Rect Free Subset is the smallest there is, or could there be one of sized 73. Actually we could just take out one element and get a 73-sized Rect Free Subset. I think dut meant to ask: in a 4-coloring do we know a number x such that no color appears less than x times? YES. Lets say (and this is true but probably can be improved) that there is no Rect Fres set of sized 80 of 17x17. Then the smallest possible number of times a color can appear can easily be lower bounded. li> One of the Anon posits that its impossible since this person thinks you can't have a 73-sized Rect Free Set. Alas, my original post had a 74-sized Rect Free Set. In fact, thats why I think you CAN 4-color 17x17. I look at it as a barrier result: All of the techniques to show a grid can't be c-colored used rect free sets. Hence 17x17 (and the others) will not be able to be proven not 4-colorable using our techniques. Hence new techniques are needed. Not quite as impressive as Oracles, Natural Proofs, or Algebraization.
- Scott claims that my claims are riddled with errors. Scott- please either point out an error or post that you are mistaken. Clearly the CHART was riddled with errors, but has been corrected.
- I agree with commenter after David Benson who would like to know what David Benson did. David Benson- please elaborate so we can see what you did and if its right.
10:09 AM
# 18 comments
-
Would you also give 298,00 if someone only gives a proof that such a coloring exists? Without giving an actual coloring?
-
Boo for nonconstructive proofs.
-
There is more reddit goodness here
http://www.reddit.com/r/programming/comments/a9mxh/the_17x17_coloring_challenge_worth_28900/
The haskell nearly solution is cool.
-
I could get $300 by selling my cock to ugly women, why should I do solve this instead?
A bigger challenge would be to come up with why this is useful. I offer $1000000 for a correct answer (hint: There are none, but don't let that stop you)
-
Given the 4-coloring of 21x10, results 5, 6, 7, and 8 can be collapsed down to: Exactly one of the following collections is in OBS_4: (22x10, 21x11), (23x10, 22x11, 21x12), or (23x10, 22x11, 21x13)
-
1) Anon 1: No. The reason I want a real coloring is that I can verify it and this avoids lawsuits. We would not want the supreme court determining whether a proof is correct.
2) The problem is useful because it will earn you
$289.00. Okay, Anon 4, pay up.
-
Man, you're a full professor. Don't be so cheap.
-
Anon 4, you can think of it as a scheduling problem:
Given m people, n rounds, and k activities. Is it possible to schedule all n rounds such that in each round, each of the m people does one of k activities and no two people do the same activity together more than once?
To give an example, asking if 17x17 is 4-colorable is the same as asking if 17 players can play 17 rounds of golf on 4 different holes such that no two players play the same hole together more than once.
-
we should reformulate the problem to investigate the reasons why a cheap full professor would be wanting to pay $289 for anybody else to do his job...
this is just like when teachers ask their students to model or code parts of a system that will be used in the teachers own research eventually.
this is really bad for academia in general. Never again propose such things, please.
-
Michael: No, it's not really equivalent to that. Though, it is equivalent to asking whether 289 golfers with four different colors of shirt can stand in a 17x17 grid such that no four golfers standing on the corners of an axis aligned rectangle all have the same shirt color.
If I can sneak a question past the trolls: Has anyone looked for a rotationally symmetric solution (minus the center point)? Is there some reason that I wouldn't expect to find such a solution?
-
Just to clarify: I mean that rotation by 90 degrees takes red to green, green to blue, blue to gold, and gold to red, except at the center.
-
Michael: Oh, you of course meant they can't play together twice on the same hole. Apologies for the sarcasm :)
-
Many hostile anonymous posters in this one. None of them have a valid point though, so that's good.
-
``this is just like when teachers ask their students to model or code parts of a system that will be used in the teachers own research eventually.''
While this is not true, the comment allows me to reiterate something: if someone emails me the 4-coloring of 17x17 they will get (1) CASH, unlike
the scenario above, and
(2) Acknowledment in the paper (perhaps unlike the scenario above),
(3) A chance for their own paper, WITHOUT me as a co-author, if they can crack a few more things.
I will also HELP such a person by proofreading their paper and, if need be, give them some background info.
-
"this is just like when teachers ask their students to model or code parts of a system that will be used in the teachers own research eventually"
Wrong. This is just like when Paul Erdos would offer bounties on problems he found interesting but couldn't solve himself.
-
the aggregation of comments in this post accumulates to aggravatingly annoying.
anyhow, a coloring does exist. but since only 289 dollars are at stake, i better take it away and publish it myself.
Bill might be disappointed but then again, don't pose such a bounty. see for 2890.00 dollars you'd get a hell of a lot more momentum. last time i talked to erdoes he told me that if we were to take inflation into account, reasonable amounts/bounties would start in the thousands nowadays.
-
Mr Re-Fuse, if you are serious,
which I doubt, recall that my original post said that you COULD publish it WITHOUT me and still get the money.
-
Sup Mr. Refuse. Long time no see. If you submit the solution, I'll cover the $2601 difference. See ya round,
JB
Links to this post:
Weblog Home
Archives
