What was the first math problem that we needed a computer to solve?

Illustration for article titled What was the first math problem that we needed a computer to solve?

In the 1970s, a remarkable thing was done; a computer was used to solve a math problem. This, in and of itself, was not remarkable. The difference engine could do it. But this problem was the first one that would probably remain unsolved if it weren't for computers. Find out about the Four-Color Theorem, and why it needed to be turned over to the machines, below.


Hey. What's one hundred and seventeen thousand six hundred and twenty-two plus three million, four hundred and fifty thousand and twelve?

You just opened up the calculator function on your computer, didn't you?

Hey. There's no shame in that. I'm not even going to solve the problem, and I'm the one who wrote it. I'm just saying that we're used to turning over even relatively easy problems to computers. (Look. Someone programmed that calculator function. If you waste paper trying to figure it out, you're squandering their hard work.)

Even during the 1970s, when computers were harder to come by and problems were weightier, computers were routinely brought in to solve things for the people who had access to them. But prior to 1976, they weren't required to prove any math problem. They just made things easier. That is, until Kenneth Appel and Wolfgang Haken used a computer to prove a 124-year-old conjecture. In 1852, Francis Guthrie came up with what's known as the Four-Color Theorem. That theorem stated that no map needed more than four colors to delineate territories. Generally, different countries, states, or provinces, were given different colors on a map. If a mapmaker were armed with four different colors, there was no territory, or set of them, that could be arranged in such a way that two adjoining territories were the same color.

No one had found anything to contradict Guthrie, but then no one had the time to check. Thousands of different cases would have to be tested before anyone could come to a conclusion. The theorem just wasn't practically testable, and so not provable, by humans. In 1976, though, a human didn't need to work through all those cases. Appel and Haken enlisted the help of a machine that worked fast and didn't mind if its time was being wasted, and proved the Four-Color Theorem. Mapmakers raised a bored eyebrow and continued to use however many colors they felt like using. Computer scientists, though, were impressed.

Image: LR

Via The Mathematical Association of America




A few thoughts:

1) Did they use the number of countries when the theorem was first posed or the number of countries in 1976? How about the number of countries now? Would it make a difference?

2) Couldn't someone just play around with a map and some crayons and come up with the same solution or is that considered too tedious? Might be a good project for your fifth grader.

3) And speaking of school projects, this would have been good to know about when we had to make maps of Europe and Asia in middle school. I used a lot of colors for those (but I still have them because I'm rather proud of the work I did).