3 ms·
This was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem http://en.wikipedia.org/wiki/Four_color_theorem
by bshep 17y ago
This was proven in 1976 - http://en.wikipedia.org/wiki/Four_color_theorem http://en.wikipedia.org/wiki/Four_color_theorem
- jrp 17y agoDid you read the article? These are actually quite different.
- RiderOfGiraffes 17y agoI'm pretty sure you haven't understood the problem. It's really nothing to do with the 4CT.
- cperciva 17y agoThe 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".
- Dove 17y agoThe 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.)
- bshep 17y agoI 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?
- Dove 17y ago4^(17x17). I think that's quite a few. Your mileage may vary based on the force available to you for bruting.
- deleted 17y ago[deleted]
- joeld42 17y agoWhat 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.
- cperciva 17y agohow 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?
- rms 17y agoHold on, let me check my other universe.
- RiderOfGiraffes 17y agoUm, 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.
- cperciva 17y agoHe asked how many grids there were, not how many rectangles there were. :-)
- 17y ago
- nollidge 17y agoThat'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.
- Dove 17y agoNote 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 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.
- nollidge 17y agoOf 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.