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

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.

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

#5

Post by PieSquared » Mon, Nov 30, 2009, 9:36 PM UTC

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 book he has online - it's quite interesting, and it goes into more detail about colorings and such, so anyone who likes this post will find the book interesting as well.

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

#6

Post by RiderOfGiraffes » Mon, Nov 30, 2009, 9:40 PM UTC

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.

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

#7

Post by bshep » Mon, Nov 30, 2009, 9:41 PM UTC

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

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

#8

Post by jrp » Mon, Nov 30, 2009, 9:46 PM UTC

bshep wrote: post #7

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

Did you read the article? These are actually quite different.

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

#9

Post by RiderOfGiraffes » Mon, Nov 30, 2009, 9:47 PM UTC

bshep wrote: post #7

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

I'm pretty sure you haven't understood the problem. It's really nothing to do with the 4CT.

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

#10

Post by cperciva » Mon, Nov 30, 2009, 9:47 PM UTC

bshep wrote: post #7

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

The 4 colour theorem is about colouring an arbitrary planar graph such that adjacent vertices have different colours.

The problem posed here is about colouring a 17x17 grid such that there is no monochromatic rectangle.

These problems have nothing in common aside from the word "colouring" and the number "4".