Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The 17x17 challenge. "Worth $289.00. This is not a joke."

blog.computationalcomplexity.org

Post reply on HN
Print view View original

41–50 of 78 posts

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#41

Post by brent »

RiderOfGiraffes wrote: post #18
brent wrote: post #14

Earlier quoted context omitted.

A related and unsolved question (and thus legitimate) could be: what is the smallest c such that 1000x1000 is c-colorable.

The problem with that is knowing that you have the minimum. The good thing about the question as asked is that it's asking for something specific and not a proof of impossibility. Your question is legitimate and interesting, but requires a proof of minimality. That's difficult.

> That's difficult

Agreed, but that is why it would be worth $1M :-).

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#42

Post by jules »

gort wrote: post #32

I'm not the most mathy person in the world; can someone explain to me the following statement: "Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17." If I've understood it correctly, OBS4 is the set of grid-sizes which are impossible. But if 17x17 were impossible, surely the bigger ones would be too? [Edit to answer my own question: the OBS4 set seems to be made up solely of the smallest such grid-sizes…

So if they say "Exactly one of a,b,c is in OBS4" then one of a,b,c is not 4-colorable?

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#43

Post by Retric »

xenophanes wrote: post #40
Retric wrote: post #38

Earlier quoted context omitted.

Ok, if you consider in on the logarithmic scale then it's almost meaningless, but the idea was: A) you don't need to innumerate every complete grid before eliminating them. B) How you count is important, if you just looked at the top row the boxing effect does not help and you have almost 2 * 3 * 4^14 options. PS: You can also cull some rotational summitry's from those 14 options before you start, but again that's on…

> you don't need to innumerate every complete grid before eliminating them. Of course. For large grids, I wonder if you can eliminate everything that doesn't have nearly equal amounts of every color.

Yes, though I would try an construct a 9x9 grid, and then try tacking on 3 valid 8x8 grids, then add the filler. My guess is larger grids are more constrained than working with smaller independent grids. Also you could store the extra grids as part of a larger data structure and work your way up to them by testing valid 2x2 grids, which are subset's a valid 3x3 grid etc.

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#44

Post by jrp »

jules wrote: post #42
gort wrote: post #32

