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

21–30 of 78 posts

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

#21

Post by paulgb »

bshep wrote: post #15
Dove wrote: post #11

Earlier quoted context omitted.

The problem isn't what you think it is, otherwise the solution would be trivial: alternate one pair of colors on even rows, and then alternate another pair on odd rows. That satisfies the four color theorem. This problem differs in two ways. First, we're not looking for all of the vertices to be different colors. We're looking for them to not all be the same color. This is easier to do. Second, he's not trying to col…

I see now! I completely missed this part: "Second, he's not trying to color a simple planar graph. He means every rectangle on the grid -- for example, a 7 x 8 rectangle in the middle somewhere. This is much, much harder to do." Otherwise the problem seemed trivial. On the other hand... how many possible 17x17 4-colored grids are there? Can this be brute forced?

> On the other hand... how many possible 17x17 4-colored grids are there? Can this be brute forced?

4^(17*17) ~= 10^173.. a bit too many to brute force, but I'm sure you could narrow the number down a lot with simple heuristics (though it would still be too large to brute force).

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

#22

Post by cperciva »

RiderOfGiraffes wrote: post #20
cperciva wrote: post #17

Earlier quoted context omitted.

how many possible 17x17 4-colored grids are there? There's 289 points on the grid, and 4 options for each. So... 2^578 options. Can this be brute forced? That depends. Do you have a kilobit quantum computer available?

Um, no. The rectangles are aligned with the X and Y axes, so you choose two rows and two columns, giving 17C2x17C2 rectangles in total: 23409 possible rectangles.

He asked how many grids there were, not how many rectangles there were. :-)

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

#23

Post by [deleted] »

Dove wrote: post #16
bshep wrote: post #15

Earlier quoted context omitted.

I see now! I completely missed this part: "Second, he's not trying to color a simple planar graph. He means every rectangle on the grid -- for example, a 7 x 8 rectangle in the middle somewhere. This is much, much harder to do." Otherwise the problem seemed trivial. On the other hand... how many possible 17x17 4-colored grids are there? Can this be brute forced?

4^(17x17). I think that's quite a few. Your mileage may vary based on the force available to you for bruting.

[deleted]

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

#24

Post by RiderOfGiraffes »

cperciva wrote: post #22
RiderOfGiraffes wrote: post #20

Earlier quoted context omitted.

Um, no. The rectangles are aligned with the X and Y axes, so you choose two rows and two columns, giving 17C2x17C2 rectangles in total: 23409 possible rectangles.

He asked how many grids there were, not how many rectangles there were. :-)

Ah - sorry, my turn to do a misreading. As you point out, I computed the number of rectangles that aren't permitted to have all its vertices the same color.

My bad - sorry.

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

#25

Post by nollidge »

Dove wrote: post #13
nollidge wrote: post #12

Earlier quoted context omitted.

That's not the same problem. This refers to a grid (not a map) of colored points (not regions), colored with 4 colors (at least in this case) in which a rectangle with four same-colored points cannot be found.

Note that the second distinction you made is actually trivial. Coloring the vertices of a planar graph is the same problem as coloring the regions of a different planar graph. The graphs are duals: http://en.wikipedia.org/wiki/Dual_graph In this case, the dual of a grid is a grid. So at least that part of it would be the same problem. The other distinctions are true, though.

Of course you are right. I guess I pictured the 17x17=289 points forming 16x16=256 squares, which is why I felt it necessary to make the distinction.

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

#26

Post by [deleted] »

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.

[deleted]

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

#27

Post by joeld42 »

Dove wrote: post #16
bshep wrote: post #15

Earlier quoted context omitted.

I see now! I completely missed this part: "Second, he's not trying to color a simple planar graph. He means every rectangle on the grid -- for example, a 7 x 8 rectangle in the middle somewhere. This is much, much harder to do." Otherwise the problem seemed trivial. On the other hand... how many possible 17x17 4-colored grids are there? Can this be brute forced?

4^(17x17). I think that's quite a few. Your mileage may vary based on the force available to you for bruting.

What a neat problem. I hadn't seen this before.

You don't need quite that many -- you could test 2^289 (and you can probably skip many of them) and look for the "rectangle free subsets" that he mentions in the slides, and then just look for four of them that don't overlap. Still gonna take eons.

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

#28

Post by RiderOfGiraffes »

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 the 17x17 grid we must avoid X-Y-aligned rectangles with corners all the same color. The number of such rectangles is obtained by choosing two rows and two columns, and so is (17choose2)x(17choose2) = 23409.

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

#29

Post by nandemo »

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.

Post reply on HN