Real Mathematics : Graph Theory
There is precious little mathematics being done in the public schools. Mathematics doesn't consist of determining whether 122, 357, and 1005 can form the sides of a right triangle, or using the quadratic formula to find the solutions of the equation 2x2 + 31x - 4 = 0. It involves discovering facts and proving that they are facts. So let's take a look at a problem I have several times used to introduce people to mathematics.
This puzzle was common when I was a child, and I remember one of my elementary school teachers remarking that it was popular when she was a child. You draw a square with an X connecting opposite corners:
 |
The object of the puzzle is to draw that figure without lifting one's pencil from the page or retracing a line. We were all convinced that it couldn't be done. Here I want to do it, or prove that it can't be done. And at this point, the budding young (or old) mathematician will spend a few minutes trying to draw it, to get a feel for the problem and how it might be approached. |
If no brilliant ideas come to mind — and for me, brilliant ideas are not common — then we can always fall back on brute force. Let's consider how we'd test every single path. First, do we have to try every path starting at every corner? No, obviously not; if we try every path starting from one corner, those starting at the other three will give identical results. So for our starting point we need to consider only one corner, and the crossing point in the middle as well. Of course, we have to make sure we don't miss any possible paths.
Ok, let's try one, and again feel our way around. One obvious path is to start at corner 1, draw the line to 2, then 3, then 4, and back to 1. So we've drawn the box, and now we have the cross-shaped lines in the middle to do. Can we draw that without retracing or lifting, starting at the end of one of the arms? Clearly not; we draw to the middle and then we have three branches to draw, and each one is a dead end. So at least some of the lines in the middle must be drawn before we complete the outside square.
Suppose I start at 1, then go diagonally across to 3, up to 2, left back to 1, down to 4. (Better draw it yourself so you can visualize it.) Now I have two branches remaining. I could go diagonally to 2, or right to 3. But each of those ends after one move, and I have to do both. In other words, there are two different places I have to end, and obviously I can end the trace at only one place.
Where can this trace end, anyway? Can it end at the point where I start? Lessee, there are three paths at each corner. I take one out, one back, and the final one out. So it can't end at the corner where I start. That is, if I start at 1, I have to end at some other point.
Nothing stops me from starting at the middle point, I suppose. If I start at the middle point, there are 4 paths. I take one out, one back, the third out, and the fourth one back. So starting in the middle requires me to finish there. And the same reasoning shows that if I don't start in the middle, then I can't finish at that point: I'd take one line in to the middle point, a second out, a third in, and the last one has to take me out again.
Now I think I'm on to something here, and I'm going to abandon the "try all possible paths" approach — at least until I determine that this train of reasoning leads nowhere. Furthermore, in keeping with the idea that real mathematics requires hard thinking, trial, error, and rigorous demonstration, I'm going to leave you here to figure it out on your own.
If you can't get it and want to see the complete solution, send email to me and I'll send you the url to the rest of it. But don't give up! Success in mathematics — like everything else — is rewarding in proportion to the effort expended. So give it some concentrated effort over the course of several days before you decide to ask for the solution. And if you think your son or daughter likes this kind of thing, and you want a introduction to the rich field of mathematics, contact me and we'll make a plan to get it.
By the way, this branch of mathematics is called graph theory, and if it interests you, a book you'll find interesting is Four Colors Suffice by Robin Wilson.