I'm not the most mathy person in the world; can someone explain to me the following statement: "Exactly one of the following sets is in OBS4: 19x17, 18x17, 17x17." If I've understood it correctly, OBS4 is the set of grid-sizes which are impossible. But if 17x17 were impossible, surely the bigger ones would be too? [Edit to answer my own question: the OBS4 set seems to be made up solely of the smallest such grid-sizes…

So if they say "Exactly one of a,b,c is in OBS4" then one of a,b,c is not 4-colorable?

OBS4 is supposed to be a list of all configurations which deny 4-colorability for themselves, and any strictly larger (in both dimensions) configurations.

Ie, if (19,17) is in OBS4 then (19+x,17+y) is not 4-colorable either. So given a shape (x,y) or even a more funky collection of grid points like a triangle, to know if it's 4-colorable just check for all X in OBS4, if you can fit X inside your shape.

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#45

Post by jules »

jrp wrote: post #44
jules wrote: post #42

Earlier quoted context omitted.

So if they say "Exactly one of a,b,c is in OBS4" then one of a,b,c is not 4-colorable?

OBS4 is supposed to be a list of all configurations which deny 4-colorability for themselves, and any strictly larger (in both dimensions) configurations. Ie, if (19,17) is in OBS4 then (19+x,17+y) is not 4-colorable either. So given a shape (x,y) or even a more funky collection of grid points like a triangle, to know if it's 4-colorable just check for all X in OBS4, if you can fit X inside your shape.

Got it, although the more interesting property is that smaller shapes than those in OBS are 4-colorable? (because it is trivially true that if nxk cannot be colored then larger shapes can't either).

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#46

Post by JabavuAdams »

Retric wrote: post #34
xenophanes wrote: post #33

Earlier quoted context omitted.

counting there being less options b/c colors that aren't used yet are equivalent isn't going to get you very far. after all 4 colors are placed once it stops helping. also you're counting wrong. there are 2 or 3 options for the third square. 2 if the first 2 squares got the same color.

I was trying to point out that you can quickly eliminate 90% of the problem space so while I did forget about some summitry's my point still stands. Anyway looking at a 3x3 grid the box limitation is going to become increasingly important. Step 1: (1,x,x,x) Step 2: There are 2 meaningful options (1,1,x,x) and (1,2,x,x) because (1,3,x,x) is the same as (1,2,x,x). Granted only apply to the first 2x2 grid. Step 3: (1,1,…

See, that's the thing about really big numbers. 10% of 10^174 is still 10^173.

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#47

Post by scythe »

RiderOfGiraffes wrote: post #28

To summarise the numbers given elsewhere ... The number of possible 4-colorings of a 17x17 grid is 4^289 which is about 10^174, but that doesn't take into account the permutations of colors (4!) and possible symmetries. However, since almost all colorings have no symmetry that's largely irrelevant, so the number of colorings of the grid (up to permutations of colors) is about 4^289/24 which is about 4.122e172. Within…

I've got a script running right now that should be able to color everything by a sort of random walk. It colors around 230 nodes quickly and then slows down, so I suppose I'll find out soon enough.

edit: nah, at this rate it won't finish. source here for those interested; you probably just need to iterate over the remaining empty values in a more effective way than I am: http://ctrl-v.org/3708

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#48

Post by DarkShikari »

scythe wrote: post #47
RiderOfGiraffes wrote: post #28

To summarise the numbers given elsewhere ... The number of possible 4-colorings of a 17x17 grid is 4^289 which is about 10^174, but that doesn't take into account the permutations of colors (4!) and possible symmetries. However, since almost all colorings have no symmetry that's largely irrelevant, so the number of colorings of the grid (up to permutations of colors) is about 4^289/24 which is about 4.122e172. Within…

I've got a script running right now that should be able to color everything by a sort of random walk. It colors around 230 nodes quickly and then slows down, so I suppose I'll find out soon enough. edit: nah, at this rate it won't finish. source here for those interested; you probably just need to iterate over the remaining empty values in a more effective way than I am: http://ctrl-v.org/3708

I wrote a simple genetic algorithm in C, took about 30 minutes, but I suspect a break-it-down approach starting at small blocks and working up might work better.

It did 13x13 really fast but I have a hunch it might not work very well for 17x17...

( Link: http://pastebin.com/m51149dd9 )

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#49

Post by PieSquared »

nandemo wrote: post #29
PieSquared wrote: post #5

I know the professor who writes this blog, Bill Gasarch. I was thinking of interning with him (at our high school, we do an internship + report about it in our senior year), but then decided against it because the math is a bit too abstract and unapplicable to (as Gasarch would put it) make me "properly enthused". He seems like a great guy. Anyway, while I haven't read the entire thing, I would suggest reading the bo…

> but then decided against it because the math is a bit too abstract and unapplicable Combinatorics isn't really abstract as far as math goes. In fact some call it concrete mathematics .

Combinatorics isn't, but... coloring grids of squares?

Not that I really have anything against abstract mathematics. It's still very cool, but it's just not going to get me very excited - or at least this exact branch of it, I guess.

Re: The 17x17 challenge. "Worth $289.00. This is not a joke."

#50

Post by PieSquared »

hyperbovine wrote: post #39
PieSquared wrote: post #5

I know the professor who writes this blog, Bill Gasarch. I was thinking of interning with him (at our high school, we do an internship + report about it in our senior year), but then decided against it because the math is a bit too abstract and unapplicable to (as Gasarch would put it) make me "properly enthused". He seems like a great guy. Anyway, while I haven't read the entire thing, I would suggest reading the bo…

The opportunity to work directly with a university professor while still in high school is fantastic. Wish I'd had it. I hope you ended up taking advantage of it with someone else. Even if you're not totally absorbed in the research, this will give you a huge leg up when you reach college.

Living near the University of Maryland and NIST and etc, there really are a bunch of opportunities to work with professors and researchers in high school - it's really quite great. I hope (slash think, but knock on wood) that I'm going to be able to work with either another math professor or a theoretical physicist over the summer. :)
Post reply on HN