The Number Mysteries: A Mathematical Odyssey through Everyday Life
Page 14
Euler also believed that the puzzle was impossible to solve for a 10 x 10 grid, a 14 x 14 grid, an 18 x 18 grid, and so on, adding four each time. Not so, it turned out. In 1960, with the aid of a computer, three mathematicians showed that it was in fact possible to arrange ten different ranks of soldiers from ten regiments in a 10 x 10 grid in the way Euler thought was impossible. They went on to disprove Euler’s hunch completely, showing that the 6 x 6 grid is the only one in which his arrangement is impossible.
If you want to try the 5 x 5 version of Euler’s puzzle, then download the appropriate file at the Number Mysteries website, cut out the five ranks in five regiments and see if you can arrange them in a 5 x 5 grid so that in any column or row you don’t see a soldier of the same rank or in the same regiment. These magic squares are sometimes called Graeco-Latin squares. Take the first n letters of the Latin and Greek alphabets and write down all the n x n different pairs of Latin and Greek letters. Now arrange these pairs on an n x n grid so that no row or column contains the same Latin or Greek letter.
Living by the Square
One of the 10 × 10 Graeco-Latin squares was used by the French novelist Georges Perec to structure his 1978 novel Life: A User’s Manual. The book has 99 chapters, each corresponding to a room in a Parisian apartment block that has ten floors and ten rooms on each floor (one room, the 66th, doesn’t get visited). Each room corresponds to a position in a 10 × 10 Graeco-Latin square. But in Perec’s square, instead of ten Greek and ten Latin letters, he uses, for example, 20 authors divided into two lists of ten. When he wrote the chapter for a particular room, he looked to see which two authors were assigned to that room and made sure that he quoted passages from these authors during the course of the chapter. For chapter 50, for example, Perec’s Graeco-Latin square told him to quote Gustave Flaubert and Italo Calvino. But it isn’t only authors that figure in this scheme. Perec used a total of 21 different Graeco-Latin squares, each one filled with two sets of ten items ranging from furniture, artistic style, and a period in history through to the body positions adopted by the occupants of the rooms.
Sudoku works slightly differently than Euler’s soldiers puzzle. In the classic form, you have to arrange nine lots of the numbers from 1 to 9 on a 9 x 9 grid so that no row, column, or 3 x 3 quadrant contains a number twice. A few of the numbers are already placed on the grid, and you have to fill in the rest. Don’t believe those who say that no math is needed to do these puzzles. What they mean is that there’s no arithmetic involved—sudoku is essentially a logic puzzle. The kind of logical reasoning that leads you to decide that a 3 must go in the lower right-hand corner is precisely what mathematics is about.
There are some interesting mathematical questions relating to sudoku. One is this: how many different ways are there of arranging the numbers in the 9 x 9 grid to satisfy the sudoku rules? (Again, we mean “essentially” different: we regard two arrangements as the same if there is some simple symmetry, like swapping rows around, which changes one into another.) The answer was calculated in 2006 by Ed Russell and Frazer Jarvis to be 5,472,730,538—enough to keep the newspapers going for a while yet.
Another mathematical problem that arises from these puzzles has not been completely resolved. What is the minimum number of squares that need to have a number in them to start with for there to be just one unique way to fill in the other squares? Clearly, if you have too few—say, three—numbers in the grid, there will be many ways to complete the grid because there just isn’t enough information to force a unique solution. It is believed that you need at least 17 numbers to ensure that there is only one way to complete a sudoku puzzle. These questions are more than just recreational puzzles. The mathematics underlying sudoku has important implications for the error-correcting codes that we’ll meet in the next chapter.
HOW CAN MATH HELP YOU GET FROM A TO B?
During the eighteenth century, residents of the Prussian city of Königsberg were stumped by a problem about how to navigate their city. The River Pregel has two branches that run around the island at the heart of the city before emerging to the west and flowing into the Baltic. At the time, there were seven bridges spanning the Pregel, and it became a Sunday-afternoon pastime among the residents of the city to see whether they could find a way to cross all the bridges once and once only. But however hard they tried, they always found that there was one bridge they couldn’t get to. Was it really a mission impossible, or was there some route the residents hadn’t yet taken by which they could cross all seven bridges?
The problem was finally resolved by Leonhard Euler, the Swiss mathematician who’d posed the problem about Graeco-Latin squares, when he was teaching at the academy in St. Petersburg, some five hundred miles northeast of Königsberg. Euler made an important conceptual leap. He realized that the actual physical dimensions of the town were irrelevant: what mattered was how the bridges were connected together (the same principle applies to the topological map of the London Underground or the New York Subway). The four regions of land connected by the bridges of Königsberg can each be condensed to a point, leaving the bridges as lines connecting the points. This gives a map of the bridges of Königsberg that’s like a much simpler London Underground map:
Figure 3.13
The problem of whether there is a journey around all the bridges then boils down to asking whether it’s possible to trace over this map without taking your pen off the paper or running over any line twice. From Euler’s new mathematical perspective, he could see that it was in fact impossible to cross all seven bridges once and only once.
So why is it impossible? As you draw the map, each point visited in the middle of a journey must have one line into it and one line out. If you visit that point again, it will be by crossing a new “bridge” into it and a new “bridge” out of it. So there must be an even number of lines attached to each point, except at the beginning and the end of the journey.
If we look at the plan of the seven bridges of Königsberg, we can see that at each of the four points, an odd number of bridges meet—and that tells us that there is no route around the city that crosses each of the bridges only once. Euler took his analysis further. If the map has precisely two points with an odd number of lines coming out, then it is possible to trace over it without taking your pen off the page and without running over any line twice. To do this, you have to start at one of the points with an odd number of lines coming out and aim to finish at the other point where an odd number of lines meet.
Figure 3.14 Euler’s theorem implies that it’s possible to draw this map without taking your pen off the paper and going over a line twice.
There is a second sort of map on which it’s possible to follow what mathematicians now call an Eulerian path: one in which every point has an even number of lines running out of it. On a map like this, you can start anywhere you like, because the path must start and end at the same point so that it traces a closed loop. Even though you might have difficulty actually identifying the pathway, Euler’s theorem tells you that, as long as the map is one of the two types I’ve described, there must be an Eulerian path. This is the power of mathematics: it can quite often tell you that something must exist without your having to construct it.
To prove that such a path exists, we make use of a classic weapon in the mathematician’s arsenal: induction. It’s like what I do to get over my fear of heights when I’m climbing high ladders or rappelling down waterfalls: take one small step at a time.
Start by imagining that you know how to draw all the maps with a certain number of edges without taking your pen off the page. But now you’re faced with a map that has one more edge than the ones you’ve met so far. How do you know that you can still draw this new map?
Let’s say it’s a map that has two points with an odd number of edges coming out of them, and let’s call these points A and B. The trick is to remove one of the edges from one of the points with an odd number of edges. So let’s remove an edge going from B to another point, C.
This new map with one edge removed still has only two points with an odd number of edges coming out of it: A and C. (B now has an even number because we’ve just removed one line; C now has an odd number because we’ve removed the line joining it to B.) This new map is now small enough to be drawn, with a path starting at A and finishing at C. The bigger map is also now simple to draw: just join C to B, adding in the edge we removed earlier. Bingo!
There are a few variations that we need to analyze. For example, what if there is only one line from B that joins it to A so that A and C are the same point? But we can see that at the heart of Euler’s proof is this beautiful idea of building up step by step why an Eulerian path must be possible. Just as with steadily climbing a ladder, I can use this trick to find my way around however large a map I might encounter.
To see the power of Euler’s theorem, challenge a friend to draw as complicated a map as she wants. Then, by simply counting the number of points where an odd number of lines meet, thanks to Euler’s theorem you can tell instantly whether the map can be drawn without taking your pen off the page and without running over a line twice.
I recently went on a pilgrimage to Königsberg, which was renamed Kaliningrad after the Second World War. The city is unrecognizable from Euler’s day—it was devastated by Allied bombing. But three of the prewar bridges were still in place: the Timber Bridge (Holzbrücke), the Honey Bridge (Honigbrücke), and the High Bridge (Hühe Brücke). Two of the bridges had disappeared completely: the Offal Bridge (Küttelbrücke) and the Blacksmith’s Bridge (Schmiedebrücke). The remaining bridges—the Green Bridge (Grüne Brücke) and the Merchant’s Bridge (Krämerbrücke)—although destroyed during the war, had been rebuilt to carry a two-lane highway through the city.
Figure 3.15 The bridges of Königsberg in the eighteenth century.
A new railway bridge, which pedestrians can also use, now joins the two banks of the Pregel out to the west of the city, and a new footbridge called Kaiser Bridge allowed me to make the same crossing as over the old High Bridge. Ever the mathematician, my immediate thought was whether I could make a journey around today’s bridges in the spirit of the eighteenth-century game.
Figure 3.16 The bridges of Kaliningrad in the twenty-first century.
Euler’s mathematical analysis told me that if there were exactly two places with an odd number of bridges emerging from them, there would be an Eulerian path: you start at one of the odd-numbered points and end at the other. By checking the plan of today’s bridges of Kaliningrad, I found that such a journey is in fact possible.
The story of the bridges of Königsberg is important because it gave mathematicians a new way of looking at geometry and space. Rather than focusing on distances and angles, this new perspective concentrated on how shapes are connected together. This was the birth of topology (which we explored in chapter 2), one of the most influential branches of mathematics studied in the past hundred years. The problem of the bridges of Königsberg gave rise to the mathematics that currently runs modern Internet search engines, like Google’s, which seek to maximize the way networks can be navigated.
WHAT’S THE MILLION-DOLLAR PROBLEM?
There are many different versions of this chapter’s million-dollar problem. The classic one is called the traveling-salesman problem. An example of the problem is this challenge: you are a salesman and need to visit 11 clients, each located in a different town, and the towns are connected by roads, as shown in the following map—but you only have enough fuel for a journey of 238 miles.
Figure 3.17 An example of the traveling-salesman problem. Can you find a route of 238 miles or less that visits all the points on this map and returns to the starting point?
The distance between towns is given by the number on the road joining them. Can you find a journey that lets you visit all 11 clients and then return home without running out of fuel? (The solution is at the end of the chapter.) In this version of the problem, the million dollars is on offer for a general algorithm or computer program that will produce the shortest path for any map you feed into the program that would be significantly quicker than getting the computer to carry out an exhaustive search. The number of possible journeys grows exponentially as you increase the number of cities, so an exhaustive search soon becomes practically impossible. Or can you prove that no such program is possible?
The general feeling among mathematicians is that problems of this sort have a built-in complexity, which means that there won’t be any clever way to find the solution. I like to call these problems “needle in a haystack” problems because essentially, there are a vast number of possible solutions, and you’re trying to find one in particular. The technical name for them is NP-complete problems.
One of the key characteristics of these puzzles is that once you’ve found the needle, it’s easy to check that it does the job. For example, you know immediately once you’ve found a route around the map that is less than 238 miles long. A P-problem is one for which there is an efficient program for finding the solution. The million-dollar question can be put this way: are NP-complete problems in fact P-problems? Mathematicians refer to this as NP vs. P.
There is another very curious property that connects all these NP- complete problems. If you find an efficient program that works for one problem, it means that there will be such a program for all the other problems. To give an example of how this might work, here are two other “needle in a haystack,” or NP-complete, problems that look very different.
The Diplomatic-Party Problem
You want to invite your friends to a party, but some of them can’t stand one other—and you don’t want two enemies in the same room. So you decide to have three parties and invite different people to each one. Can you send out invitations in such a way that two enemies won’t turn up at the same party?
The Three-Color Map Problem
In chapter 2, we saw how you can always color a map with, at most, four colors. But is there an efficient way to tell whether you could get away with just three colors for any map?
How would a solution to the three-color map problem help you with the diplomatic-party problem? Let’s say you’ve written down the names of your friends and drawn a line between pairs of people who hate each other:
Figure 3.18 A line joins two people if they can’t be invited to the same party.
To invite each friend to one of three parties, you could start by coloring the circles using three colors, each color corresponding to a different party. Deciding which friend to invite to which party is then the same as finding a way to color in this picture so that no connected friends have the same color. But look what happens when you replace the names of the friends with something different:
Figure 3.19 A line joins two countries if they share a common border.
Friends of yours who don’t like one another have become European countries, and the links are now shared borders between countries. The problem of choosing which of the three parties to invite friends to has become the problem of choosing which of three colors to use for countries on a map of Europe.
The diplomatic-party question and the three-color map problem are different versions of the same question, so if you find an efficient way to solve one NP-complete problem, you end up solving them all! Here is a selection of different problems on which you can try your hand at winning the million.
Minesweeper
This is a single-player computer game that comes packaged with every copy of the Microsoft operating system. The aim of the game is to clear a grid of mines. If you click a square in the grid and it isn’t a mine, you are shown how many of the surrounding squares contain mines. If you click on a mine . . . you’ve lost. But the million-dollar minesweeper challenge asks you to do something slightly different. The following picture can’t be from a real game, because no arrangement of mines would give these numbers. The 1 implies that only one of the uncovered squares contains a mine, while the 2 implies that they both contain mines:
Figure 3.20
But what about the next picture—can it be from a real game?
Figure 3.21
Is there a way to place mines so that the numbers are consistent? Or is there no way that this can be from a real game because there is no arrangement of mines that could give rise to the numbers showing? Your job is to come up with an efficient program that will work this out, whatever picture you are given.
Sudoku
Finding an efficient program to solve arbitrarily large sudoku puzzles is an NP-complete problem. Sometimes, with the really killer sudokus, you need to make some guesses and then follow through the logical implications of those guesses; there doesn’t appear to be a clever way to make these guesses other than trying one after another until one set of guesses leads you to a consistent answer.
Packing Problem
You run a moving company. All your packing crates are of the same height and width, exactly the same as the internal dimensions of your truck (well, just a little smaller so that they just squeeze in). But the crates are of different lengths. Your truck is 150 feet long, and the crates available for packing have the following lengths: 16, 27, 37, 42, 52, 59, 65, and 95 feet.