\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.''