If it doesn’t work for the ocean, then the 4-color theorem is wrong, isn’t it?
It does work for the ocean, as long as you’re allowed to paint landlocked countries the same color as the ocean. And a sphere is similar enough to a plane that that also doesn’t cause any problems. You do, however, need more colors for a map on a torus (I think that takes 7).
Yeah, I was mistaken earlier.
It’s fairly simple to prove that a sphere (or an ellipsoid, or a cube, for that matter) is equivalent to a plane.
Yes. It annoyed the hell out of mathematicians that this was proven, when the case for a sphere or plane was not. It is, by the way, possible to create a map on a torus that needs seven colors with only seven “countries”.
If you require overseas territories[sup]1[/sup] of countries to be colored the same as the home country, then the Earth requires at least 5 colors. With this requirement, Belgium, France, Germany, Netherlands, and the ocean all have to be colored differently.
I don’t know any other set of countries that currently require 5 colors, but in the past there have probably been more cases. For instance, pre-unified 19th century Germany was an incredible hodgepodge of exclaves and enclaves which may have required 5 or more colors. I haven’t seen a good map of that region to say for sure, though.
[sup]1[/sup] Antarctic claims are ignored, of course.
Right, the four color theorem only applies to maps where each of the territories is one contiguous unit.
From a mapping perspective, oceans count as a sort of country in which all the others are enclaves. It’s surely a generalisation related to number of dimensions, but what? Is it D+2 or D*2 or D^2? What is the minimum number of colours to mark chunks inside a transparant object?
The 3D number is probably ℵ[sub]2[/sub] or greater. Infinite, at any rate. Essentially, the problem is only interesting in 2D (though the 2D may be embedded in a higher dimension).
In three dimensions, the right question is no longer so obvious, and that the answer is very sensitive to what question you ask. I don’t think we want to allow situations where an infinite number of countries touch each other, so let’s stick with a finite partition of a closed and bounded set.
In two dimensions, you’re limited to planar graphs, which you can think of as corresponding to maps where every country is connected. But you can draw a three-dimensional map where any arbitrary number of countries are connected, and so no matter how many colors you propose to be sufficient, there’s a map that needs at least one more. You can probably get a bound for the case where every country is convex, but I don’t know of any results in that area.
ETA: Forgot to mention, the dimension of the space is not sufficient to give an answer. The surface of a torus is a two-dimensional space, but you need seven colors there.
This is an excellent explanation of the proof. I wish these details were in the original article. Thanks.
That is an interesting question. I know of a case that requires at least six; can anyone find any higher?
Eight. I’ll spoiler my description, since everyone here loves a puzzle.
[spoiler]Start with a solid regular tetrahedron. From some thin material, cut four triangles with beveled edges that just fit over the tetrahedron, giving you four pieces that touch each other and touch the tetrahedron.
Next, place the original tetrahedron on the table balanced on one of its edges, and cut it in half horizontally. This gives you two pieces, each with five sides: two triangles, two parallelograms, and one square. (You’ve probably seen these shapes in the “make a pyramid” puzzle.) Place each piece with its square side down, then cut it in half with a vertical plane cut that divides in two all five surfaces. (Any cut that goes through the piece’s axis, and intersects the square along a side that touches a triangle, will do.) Each piece still touches all four surface pieces, and each of the other three interior pieces, so all eight pieces are in contact with every other piece.[/spoiler]
Nine or ten, but it’s progressively harder to describe, and the board ate my first attempt, so you’re getting the short version.
In the eight piece solution, there’s a vertical line running through the middle that is adjacent to each of the eight pieces. Change the last pair of cuts so that each face becomes angled, with the two resulting pieces touching over less than half the original face, and with a wedge between them removed. Assemble the inner tetrahedron with the wedges missing, and there’s a kite-shaped hole that runs vertically through it, where a ninth piece can be added that touches each of the other eight.
If these cuts are made vertical, there’s no way to cut the new piece in two such that each piece touches all the others, but from pictures I’ve drawn, I believe the cuts can be skewed a little bit, so that a single plane cut through the new piece will have a least a small bit of face touching each of the original eight, giving a total of ten pieces, all of which touch each other.
I think I see a way that requires nine, but it would be a real pain to describe and it sounds like ZenBeam already has me beat.
Here’s an illustration of my way of requiring nine colors. (Hopefully I didn’t mess it up.)
Start with a flat slab, and split it into four pieces as in the left most image. Each piece touches all the rest, so four colors are required.
Directly on top of this slab we can add a second slab, split into four convex pieces as shown in the middle image. (Notice the small green piece between the red and blue pieces, and also note that the red and blue pieces extend beyond the green piece so as to touch each other.) Each piece in the upper slab touches the other three in the upper slab and all four in the lower slab, so now four new colors are required, bringing the total to eight.
We can add a third slab directly below the original slab, as in the rightmost image. This slab touches all four pieces of our original slab. However, we want it to touch all four pieces of the top slab as well, so we change our original slab so that its top face is angled. That way, the pieces in our top most slab are slanted, and they can extend past the edge of the original (middle) slab to touch the bottom slab. [At first I was worried that the bottom slab might not be able to touch the small green piece, since it doesn’t extend as far. But if necessary we can make the top face of the brown bottom slab angled downwards after it extends past the original (middle slab), so that that the outer portion of the bottom slab is flush with the top slab.]