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.
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.
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.
There is something like 12, valid 2x2 grids, and you can get rid of almost another (17!)^2 options because rows and columns are interchangeable. Actually thinking about it a little bit the only valid option for the top left square is:
0,0
0,1
However, the vast majority of the grids are eliminated by the boxing constriant before the grid get's all that large.
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)
It's no where near 10^173 because of the box limitations. Adjusting for summitry's there are 12 (or less) 2x2 boxes. But then building a 3x3 box, the total is not 12 * 4^5 possible because at least 4 * 12 of them are eliminated by the boxing constraint. It's more than that but I am not doing this by hand.
The reason you can't crack RSA is because after skipping composite numbers and small primes you cant further reduce the search space. Don't forget 20x20 box is known to not be solvable and the 16x16 box has at least one known solution.
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.
Yes, though I would try an construct a 9x9 grid, and then try tacking on 3 valid 8x8 grids, then add the filler. My guess is larger grids are more constrained than working with smaller independent grids. Also you could store the extra grids as part of a larger data structure and work your way up to them by testing valid 2x2 grids, which are subset's a valid 3x3 grid etc.
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
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...
This is a class of problems that Monte Carlo optimization (GA's, simulated annealing, etc.) typically can't solve, because almost-solutions are generally really deep local minima that the search machinery can't climb out of.
I made some tweaks (and a bug fix or two), left it running overnight (four instances, one per CPU core)... They all get down to 12 to 14, but it seems like they stop progressing. Haven't seen 11 yet.
It's not pretty, but I did a few things. Instead of taking the top n candidates and breeding them randomly, I kept all of them (NUM_STATES 200 and KEPT_STATES 200), but weight them according to score. So the best scores have the highest chance of passing their DNA down to the next generation, but the occasional loser gets lucky too.
Mutation is also weighted, so the most likely number of mutations is zero, but it's possible to have up to 4. Increasing this value made the performance go down, but it's also possible that there is no way to get to a solution by incrementally tweaking a decent attempt. Which could explain why I'm stuck at 12.
There are a few optimizations that may or may not make a difference, for instance in the scoring function. I think the pick_best_states function was not actually picking the best states. If you had two states with the same score, the first one is kept, but the next one is not. I fixed this. The stupid thing is, with NUM_STATES and KEPT_STATES at 200, it's basically an n^2 sort now. I never bothered to improve that.
I'm not sure minimizing the score (at least, until you get to 0) is interesting, but anyway, I wrote a simple hill-climbing-with-random-perturbation routine and let it run over and over for the last couple of days. So far my best has a score of 10:
Something that might help would be to have the grids in some sort of canonical form: as swapping rows and columns doesn't change the score, for every configuration there is a reordering such that the whole grid value is minimal (i.e. if we read out as a 279 digit number). Intuition says that if grids were brought in such a canonical form, recombination might work better.
I've got 67 just using random placements with heuristics, programmed in Python. Apparently they've got 73 (which is 289/4 rounded up), and that's why they think this might be possible.
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.
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.
I'm not one to say that coloring grids of squares sounds fascinating to me, but nandemo's point still holds -- as far as mathematics goes, it's pretty concrete.
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.
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. :)
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?)
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.]
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.
Got it, although the more interesting property is that smaller shapes than those in OBS are 4-colorable? (because it is trivially true that if nxk cannot be colored then larger shapes can't either).
Right, he has apparently solved and proved a short list for OBS3 with the property that X is 3-colorable if and only if X doesn't contain anything from OBS3.
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.
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.
A different question would be "who can come up with the smallest c in 6 months", which probably wouldn't yield the true answer, but for a $1M prize it might come quite close (and could lead to some interesting theoretical advancements).
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.)
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?
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.
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.
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.
> 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).
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:
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.