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

11–20 of 78 posts

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

#11

Post by Dove »

bshep wrote: post #7

This was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem

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 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.

(To be fair, I made the same mistake on a first reading of the problem.)

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

#12

Post by nollidge »

bshep wrote: post #7

This was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem

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.

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

#13

Post by Dove »

nollidge wrote: post #12
bshep wrote: post #7

This was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem

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.

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

#14

Post by brent »

RiderOfGiraffes wrote: post #6
rauljara wrote: post #4

Took me a second to realize why 289. 17 * 17. One dollar per square. If you could get him to offer a prize for a 1000 * 1000 grid, you have quite a nice reward.

You're not being serious, I know, but I'll answer seriously anyway. 1000x1000 is not an edge case - it can't be done - so offering a reward for a solution is pretty pointless.

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

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

#15

Post by bshep »

Dove wrote: post #11
bshep wrote: post #7

This was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem

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?

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

#16

Post by Dove »

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?

4^(17x17).

I think that's quite a few. Your mileage may vary based on the force available to you for bruting.

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

#17

Post by cperciva »

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?

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?

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

#18

Post by RiderOfGiraffes »

brent wrote: post #14
RiderOfGiraffes wrote: post #6

Earlier quoted context omitted.

You're not being serious, I know, but I'll answer seriously anyway. 1000x1000 is not an edge case - it can't be done - so offering a reward for a solution is pretty pointless.

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.

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

#19

Post by rms »

cperciva wrote: post #17
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?

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?

Hold on, let me check my other universe.

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

#20

Post by RiderOfGiraffes »

cperciva wrote: post #17
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?

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.
Post reply on HN