Writing

Feed Software, technology, sysadmin war stories, and more.

Wednesday, July 4, 2012

Fiddling with that four color theorem

Have you ever found some ancient paper from your grade school days and applied your current knowledge to it? That which used to be considered ordinary might now seem kind of interesting. It's all a matter of appreciating the context of what was really going on, and you can only get that through experience.

In my case, I found an old notebook from around 7th grade which had a bunch of odd little scribbles in it. It took me a little while to figure out what had been going on. All of the scribbles were a series of different shapes, all labeled 1 through 4. There might be many shapes within any given blob, but no numbers went above 4.

After staring at it for a little bit, it started coming back to me. That year, my math teacher had apparently dropped some kind of aside on us which was "you only need four colors for a map". This is that whole thing where no matter how you bend the regions around, you won't be able to force yourself to need a fifth, assuming your goal is to not have two same-colored countries meet.

I think he threw in a note that crossing at a diagonal didn't count, so that particular trick evaporated quickly. Still, this seemed wrong to me. There had to be a way around this... but how?

I went through bunches of iterations, apparently while my math class went on to whatever else they were doing. The scribbles were all over the place. I think this went on for several days, even. Sometimes, I'd get some half-baked idea and would try to sketch it only to fail again and again.

Then, one day, something changed. I guess I had a full sheet of notebook paper out and started thinking about it in terms of it being more like a planet. In other words, my map drawings would be happening on a globe instead of just an empty space on a flat piece of paper. I mean, these flat maps are really representing something which is more or less spherical, right?

What did this change? Well, now, anything that went off the left side could "come back" on the right side, sort of like those tunnels in Pac-man. Did this change anything? Well, no, but it did mean that I no longer needed to waste a number just to cover the left and right sides of my paper since those could now be the same "country". Even though that "wraparound" was useful, it still didn't help. I couldn't make that fifth color appear.

Somehow, after staring at this for a while, it came to me. Perhaps using an actual loose sheet of paper instead of something in a spiral notebook or still in my binder helped. I picked it up and rolled it into a tube, and noticed what happened. I still had my sphere-like "off one side and back on the other" thing going on, but now I picked up this crazy "off the top and reappear at the bottom" thing too!

With this wild new trick, it was possible to blow past the 4 color requirement. This made sense to me. It was like I had gotten inside the problem and had rewritten it in my own personal language. As I have since learned, it takes far more colors if you happen to live on a planet shaped like a donut. Homer Simpson would be proud.

Apparently all of this is old news, but nobody told me that at the time. I only know that now thanks to resources like Wikipedia.

That was probably the last random theoretical thing from math class I bothered to chase down. Everything after that point just got more and more abstract and even more pointless. Besides, if I couldn't restate something in my own terms, what hope could I have of truly understanding it?