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

http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html

by sp332 • 17 years ago

87 72 17 years ago

blog.computationalcomplexity.org

rauljara• 17 years ago

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.

RiderOfGiraffes8• 17 years ago

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.

brent2• 17 years ago

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

PieSquared4• 17 years ago

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.

nandemo• 17 years ago

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

PieSquared4• 17 years ago

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.

ahn• 17 years ago

>Combinatorics isn't really abstract as far as math goes.

Huh? Is it naturally abstract?

hyperbovine• 17 years ago

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.

PieSquared4• 17 years ago

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

mshafrir2• 17 years ago

magnet program?

PieSquared4• 17 years ago

Yup, it's the Montgomery Blair High School Magnet Program - it's in Silver Spring, Maryland. The funding cuts are kind of hurting it, but it's a very good education, especially if you put your own effort into it too.

(Are you, perhaps, somehow associated with this or another magnet program in the MD area?)

bshep2• 17 years ago

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

jrp3• 17 years ago

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

RiderOfGiraffes8• 17 years ago

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

cperciva3• 17 years ago

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

Dove3• 17 years ago

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

bshep2• 17 years ago

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?

nollidge2• 17 years ago

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.

Dove3• 17 years ago

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.

RiderOfGiraffes8• 17 years ago

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.

Retric6• 17 years ago

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.

xenophanes3• 17 years ago

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.

RiderOfGiraffes8• 17 years ago

Although this succeeds in eliminating 90% of the search space for a 2x2 grid (and even then I think your sums are slightly wrong) this doesn't even dent the 17x17 case. The 2x2 square in the top left of that only has 23 (or fewer) configurations, but now you can probably no longer permute the colors. The savings are irrelevant in the larger cases.

Besides, to some extent you are preempting the problem. You've counted the number of colorings of the 2x2 grid and found there to be only a small number. The evidence suggests that the number of colorings of the 17x17 grid is either 1 or 0 (up to permutation of colors), but that doesn't mean the search is trivial.

I may not have expressed that clearly, but I hope I've conveyed the point.

abentspoon2• 17 years ago

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.

scythe2• 17 years ago

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

DarkShikari4• 17 years ago

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 )

ars• 17 years ago

Is the problem basically this game? http://www.kongregate.com/games/Mygame/blocky

i.e. find a grid where you can not make any moves in the game?

dkasper• 17 years ago

Yes

gort• 17 years ago

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

jules2• 17 years ago

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

jrp3• 17 years ago

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.

patrickgzill• 17 years ago

Given the difficulty, should he not be offering more?

cellis• 17 years ago

I think the cash is more symbolic than anything.

See: http://en.wikipedia.org/wiki/Knuth_reward_check

charlesju• 17 years ago

Darn it. I thought this was a huge In & Out burger or something. I guess a math game is more logical and fitting for this forum.

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

Related Stories