\chapter{Handshakes, Islands, and Groups} \section{Leaves on Kittens} ``Remember the lattice forest that you chased me through earlier?'' Alice nodded. ``Well, I'll bet you weren't paying any attention to the leaves.'' ``The leaves?'' asked Alice. ``No, I wasn't. Why, do they follow Fibonacci or something?'' ``Actually what I'm about to tell you has very little to do with those trees and those leaves. I could easily make the same point with whiskers on kittens. Why trees? Trees are arbitrary. But why not?'' Alice was not about to ask, and the Pig continued. ``All of the trees in that forest have less than 170,000 leaves on them. And there are more than 170,000 trees in the forest. So, there must be at least one pair of trees with the same number of leaves.'' ``What?'' asked Alice. ``You expect me to believe you when you say there are two trees with the same number of leaves? Surely you couldn't have counted them all.'' Alice was beginning to question the Pig's sanity. What did leaves and trees have to do with anything? And were there really that many trees and leaves? ``I didn't need to count them. But I'll give you an example that you can count so you can see that it works. As a yellow pig, I, of course, have seventeen eyelashes. All yellow pigs do. And all yellow pigs have one eye with nine or more eyelashes. It's an argument in counting. Count my eyelashes.'' The Pig sat down beside Alice, and Alice proceeded to count his eyelashes. She lost count once and had to start over again. But sure enough, she counted eight eyelashes over the left eye and nine eyelashes over the right eye. Or maybe it was the other way around. But certainly there were eight eyelashes over one eye and nine above the other. ``Now,'' continued the Pig. ``You should be convinced that because I have seventeen eyelashes, one eye must have nine or more eyelashes. Here, I'll try to draw a picture of a seventeen-eyelashed pig with no eye having more than eight eyelashes.'' He quickly sketched a pig's face and drew in eyes. He drew one eyelash over the left eye, then one over the right, then another over the left, and another over the right. All the while he counted out loud. He stopped at sixteen, having a pig with eight eyelashes over both the left and right eyes. ``Where do I put the last eyelash?'' he asked. ``If I put it on the left eye, then that one has nine eyelashes. But if I put it on the right eye, that one has more than eight eyelashes. I could have made a pig with ten eyelashes and seven eyelashes or one with sixteen and one, but no matter what, one of the eyes will have to have more than eight eyelashes.'' ``Well, that's all obvious,'' said Alice. She almost laughed when she heard herself say that. Since when had math seemed so easy to understand? It was just about thinking, really. ``It may seem obvious to you,'' said the Pig, ``but from obvious ideas come powerful results. I don't have to count the leaves on the trees. I can picture 170,000 different trees. One has one leaf, the next two, and so on. But as soon as I conceive of the 170,001st tree, it must have the same number of leaves as another tree.'' Alice still had trouble thinking about that many trees. The Yellow Pig explained, ``This reasoning is based on the pigeonhole principle, so named because we are putting a fixed number of things --- pigeons --- into a fixed number of categories --- pigeonholes. If you try to get 18 pigeons into 17 pigeonholes, two pigeons are going to have to share a pigeonhole. I like to refer to it as the pigs-in-holes principle. If you try to get 18 pigs in 17 holes, two pigs have to share a hole. And, if you try to put 35 pigs in 17 holes, one hole will have at least three pigs in it.'' ``That's because 35 is more than 34, isn't it?'' asked Alice. She reasoned aloud. ``It's more than 2 times 17. If you have 34 pigs, you can arrange them so that there are two in each hole. But as soon as you add the 35th pig, you'll have one hole with 3 pigs. That's the best case scenario. You can try arranging the pigs any other way that you want, but one hole will have three or four or five or even more pigs in it.'' ``Exactly,'' the Pig agreed. ``I'm so glad you understand. The pigs-in-holes principle is yet another of the mathematician's tricks. I have a special book of my favorite proofs, and a lot of the proofs in it make use of this pigs-in-holes principle. Some of the proofs are pretty sophisticated, but I'll try to explain a few. ``Here's one of them. It may take you a moment to understand the problem because there's some new terminology. I claim that if you pick any 50 natural numbers from 1 to 99, at least two of the numbers you pick will be relatively prime to each other. Relatively prime means that the two numbers have no common divisors or common factors, except for 1. In other words, they are not necessarily primes, but they are prime with respect to each other. The numbers 4 and 15 are relatively prime to each other. Neither 4 nor 15 is prime, but they don't share any divisors so they are relatively prime to each other. Do you understand?'' asked the Pig. ``If you are ever unsure of what I am saying, tell me to stop and explain it again.'' ``I'm not sure I get it,'' said Alice. ``You mathematicians sure have a lot of concepts and terms to define before you ever prove anything, though. Why, it's like having to learn another whole language.'' ``That's a very astute analogy,'' the Pig said. ``Mathematics is sort of another language. Not only is it a language, it's even a somewhat universal one. Mathematicians who speak different languages can often communicate with each other through numbers and mathematical notation. It is confusing, though, to understand math if you aren't already familiar with the terminology. When I studied mathematics in school, I used to keep a list of terms that I needed to know. I'd look at it every night before I went to sleep and I would dream about homomorphisms and endomorphisms and words you wouldn't believe. Mathematics is a very complicated language because there are so many words with such precise meanings. But, I'm getting off the subject again, am I not? Back to relatively prime numbers. The numbers 17 and 6 are relatively prime, but 17 and 34 aren't. Neither are 6 and 8. Do you see why?'' ``Let's see,'' thought Alice. ``Well, 17 is prime and 34 isn't \ldots .'' ``But that's not really what matters,'' interrupted the Pig. ``Though it's a handy thing to know.'' ``And 17 divides 34 evenly, so they aren't relatively prime. The other one is trickier. Certainly 6 can't divide 8. But you said relatively prime has to do with common divisors. And 6 is divisible by 2 and 3, and 8 is also divisible by 2. They share a common factor of 2 so they can't be relatively prime. Hey, neither 6 nor 8 is a prime number.'' Alice remarked. ``True,'' said the Pig. ``Now my claim should make sense. If you pick 50 numbers from 1 to 99, some pair will be relatively prime.'' Alice thought about this for a moment before the Pig spoke again, ``You should notice that I said 99 and 50. It is crucial that 50 is more than half of 99. Let's try it with a smaller example. I claim that you can't pick 5 numbers from 1 to 9 without having a common divisor. Try it.'' The Pig wrote the numbers from 1 to 9 on another page in his notebook. Alice chose the first five numbers. ``Nope, that won't work at all, because 1 and any number have no common divisor except for 1, and that's the definition of relatively prime.'' ``Right,'' the Pig confirmed. ``So I can't pick 1. I can pick 2, though. What about 3? I can't pick 3 then because 2 and 3 are relatively prime. In fact, they are both prime numbers.'' ``Any two prime numbers have to be relatively prime to each other,'' interjected the Pig. ``I can pick 4 though, because 2 divides 4. And I can pick 6 and 8 as well. They are all multiples of 2 so none of them is relatively prime to 2.'' ``Impressive,'' said the Pig. ``You've got four numbers. I asked for only five. You're almost there.'' ``I can't pick 5, because 5 and any of those numbers are relatively prime. I can't pick 7 either. Or 9. I'm stuck. I guess you win in that case.'' Alice frowned. ``Maybe I should have started with a different number. It seems that as soon as I picked 2, I had no choice in what I picked.'' ``Very true,'' the Pig said. ``I'll try starting with 3. But then, wait. When I started with 2, I was able to add all of the multiples of 2 but nothing else. So when I start with 3, I'll be able to pick all the multiples of 3, but nothing else. Now I can only have 3, 6, and 9. That's even worse than before.'' ``You had the best case to start with,'' said the Pig. ``And that's what pigs-in-holes is all about. It's about the best case not being good enough. Your intuition is exactly right. The best you can do is to have 2 and its multiples. Because there are more multiples of 2 in a given interval than there are multiples of any other number. And that's not good enough. A real mathematician would flesh out those ideas a bit more and write out a formal proof. We can outline a proof. First, we need to decide what our pigs and holes are.'' ``Well,'' said Alice, ``the pigs are the things we are picking, right?'' The Pig nodded. ``So those are the numbers. We want to pick 5 out of 9 pigs, or 50 out of 99 in your bigger example. I don't know what the holes are, though.'' ``That's the real key to pigs-in-holes proofs,'' the Pig said. ``I'll help you out because this one is fairly tricky. The mathematicians who discovered this one were pretty quick-thinking fellows. Let's look at the numbers from 1 to 9. You were able to pick 4 numbers, but not 5. So there are going to be 4 holes. That's where the final part of the proof comes from. The last line is something like `since there are 4 holes, and we want 5 pigs, two of the pigs must come from the same hole. And that's no good.' Actually, the last line is `Q.E.D.' Some mathematicians write that at the end of proofs to show they are done. It comes from a Latin phrase meaning `which was to be demonstrated'.'' He continued, ``We want to set up our pigs and holes in a way that we can't pick more than one pig from each hole. That means the holes must contain sets of numbers which are relatively prime to each other. This is, in a sense, the opposite of what we are really looking for. In order to find numbers that aren't relatively prime, we first find numbers that are. Remember our proof that there were an infinite number of primes?'' Alice remembered it well. That was the proof in which the Pig had found a larger prime by multiplying all of the primes together and adding 1. ``That proof used the fact that if you add 1 to a number, it shares no common factors with the number. No matter which of its divisors you divide the new number by, you will always get a remainder of 1. And that's the same as saying that any two consecutive numbers are relatively prime. Now I'm ready to show you how the numbers are arranged in holes,'' and he wrote in his notebook: \begin{center} \begin{tabular} {ccccc} 1 & 2 & 4 & 6 & 8 \\ & 3 & 5 & 7 & 9 \\ \end{tabular} \end{center} ``What I said before was kind of misleading. I actually wrote five holes in my notebook. The first hole contains only the number 1. It's a special hole, because once you pick 1, you can't pick any other numbers. So even though there are five holes, that one doesn't really count. In the remaining four holes I have just placed pairs of numbers. Because they are consecutive numbers, each pair is relatively prime. If I wanted to write out the example with the numbers from 1 to 99 I would just have those 5 holes and a lot more. The next hole would contain 10 and 11, the one after that 12 and 13, and so on all the way up to the last hole which would have 98 and 99. Then I would have 50 holes, the first one of which contains just 1. And I would have to pick 50 numbers, excluding the 1 and with no two from the same hole. There's no way I could do it. We thought that was true before, but by drawing the pigs and holes, we are able to clearly show it. Proving something is about having a convincing argument. It's about knowing why something must or must not work.'' Alice was a little bit confused. The result made sense, she supposed, but she didn't think that she would have been able to see it herself. ``I'll work out another similar proof, and then maybe it will make more sense to you,'' said the Pig. ``In mathematics sometimes it is better to plunge ahead even if you aren't sure you understand what you've seen so far. Sometimes everything just clicks into place after you are more familiar with it.'' He continued, ``Suppose at least 1 pig is born every day and 34 pigs are born in 18 days. Then it must be the case that in some consecutive interval of days, exactly 17 pigs are born.'' Alice thought about this. ``The key here is to look at how many total pigs have been born by the end of any given day. If the difference between any of these final counts is 17, then that means exactly 17 pigs are born on the in-between days.'' ``That is clever,'' said Alice. ``Very,'' said the Pig. ``Because now we can assume our statement is false --- that is, suppose that there is no interval of days in which exactly 17 pigs are born --- and apply our pigs and holes. A total of 34 pigs are born. That means that the total number of pigs at the end of the 18th day is 34. Since the problem deals with 18 days and 17 pigs, it seems likely that we will end up trying to pull 18 pigs out of 17 holes, and of course we won't be able to do so without picking 2 pigs from the same hole. ``Here's how we group the pigs. Say there is 1 pig born the first day. That means the total number of pigs at the end of any day can never be 18 because then exactly 17 pigs would have been born on the days in between. So we put 1 and 18 in the same hole to signify that we can't choose both of them. Same with 2 and 19. If 2 pigs have been born by the end of some day, then 19 pigs can't be born by the end of another day. We want our holes to contain possible numbers of pigs born by the end of each day. And we want to pair up numbers which have a difference of 17, so our holes end up looking like this:'' \ssp \begin{center} $ \begin{array}{ccccccccccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 & 33 & 34 \\ \end{array} $ \end{center} \dsp ``That's 34 numbers, representing numbers of pigs, in 17 holes. Our challenge was to pick 18 numbers, but we've arranged our numbers so we can't pick any two numbers from the same hole. If we pick 18 numbers, two of those numbers must be from the same hole. Hence, there will be a pair of numbers with a difference of 17. That means we've shown that it is impossible to have the pigs born in such a way that there is not a set of consecutive days in which exactly 17 pigs were born. And that's where we say Q.E.Doodilidoo,'' finished the Pig. ``Want to hear another problem?'' he asked. Alice nodded. ``This is a variation on the pigs-in-holes principle that involves handshakes. Let me tell you a bit about handshakes first,'' the Pig said. ``If six people all shake hands, each one shakes five other hands. That's 30 handshakes. But shake my hand,'' he said, extending his front right hoof. ``That's one handshake for me and one for you. But it's the same handshake. So we divide by 2. There are actually only 15 handshakes because each handshake involves two people.'' ``I see,'' said Alice. ``Another way to think of handshakes is to remember the triangular numbers. Think about the first of the six people shaking hands. He goes around and shakes the other five hands exactly once. Then he leaves. The next person shakes the hands of the remaining four people. That's four more handshakes. The third person shakes the three hands that he hasn't yet shaken. Then there are two more handshakes and one last handshake. The last person doesn't initiate any handshakes because he has already shaken hands with everyone. So that's $5+4+3+2+1$ handshakes,'' concluded the Pig.'' Alice added up the numbers. ``That's 15 handshakes, which is the same as the number you got before.'' ``Yup,'' said the Pig. ``There's more than one way to get the same result. It's just like Gus said: $1+2+3+4+5$ is the same as $\frac{(5)(6)}{2}$.'' ``I get it,'' said Alice. ``Now, what's your handshake problem?" ``In this problem there are 11 people. There are 10 dinner guests and a host. I claim it is impossible for them each to have shaken a different number of hands. The pigs in this problem are the numbers from 0 to 10.'' ``And we want to choose 11 such numbers,'' said Alice. ``But wait, I don't see why we can't do that. There are 11 numbers from 0 to 10.'' ``There's a catch,'' said the Pig. ``There are actually 10 holes even though there are 11 pigs. Remember that handshakes come in pairs. So,'' the Pig continued, ``if there are 11 people and one of them shakes 10 hands, that means everyone has shaken hands with that person. It is impossible for one person out of 11 to shake 10 hands and another person out of 11 to shake 0 hands. We put 11 and 0 in the same hole, and then we have our proof.'' ``Here's a riddle for you. A lot of handshaking goes on between the 10 guests and the host. It turns out that all of the guests shake a different number of hands. Every guest shakes at least one hand. The question is: How many hands does the host shake?'' ``I can't solve that,'' Alice cried out. ``You haven't given me enough information.'' ``But I have,'' said the Pig. ``Let's try to write out which people every guest has shaken hands with. Handshakes work in pairs, right?'' ``Right,'' agreed Alice. ``So we can determine precisely which handshakes took place. Each guest shakes a different number of hands. That means one guest shakes 1 hand, one guest shakes 2, and so on up to 10. We can call our guests 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10 to designate how many hands they shook. And we'll call our host $h$ because we don't know how many hands he shakes. Now I'll draw a table for all the possible handshakes and we can fill it in.'' ``I'll place a 1 in the table if a handshake occurred and a 0 if a handshake didn't occur. No one shakes their own hand, so I can fill the diagonal with 0's. Because handshakes come in pairs, my drawing, or matrix as mathematicians would call it, will be symmetric. So I only have to fill in the spaces to the left of the diagonal.'' ``Okay,'' said Alice. She looked over at the Pig's notebook. He had drawn a table that looked like this: \begin{center} \begin{tabular} {c|cccccccccccc} & {\bf 10} & {\bf 9} & {\bf 8} & {\bf 7} & {\bf 6} & {\bf 5} & {\bf 4} & {\bf 3} & {\bf 2} & {\bf 1} & & {\bf h} \\ \hline {\bf 10} & 0 & & & & & & & & & & & \\ {\bf 9} & & 0 & & & & & & & & & & \\ {\bf 8} & & & 0 & & & & & & & & & \\ {\bf 7} & & & & 0 & & & & & & & & \\ {\bf 6} & & & & & 0 & & & & & & & \\ {\bf 5} & & & & & & 0 & & & & & & \\ {\bf 4} & & & & & & & 0 & & & & & \\ {\bf 3} & & & & & & & & 0 & & & & \\ {\bf 2} & & & & & & & & & 0 & & & \\ {\bf 1} & & & & & & & & & & 0 & & \\ \\ {\bf h} & & & & & & & & & & & & 0 \\ \end{tabular} \end{center} ``Number 10 shook 10 hands which means he shook every hand. So we can fill in the 10 column 1's. And because 10 shook 1's hand, 1 can't shake any more hands. His quota is up. So we can fill in the rest of the 1 row with 0's. We do the same thing for number 9. Number 9 shook hands with 10, 8, 7, 6, 5, 4, 3, 2, and $h$. That's everyone who is left as a potential person to shake hands with. So we fill down the 9 column with 1's. Again, look at row 2. It already has 2 1's, so the rest of the row gets filled with 0's.'' ``We can do the same thing for 8,'' said Alice. ``Right,'' said the Pig. ``And again for 7 and 6.'' ``And now since 5 and 4 and 3 and 2 and 1 have already completed their handshaking, we're done. We just need to finish filling out the other half of the chart to verify that everyone is performing the right number of handshakes. And then we count up the handshakes in the $h$ row or column to know how many hands the host shakes.'' The Pig's chart now looked like this: \begin{center} \begin{tabular}{c|ccccccccccc} & {\bf 10} & {\bf 9} & {\bf 8} & {\bf 7} & {\bf 6} & {\bf 5} & {\bf 4} & {\bf 3} & {\bf 2} & {\bf 1} & {\bf h} \\ \hline {\bf 10} & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ {\bf 9} & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\ {\bf 8} & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \\ {\bf 7} & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ {\bf 6} & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ {\bf 5} & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ {\bf 4} & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {\bf 3} & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {\bf 2} & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {\bf 1} & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {\bf h} & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{tabular} \end{center} ``I get it,'' exclaimed Alice. ``We solved your problem. The host shook hands with guests number 10, 9, 8, 7, and 6. That's five handshakes.'' ``Correct,'' said the Pig. ``That's the sort of problem that is more about the thinking than actual computation. A lot of math is like that. Proofs are just logic puzzles, exercises in creativity. Speaking of exercise, let's go for a walk.'' Alice and the Pig stood up, and they continued on their way. \section{Over the Bridge} They completed a circle around the mathematical garden, passing the stream that Alice has noticed when she first followed the pig down his hole. After a moment, they continued walking further downstream until they reached a rather large lake. ``If I were a teddy bear looking for fish or a nice swim,'' the Pig said, ``this is where I would go.'' Alice agreed that it was a very nice location for both fishing and swimming. She would go swimming herself except that the water was a wee bit too cold. Besides, she was on a mission to find her bear and couldn't let herself be distracted. Alice and the Pig circled the lake, with Alice frequently calling out, ``Honeybear? Can you hear me?'' and ``Teddy, where are you?'' She kept calling even though she knew her bear wouldn't answer. ``He's very shy and talks not at all,'' she explained to the Pig. About halfway around the lake, as Alice was beginning to become discouraged, the Pig noticed an empty jar of honey. Excitedly, he pointed it out to Alice as a sure sign that her bear had been there. Alice hugged the Pig and exclaimed, ``Oh Teddy, we will find you!'' and resumed her calls with renewed enthusiasm as the two made their way around the shore. She was certain she would find her teddy, but the stuffed animal was nowhere in sight. ``I'm sorry, Alice. We're back where we started,'' said the Yellow Pig finally. ``And I need to rest for a moment.'' The two of them sat and watched the ripples in the water. ``Is that an island?'' inquired Alice, peering into the distance. ``Yes,'' replied the Pig. ``Actually there are several. We are going to try to visit them all, which is why I need to rest first. You see those bridges? We are going to try to cross all of the bridges exactly once. It's like a maze. Actually, it's called a graph. A graph is a diagram with edges and vertices. Edges are paths, like those bridges. Vertices are points or nodes, like the islands. The problem of crossing bridges is one that mathematicians of graph theory know well.'' ``Maybe my bear went to one of those islands,'' Alice ventured. ``He might have. There are nine bridges connecting the five land masses,'' said the Pig. ``I'll tell you a little about each of the islands. The northernmost island is Sunny Harbor, known for its early morning sun. To its west, off in the distance, is Seashell Isle, named for the beautifully spiraled shells that decorate its beaches. Just south of Seashell Isle are Francis Island and Matthew Island. Matthew Island is the one farther south. Finally, we are in the southeastern corner at Treeline Shore.'' ``There are a lot of bridges here,'' remarked Alice. ``There are. From Treeline Shore are six of the nine bridges. Two of them go north to Sunny Harbor and two of them west to Matthew Island. One goes to Francis Island and the last to Seashell Isle. There are three more bridges connecting the islands to each other. One goes from Sunny Harbor to Seashell Isle. Another goes from Seashell Isle to Francis Island, and the third bridge connects Francis and Matthew Islands. But I don't need to tell you,'' said the Pig, ``you can look at my map.'' \centerline{\epsfbox{images/3-islands.ps}} ``The bridges are lettered so we can write down our path as we traverse the bridges,'' the Pig said. ``Are you ready to see the islands?'' Alice said she was. ``Good. I think I've rested enough. Let's go try some bridge crossing.'' And with renewed energy, the Pig leapt to his feet. ``Which bridge first?'' he asked. Alice thought for a moment. ``How about one of the ones going north to Sunny Harbor?'' ``Okie-dokie,'' said the Pig agreeably, and they took off in the direction of the first bridge. The Pig marked the letter M in his notebook. They strolled quickly across the bridge, pausing at the center so Alice could look down at the water. Soon they reached the end of the bridge and an old wooden sign that read ``Welcome to Sunny Harbor''. Alice was disappointed that her teddy was not there to greet them, but otherwise she thought it was a wonderful and enchanted island. She saw a bird, a caterpillar, and a badger having a picnic. This did not strike her as odd in the least. ``Now what?'' asked the Pig, awaiting Alice's instruction. ``We can take the other bridge back to Treeline or we can continue to Seashell Isle.'' ``Oh, let's go to Seashell Isle,'' Alice begged. ``Very well,'' said the Pig, jotting down a P in his notebook. They went over another and longer bridge. Alice and the Pig skipped merrily, whistling as they went. They stopped at Seashell Isle briefly, and Alice wandered along the beach picking up seashells to bring back with her. ``I'll give some to my sisters,'' Alice thought to herself, ``if I ever return. Why, I don't even know if I can get back to the shore, and then I don't know how I will leave this mathematical land. Surely I can't stay forever! But I must find my bear before I leave.'' Before Alice could get too wrapped up in her worries, the Pig asked, ``Where to now, my lady?'' ``Let's go back to the shore,'' said Alice. ``Good idea,'' remarked the Pig. ``Once we get there we will have ample bridges to choose from.'' And he wrote down an R, and they were off. Back at the shore, they sat under the shade of a tree for a moment. All the walking across bridges was starting to tire them out. But they hadn't lost their sense of adventure, so they continued to Matthew Island. The Pig added a D to his notebook. This bridge was closer to the water than the others had been. ``Oh look,'' exclaimed Alice just after they got on the bridge. ``There are ducks.'' Alice leaned over the railing to watch a mother duck swim by with her ducklings following closely. The Pig stood behind Alice, watching carefully so she wouldn't fall over. After the ducks had passed, they crossed the bridge to Matthew Island. ``Let's go to Francis Island,'' said the Pig. ``It's the only one we haven't seen yet.'' The Pig wrote an A in his notebook and they crossed the short bridge. Francis Island was cooler and more hilly than the other islands. From there they took the widest bridge, which went back to Treeline Shore. A letter O joined the other letters in the Pig's notebook. From the Shore, they had two paths left: one to Sunny Harbor and one to Matthew Island. ``We haven't been to Sunny Harbor in a while,'' pointed out Alice. ``And it's closer,'' said the Pig, looking a bit winded. He wrote down C and they marched off over the bridge. But just before they reached Sunny Harbor, a horrible thought occurred to Alice. ``Oh no!'' she cried out loud. ``We're going to be stuck on Sunny Harbor. Look at the map. Sunny Harbor has three bridges. There's the one labeled M which we first crossed, the one labeled P which we took second, and finally C, the one we are on now. We've crossed them all. We can't go back without crossing one of the bridges a second time.'' ``You're right,'' said the Pig. ``Fortunately, I anticipated that. No matter what order we cross the bridges in, we won't be able to go over them all exactly once. The reason is very simple.'' He motioned for Alice to sit down and he began his explanation. ``Every time we go out to an island over a bridge, we have to make sure there is a bridge for us to come back on. Just as in the handshake problem, the key is pairs. There have to be pairs of bridges: one to go out on and another one for coming back. So every island has to have an even number of bridges.'' The Pig flipped back to the map in his notebook. ``Now look at how many bridges there are from each of the islands. From Sunny Harbor, Seashell Isle, Francis Island, and Matthew Island there are three bridges each. So we would have gotten trapped on any island if we tried to go back a second time.'' ``You mean you knew we were doomed from the start?'' asked Alice, almost incredulously. ``We're not doomed at all,'' said the Pig with a laugh. ``We just can't go over any more bridges. That's why all of these islands have boats.'' And sure enough, he produced a rowboat. With Alice's help, he dragged it down to the water, and the two of them rowed back to Treeline Shore. When they returned to the mainland, the Pig said, ``Now you've seen one of the classic problems of graph theory. It was a problem about paths, or edges between points. Graphs are also about the points or vertices themselves. Some problems in graph theory are about coloring. A well-known theorem states that any planar graph --- like any geographic map with different regions --- can be colored with only four colors so that no adjacent regions are colored in the same color.'' ``Only four colors?'' asked Alice. ``How can that be? A map can be very complicated.'' ``It's true,'' said the Pig, ``though it's really hard to prove. It was a conjecture for over a century before it was finally proven. You should draw a map sometime and try coloring it with four colors.'' Alice was eager to try this for herself. It would make a good exercise for her teddy bear, if she ever found him. ``I'll also briefly tell you a problem about coloring edges. Suppose I go to a small party of random guests. Some of these guests know each other and some of them don't. If there are six people at the party, then I claim that either it is the case that some three of them all know each other or else it is the case that there are three people who have never met. We can represent this mathematically by thinking of the guests as six points with edges between them. There are $5+4+3+2+1$ edges connecting the six points. The edges go both ways like handshakes in our handshake problem. Since any pair of guests either knows each other or doesn't, we can model the situation by coloring the edges using two colors. According to my statement, if all of the edges in the graph are colored, there will be a single-colored triangle, representing three people who either all know or all don't know each other. I want to prove that my statement is true.'' ``We could just draw out all of the possible colorings,'' suggested Alice. ``We could in this case,'' said the Pig, ``though I prefer to use a strategy for coloring. I'll start out by drawing six evenly spaced points on a circle, like the corners of a hexagon. Then I choose one color and use it to draw lines connecting all points of one unit away. That's six edges. Then, for lines connecting every other point, I can't use the same color without forming triangles. So, I need to use the other color. I can use my first color to color the three edges connecting the points that are three units away. Now I have to switch to the other color. The six remaining edges must be in the other color. But, if they are all in the same color, we get two triangles. I can't use either color, so a third color is required to complete the graph.'' \centerline{\epsfbox{images/3-ramsey.ps}} ``But that was just one possible coloring,'' said Alice, unconvinced by the Pig's logic. ``There are an awful lot of combinations,'' said the Pig. ``We can draw all of them, or we can try to show that no coloring is better than this one. Because there are only six guests, it's not too hard to try all of the possibilities. You can see how it would get very difficult to solve such problems with more guests. That's why there are so many open problems in this field of study.'' ``I guess it would take a long time to draw all of the colorings,'' conceded Alice. ``There are a lot of deceptively easy problems like that in mathematics. Fortunately, a lot of excellent mathematicians have been working on these and other problems in graph theory. They are on a quest for beautiful proofs. Beautiful, or elegant, proofs are ones that are so simple that they make their theorems seem almost trivial. They are proofs that other mathematicians read and feel silly because they did not arrive at the conclusions themselves. One Hungarian mathematician, named Erd\H{o}s, conceived of a God who possessed a book of all such proofs. A friend of his said that the devil had an analogous book, full of theorems for which God had no proofs. ``That's what drives mathematicians, the desire to find proofs for the unproven theorems, the desire to solve problems that were previously unsolved. Mathematicians want not only to find solutions, but they want to find good solutions. For a proof to be satisfying to a mathematician, it has to be beautiful. A mathematician is an artist, and proving theorems is his art.'' \section{Through Another Door} ``Speaking of art, let me show you the collection we have here in our gallery,'' the Pig said, leading Alice to an elaborate and domed building. He paused before a gold door. ``This is where we store our great artwork. We have a most impressive collection, funded by a number of families, including my own. The gallery contains some of our favorite artwork. All of the art in this gallery is mathematically pleasing. There are a lot of paintings from the Renaissance and even a whole exhibit by M.C. Escher. Escher is an amazing artist who used to visit here.'' The Pig led Alice to a room that was unlike any Alice had ever seen before. ``This is the entrance hall,'' he said. The walls were covered with patterns of different colors and geometric shapes. There were no actual pictures. ``It's a tribute to the Alhambra. Do you like it?'' ``The Alhambra? What's that?'' Alice asked. ``The Alhambra is a Moorish castle. It contains all of the patterns you see here. They are known as tessellations or wallpaper patterns or symmetry groups. And there are seventeen of them. Isn't that incredible? There are exactly seventeen distinct patterns. Seventeen is such a wonderful number,'' said the Pig proudly. ``When I say seventeen different patterns, I mean there are seventeen different ways for the lines of symmetry to be arranged. For example, I can start with a square tile and translate it in all directions to form a square grid like a checkerboard. Or I can start with a hexagon or a triangle. I can also rotate tiles before translating them. Think of a tile as the single unit that is reproduced in the tiling,'' explained the Pig. ``Tiles come in different shapes and have different symmetries. For example, a tile can be a square. The square can be cut in half to form two rectangles. The pattern filling in one rectangle is then a mirror image of the pattern filling the other rectangle. Or the second rectangle could be identical to the first only rotated $180^{\circ}$. The square could also be cut along its diagonal to produce two triangular pieces.'' ``There must be other shapes besides squares,'' interrupted Alice. ``like slanted rectangles and beehives.'' ``Yes,'' agreed the Pig. ``We call the slanted rectangles parallelograms and the beehives hexagons. Both shapes have the appropriate angles to cover the plane. Before I teach you any more geometry, I think you should learn some algebra.'' ``Algebra?'' said Alice. ``Like that awful quadratic formula Lorina used to recite?'' ``Not exactly,'' said the Pig smiling. ``This is even more advanced algebra. It's sometimes known as modern algebra because as a branch of mathematics it has been around for a short time when compared with regular algebra. Modern algebra is the study of groups. And a group is just another mathematical term. It means a set of elements, which are often numbers, and an operation, such as addition or multiplication, that follow certain rules or conditions.'' Alice was starting to feel tired. All of this mathematical terminology really did make her dizzy. She followed the Pig to a corner where he sat on a dark rug that was covered with geometrical patterns. ``You already know some examples of groups,'' said the Pig. ``The real numbers with the operation of multiplication. That's a group with a whole lot of elements. If you multiply any two real numbers together, you get another real number. If you multiply a real number by 1, the result is the same real number. You can divide any real number into 1 to get another real number. If you are multiplying a whole string of numbers, it doesn't matter what order you multiply them in; you will always get the same result. So mathematicians say that the real numbers --- excluding 0 because you can't divide by 0 --- form a group under multiplication. Let me show you the properties of groups under multiplication.'' He wrote: \vbox{ \ssp \begin{enumerate} \item{Multiplying two numbers in the group together yields another number in the group (closure).} \item{1 times any number is that number (identity).} \item{Any number has a number that it can be multiplied by to get 1 (inverses).} \item{The order of multiplication is flexible (associativity).} \end{enumerate} \dsp } Alice looked skeptical. ``What is it?'' asked the Pig. ``I don't understand what makes groups so special. What isn't a group?'' she asked. ``Excellent question,'' said the Pig. ``The integers under multiplication, for one. Here's why: a group must have inverses that are contained within the group. An inverse is something that you multiply a number by to get 1, the identity. Take 3 for example. What do you multiply 3 by to get 1?'' ``You multiply it by $\frac{1}{3}$,'' said Alice. ``The 3's cancel, so you are left with 1.'' ``Right,'' the Pig said. ``And $\frac{1}{3}$ isn't an integer. So the integers under multiplication can't be a group.'' ``I see,'' said Alice. ``But I'm still not impressed with the real numbers being a group. After all, that's everything. Surely with an infinite number of numbers it is easy to find inverses and things.'' ``Oh, there are finite groups, too,'' said the Pig. ``Remember our numbers mod 12 and mod 7?'' ``Yes,'' said Alice. ``We had the numbers from 0 to 11 and then from 0 to 6 and then they repeated again and again after that.'' ``Well, they are both groups under addition. The nonzero integers mod 7 are also a group under multiplication because 7 is a prime number. For mod 12 the additive identity is 0 and the inverses are numbers that add to 12, or 0. So the inverse of 1 is 11, of 2 is 10, of 3 is 9, and so on. For mod 7 the multiplicative identity is 1 and the inverses are numbers that multiply together to make 1. Like 2 and 4; 2 times 4 is 8 which is one more than 7. And 3 and 5, because $3 \cdot 5 = 15 - 14 = 1$. The order of the addition or multiplication doesn't matter. And whenever you add or multiply two numbers together, you are going to get another number less than the mod you are in. That's how modular arithmetic works. And we have two examples of finite groups.'' ``I think I see,'' said Alice. ``Then let's try a more abstract example, one without numbers,'' said the Pig. He drew a square in his notebook and cut it out, leaving the paper around it to frame the empty space where the square had been. He labeled the vertices $a_{1}$, $b_{1}$, $c_{1}$, and $d_{1}$. Then he flipped over the square. On the other side of those vertices he labeled $a_{2}$, $b_{2}$, $c_{2}$, and $d_{2}$. He also labeled the corners of the paper cut-out with $a_{1}$, $b_{1}$, $c_{1}$, and $d_{1}$. ``There are eight ways that I can get this square to fit back in my notebook. Any of those eight corners I labeled can be in the top left corner. That's because of the symmetry of the square. From its original position, I can rotate the square $0^{\circ}$, $90^{\circ}$, $180^{\circ}$, or $270^{\circ}$. I can also pick up the square and flip it like this,'' he said, demonstrating. \centerline{\epsfbox{images/3-dihedral.ps}} ``I'll call these two manipulations $r$ for $90^{\circ}$ rotation and $f$ for a flip over the dotted line. There is also the identity, written $1$, which means to leave the square alone. I can combine moves by performing them consecutively. Using a combination of these types of moves, I can get the square from its original orientation to any other orientation. Or, in other words, if you give me the square in any old way, I can move it back to its original position using only $90^{\circ}$ rotations and flips. ``For example, if you give me the square with vertex $b_{1}$ at the top left and with $c_{1}$, $d_{1}$, and $a_{1}$ going around clockwise, I just have to rotate the square one $90^{\circ}$ turn clockwise. That would be $r$. If you gave me the square with $c_{1}$ at the top left, then $d_{1}$, $a_{1}$, and $b_{1}$ going around clockwise, I would have to do two rotations, or $r^{2}$,'' continued the Pig. ``I claim that these manipulations form a group. The group has the elements 1, $r$, $r^{2}$, $r^{3}$, $f$, $rf$, $r^{2}f$, and $r^{3}f$. We say that 1 is the identity. The next three elements are rotations by $90^{\circ}$, $180^{\circ}$, and $270^{\circ}$ respectively. The fifth element is a flip. From the original position, a flip would yield a clockwise sequence of $a_{2}$, $d_{2}$, $c_{2}$, $b_{2}$ starting from the top left. The last three elements are compositions of rotations and flips. My operator is composition. I can compose two elements by applying the two manipulations in succession from right to left. That is, $rf$ means a rotation applied to a flip, or a flip followed by a rotation.'' The Pig let Alice play with the square cutout for a few minutes so she could get an idea of the rotations and flips. ``To show that this is a group, I need to show that all of those properties I mentioned earlier are satisfied. 1 is the identity. If I apply 1, nothing changes. Every element has an inverse. In other words, when any one of those eight things is applied to the `home position' square, one of those same eight moves can be applied to get the square back to the `home position'. If 1 is applied, then 1 is just applied again. Same with $f$. One $f$ will undo another $f$. An $r^{2}$ will undo an $r^{2}$ as well. And an $r$ can be reversed by an $r^{3}$. The inverse of $rf$ is $rf$. The inverse of $r^{2}f$ is $r^{2}f$, and the inverse of $r^{3}f$ is $r^{3}f$. ``Next it is important to show that our group is closed. That means when we compose two manipulations, the resulting state can be represented by one manipulation or element. For example, if I perform $r$ to rotate the square once and then I perform $r$ to rotate the square again, that's the same as performing $r^{2}$.'' ``I see,'' said Alice. ``And if you perform $r$ to rotate the square once and then $f$ to flip the square once, that's the same as performing $rf$ just once.'' ``Exactly,'' said the Pig. ``We can write out a composition table for these manipulations, just like the multiplication table. The table will tell you what happens when the operation at the left is followed by the operation at the top. The first row is easy. Anything that follows 1 is itself. The manipulation $r$ followed by anything else is pretty easy too. The composition $r1$ is just $r$; $rr$ is $r^{2}$; $rr^{2}$ is $r^{3}$; $rr^{3}$ is 1; $rf$ is $rf$, $rrf$ is $r^{2}f$, $rr^{2}f$ is $r^{3}f$, and $rr^{3}f$ is $f$. That gives us each of the elements again in a different order.'' He and Alice went through the rest of the combinations, until they had filled out a table in his notebook. \begin{center} \begin{tabular}{c|cccccccc} & ${\bf 1}$ & ${\bf r}$ & ${\bf r^{2}}$ & ${\bf r^{3}}$ & ${\bf f}$ & ${\bf rf}$ & ${\bf r^{2}f}$ & ${\bf r^{3}f}$ \\ \hline ${\bf 1}$ & $1$ & $r$ & $r^{2}$ & $r^{3}$ & $f$ & $rf$ & $r^{2}f$ & $r^{3}f$ \\ ${\bf r}$ & $r$ & $r^{2}$ & $r^{3}$ & $1$ & $rf$ & $r^{2}f$ & $r^{3}f$ & $f$ \\ ${\bf r^{2}}$ & $r^{2}$ & $r^{3}$ & $1$ & $r$ & $r^{2}f$ & $r^{3}f$ & $f$ & $rf$ \\ ${\bf r^{3}}$ & $r^{3}$ & $1$ & $r$ & $r^{2}$ & $r^{3}f$ & $f$ & $rf$ & $r^{2}f$ \\ ${\bf f}$ & $f$ & $r^{3}f$ & $r^{2}f$ & $rf$ & $1$ & $r^{3}$ & $r^{2}$ & $r$ \\ ${\bf rf}$ & $rf$ & $f$ & $r^{3}f$ & $r^{2}f$ & $r$ & $1$ & $r^{3}$ & $r^{2}$ \\ ${\bf r^{2}f}$ & $r^{2}f$ & $rf$ & $f$ & $r^{3}f$ & $r^{2}$ & $r$ & $1$ & $r^{3}$ \\ ${\bf r^{3}f}$ & $r^{3}f$ & $r^{2}f$ & $rf$ & $f$ & $r^{3}$ & $r^{2}$ & $r$ & $1$ \\ \end{tabular} \end{center} ``Ta-da!'' exclaimed the Pig when he had finished. ``There are a lot of interesting things to notice about this table. What patterns do you see?'' Alice took a long time studying the table. ``Each row and column contains each entry exactly once,'' she said. ``Also, all of the entries with $f$'s are in two of the corners, and most of the 1's are on the main diagonal.'' ``Wonderful observations,'' said the Pig. ``All of those things hold because groups like this one have such elaborate properties. Another thing to look at is subgroups.'' ``What's a subgroup?'' asked Alice. The Pig explained, ``A subgroup is a smaller set of the elements in the table that satisfy all of the properties of being a group. It's just a group contained within a group. The set of 1, $r$, $r^{2}$, $r^{3}$ is a subgroup. If we just study the portion of our table with these four elements, we see that all of the composite operations are one of those four operations. Subgroups and groups are related to each other in complex and interesting ways. I don't think you're quite ready to hear about that, though. We've had enough algebra for now. Shall we enter the first exhibit hall instead?'' the Pig asked. ``Oh, yes,'' said Alice. ``I'd love to see what works of art are on display.'' And the Pig closed his almost-full notebook, helped Alice to her feet, and the two walked toward the small red door labeled ``Escher.''