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

31–40 of 78 posts

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

#31

Post by Retric »

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…

This is also more brute forcible than 4^289 might suggest. Consider a 2 x 2 grid. The first square does not count, there are 2 options for the second square, and 3 for the 3rd. But there is only 4 options for the fourth square if the first 3 squares where not the same color. Resulting in (2 * 3 -1) * 4 + 3 = 23 options not 4^ 4 = 256.

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

#32

Post by gort »

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 that can be given without being redundant.]

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

#33

Post by xenophanes »

Retric wrote: post #31
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…

This is also more brute forcible than 4^289 might suggest. Consider a 2 x 2 grid. The first square does not count, there are 2 options for the second square, and 3 for the 3rd. But there is only 4 options for the fourth square if the first 3 squares where not the same color. Resulting in (2 * 3 -1) * 4 + 3 = 23 options not 4^ 4 = 256.

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.

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

#34

Post by Retric »

xenophanes wrote: post #33
Retric wrote: post #31

Earlier quoted context omitted.

This is also more brute forcible than 4^289 might suggest. Consider a 2 x 2 grid. The first square does not count, there are 2 options for the second square, and 3 for the 3rd. But there is only 4 options for the fourth square if the first 3 squares where not the same color. Resulting in (2 * 3 -1) * 4 + 3 = 23 options not 4^ 4 = 256.

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,1,x), (1,1,2,x), (1,2,1,x), (1,2,2,x), (1,2,3,x)
  Step 4: (1,1,1,2), (1,1,2,1), (1,1,2,2), (1,1,2,3), (1,2,1,1), (1,2,1,2), (1,2,1,3), (1,2,2,1),(1,2,2,2),(1,2,2,3), (1,2,3,1),(1,2,3,2),(1,2,3,3),(1,2,3,4)
So 14 options.

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

#35

Post by xenophanes »

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,…

how does it stand? you have given no argument this will make a substantial reduction when the grid size is much larger than the number of colors

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

#37

Post by abentspoon »

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…

You are also free to interchange rows and columns.

This should reduce the number of possible grids by a factor of (17!)^2, leaving 3.25e143 colorings.

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

#38

Post by Retric »

xenophanes wrote: post #35
Retric wrote: post #34

Earlier quoted context omitted.

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,…

how does it stand? you have given no argument this will make a substantial reduction when the grid size is much larger than the number of colors

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 only important if you are trying to actually calculate it.

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

#39

Post by hyperbovine »

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.

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

#40

Post by xenophanes »

Retric wrote: post #38
xenophanes wrote: post #35

Earlier quoted context omitted.

how does it stand? you have given no argument this will make a substantial reduction when the grid size is much larger than the number of colors

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.

Post reply on HN