The most famous and intriguing problems in mathematics tend to be the ones that share two features. First they have been around for a really long time - which means that many people have tried to solve them and failed - and second they must be easy to explain. Curiously, they often lead to controversy - have they been solved or not? I want to describe two mathematical chestnuts that, on balance, mathematicians agree are solved. But...
|Pierre de Fermat|
Here's the problem:
|Kenneth Appel & Wolfganh Haken|
If you want to color a map in such a way that no two countries with a common border have the same color, then you only need four different colors. The problem was posed in 1852. Ten minutes playing around will convince you that this is so reasonable, it's obviously true. It took mathematicians until 1976 to come up with a proof, and even then...
|Four colors is enough for the US|
Of course the problem has no practical interest. Every real map is colored to distinguish the countries using plenty of colors. After all there is no shortage of them! And no one has ever come across a map requiring more than four colors anyway. In fact proving that five colors is enough is easy - usually included in undergraduate mathematics graph theory courses. But four?
Well, the proof was curious. The authors reduced the problem to a large number of different cases which required checking. A very large number. A number so large that it could only be checked by computer. They wrote the program, ran it, and the results were that all the cases checked correctly. So what's the problem? Well, a recent article in the Chronicle of Higher education suggests that only 20% of scientific programs are completely correct. So if you're checking millions of cases...well.
The proof has been replicated in other ways since then. But do we know if the original proof was correct? Maybe. Maybe not.
Michael - Thursday.