tag:blogger.com,1999:blog-3722233.post6494900245340663627..comments2020-04-04T11:22:04.819-04:00Comments on Computational Complexity: 17x17: Comments on your commentsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-91989510199327166242012-02-08T08:25:00.684-05:002012-02-08T08:25:00.684-05:00THE PROBLEM HAS BEEN SOLVED.
See my Feb 8, 2012 p...THE PROBLEM HAS BEEN SOLVED. <br />See my Feb 8, 2012 post.<br /><br />They are publishing a paper WITHOUT ME which is absolutely fine.<br /><br />They were happy to work on it.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69987268550115454662009-12-03T23:59:53.240-05:002009-12-03T23:59:53.240-05:00Sup Mr. Refuse. Long time no see. If you submit ...Sup Mr. Refuse. Long time no see. If you submit the solution, I'll cover the $2601 difference. See ya round,<br /><br />JBJimbob Erdoesnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85143860506111164002009-12-03T23:15:04.438-05:002009-12-03T23:15:04.438-05:00Mr Re-Fuse, if you are serious,
which I doubt, rec...Mr Re-Fuse, if you are serious,<br />which I doubt, recall that my original post said that you COULD publish it WITHOUT me and still get the money.gasarchnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28641435408931819612009-12-03T21:05:56.364-05:002009-12-03T21:05:56.364-05:00the aggregation of comments in this post accumulat...the aggregation of comments in this post accumulates to aggravatingly annoying.<br /><br />anyhow, a coloring does exist. but since only 289 dollars are at stake, i better take it away and publish it myself.<br /><br />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-Fusenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83984672605946350542009-12-03T18:20:42.694-05:002009-12-03T18:20:42.694-05:00"this is just like when teachers ask their st...<i>"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"</i><br /><br />Wrong. This is just like when Paul Erdos would offer bounties on problems he found interesting but couldn't solve himself.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65893311260390395442009-12-03T12:24:21.419-05:002009-12-03T12:24:21.419-05:00``this is just like when teachers ask their studen...``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.''<br /><br />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<br />the scenario above, and<br />(2) Acknowledment in the paper (perhaps unlike the scenario above),<br />(3) A chance for their own paper, WITHOUT me as a co-author, if they can crack a few more things.<br />I will also HELP such a person by proofreading their paper and, if need be, give them some background info.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70746145040032396602009-12-03T11:31:48.776-05:002009-12-03T11:31:48.776-05:00Many hostile anonymous posters in this one. None ...Many hostile anonymous posters in this one. None of them have a valid point though, so that's good.The Ubiquitous Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8132954456851560472009-12-03T11:23:44.121-05:002009-12-03T11:23:44.121-05:00Michael: Oh, you of course meant they can't p...Michael: Oh, you of course meant they can't play together twice on the same hole. Apologies for the sarcasm :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88104448339455608342009-12-03T11:05:53.913-05:002009-12-03T11:05:53.913-05:00Just to clarify: I mean that rotation by 90 degre...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31776307924283246152009-12-03T10:51:32.876-05:002009-12-03T10:51:32.876-05:00Michael: No, it's not really equivalent to tha...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.<br /><br />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?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8599874404180943532009-12-03T06:41:57.778-05:002009-12-03T06:41:57.778-05:00we should reformulate the problem to investigate t...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...<br /><br />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.<br /><br />this is really bad for academia in general. Never again propose such things, please.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49303421603838385462009-12-02T16:16:16.460-05:002009-12-02T16:16:16.460-05:00Anon 4, you can think of it as a scheduling proble...Anon 4, you can think of it as a scheduling problem:<br /><br />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?<br /><br />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.Anonymoushttps://www.blogger.com/profile/11976987929795854783noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75578186979320263182009-12-02T15:09:15.127-05:002009-12-02T15:09:15.127-05:00Man, you're a full professor. Don't be so ...Man, you're a full professor. Don't be so cheap.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60041352676136732652009-12-02T13:39:37.399-05:002009-12-02T13:39:37.399-05:001) Anon 1: No. The reason I want a real coloring i...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.<br /><br />2) The problem is useful because it will earn you<br />$289.00. Okay, Anon 4, pay up.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28711929940798701612009-12-02T13:38:47.437-05:002009-12-02T13:38:47.437-05:00Given the 4-coloring of 21x10, results 5, 6, 7, an...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)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31276127994715715112009-12-02T12:02:23.847-05:002009-12-02T12:02:23.847-05:00I could get $300 by selling my cock to ugly women,...I could get $300 by selling my cock to ugly women, why should I do solve this instead?<br /><br />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)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62830086559391556532009-12-02T11:43:44.586-05:002009-12-02T11:43:44.586-05:00There is more reddit goodness here
http://www.redd...There is more reddit goodness here<br />http://www.reddit.com/r/programming/comments/a9mxh/the_17x17_coloring_challenge_worth_28900/<br /><br />The haskell nearly solution is cool.Iamreddavehttps://www.blogger.com/profile/02768287658329807075noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58784077803561936852009-12-02T11:26:18.640-05:002009-12-02T11:26:18.640-05:00Boo for nonconstructive proofs.Boo for nonconstructive proofs.Davidnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73689706333521470262009-12-02T11:21:44.590-05:002009-12-02T11:21:44.590-05:00Would you also give 298,00 if someone only gives a...Would you also give 298,00 if someone only gives a proof that such a coloring exists? Without giving an actual coloring?Anonymousnoreply@blogger.com