Friday, January 8, 2010

Coloring a donut

Let's say that we have a map which is split into many different regions. We want to color each region such that no two regions of the same color share a border. It has been proven that only four distinct colors are required, no matter what the map is.

There are two parts to the proof:
  1. Some map requires at least four colors.
  2. No map requires more than four colors.
Part 2 is complicated! It required computer assistance to check over a thousand cases.

But part 1 is easy. Here is one such map.

One of the assumptions of this theorem is that the map is on a flat plane. But what if we have a map on a donut's surface? It turns out that we need seven colors. Can you find a map on a donut that requires at least seven colors?

You can send solutions to skepticsplay at gmail dot com. A tip: you can represent a donut with a flat square in which each edge wraps around to the opposite edge.

solution posted


Eduard said...

It is difficult to not find immediatly an answer in Google. So I didn't have a chance to find myself. An oblique tiling with hexagons does the job.

miller said...

True, this is one puzzle which is easy to google. If you want more, you can also try to prove that a mobius requires six colors (but don't google it).

Eduard said...

I tried, but then I googled. There is much less info about the six colored mobius. I miss especialy a 3D turnable model (as the NON-6-colored mobius on the wolfram page).
The 6-colored mobius in tissue is not satisfying.

Secret Squïrrel said...

I just sent you a map which I think meets the criteria. Then I came here and see that a hex map works. Looking at mine again, I think it's topologically similar but I drew it in Paint so it's all R angles.

I'll have a look at the Moebius later.

miller said...

I haven't received any e-mails from you. You might have to resend.

Eduard said...

I made a 6-color-Mobius model with paper. I had to print "both sides". One with the mirror image. Because a mobius strip is not orientabel his thickness must be zero and "both sides" must locally have the same color. I send a photo of my model.