Disc Math
Disc Math
Martin Milanič
Brigitte Servatius
Herman Servatius
ISBN: 978-0-443-18782-7
Preface xi
1. Discreteness
1.1 What is discrete mathematics? 1
1.2 The Multiplicative Principle 6
1.3 Binomial coefficients 8
1.4 Pascal’s Triangle 10
1.5 Binary numbers 12
1.6 Base conversion 14
1.7 Case study: Towers of Hanoi 17
1.8 Case study: The Binomial Theorem 18
1.9 Case study: The Guarini Problem 20
1.10 Case study: Red rum and murder 21
1.11 Case study: Tit for tat, nim 22
1.12 Summary exercises 24
vii
4. Formal logic
4.1 Statements and truth value 73
4.2 Logical operations 74
4.3 Implications 76
4.4 Double implication 79
4.5 Working with Boolean algebra 81
4.6 Boolean functions 83
4.7 DNF and CNF† 84
4.8 Case study: Classic logic puzzles 86
4.9 Case study: Spies 87
4.10 Case study: Pirates and cannonballs 89
4.11 Summary exercises 91
5. Induction
5.1 Predicate logic 93
5.2 Existential and universal quantification 95
5.3 The theory of induction 97
5.4 Induction practice 100
5.5 Strong induction 103
5.6 Sets versus logic 105
5.7 Case study: Decoding the Gray code 106
5.8 Case study: The 14–15 puzzle 107
5.9 Case study: Towers of Hanoi 109
5.10 Case study: The Fibonacci numbers 111
5.11 Summary exercises 113
6. Set structures
6.1 Relations 115
6.2 Functional relations 117
6.3 Counting functions on finite sets 119
6.4 Working with functional relations 120
6.5 Functions on infinite sets† 122
6.6 Cardinality of infinite sets† 124
6.7 Symmetry, reflexivity, transitivity 127
6.8 Orderings and equivalence 130
6.9 Case study: The developer’s problem 132
xi
The case studies have been placed so that, by the time they appear, all back-
ground concepts have been covered, but many work well in earlier or later
chapters, and covering them in between main sections is just as effective as
waiting until the main material is done. Some are very easy, some are more
challenging, and all are to some degree open ended. The case studies also work
very well for individual or group student presentations.
The book contains few citations and almost no bibliography. Students should
have no trouble finding sources for the material presented if desired. On the
other hand, for many problems and results we have deliberately altered the
names and the framing (e.g., “Euclid’s Coin Problem”) so that the student cannot
easily just “google it”, and will perhaps think it through on their own instead.
The pace of the class should be to cover two sections, main or case studies,
in each 50-minute class period.
For our students we always use all five of the initial chapters, varying only
the choice of case studies. On average we use two case studies per chapter, either
those in the text or others written in the same format, the choice depending on
class interest. The last week or two is devoted to some selection of the later
material.
Discreteness
1.1 What is discrete mathematics?
Defining discrete mathematics is not as easy as defining many other branches
of study. In biology you study living things, in astronomy you study heavenly
bodies, in vector calculus you study calculus on vectors. For discrete mathemat-
ics, the question is not only what is being studied, but how it is being studied.
The easiest way to answer the question “What is discrete mathematics?” is to
consider a variety of problems, mathematical and non-mathematical, and to ex-
amine for each of them to what extent we would consider it to be part of discrete
mathematics.
Problem list
1. Maximize
√ x 3 − 100x on the interval [−5, 21].
2. Is 2 rational?
3. Pythagoras’s problem: Show that for any right triangle, the square of the
hypotenuse is equal to the sum of the squares of the other two sides.
4. The Nantucket Map Problem: There is a large map of Nantucket pinned to a
bulletin board. Someone pins a small map of Nantucket on top of the large
map. Find a point to place a pin so that it marks the same location on both
maps.
5. The Wolf-Goat-Cabbage Problem: Can a man transport three items, a wolf,
a goat, and a basket of cabbages, across a river using a boat which is only
large enough for him to transport one item of cargo at a time, and keeping in
mind that, if left unguarded, the wolf will kill the goat and the goat will eat
the cabbage.
6. Albertson’s Magic Trick: An MC asks a victim from the audience to pick a
number from 1 to 31 and then answer truthfully whether or not it lies on each
of the following five cards.
16 18 20 22 8 10 12 14 4 6 12 14
17 19 21 23 9 11 13 15 5 7 13 15
24 26 28 30 24 26 28 30 20 22 28 30
25 27 29 31 25 27 29 31 21 23 29 31
2 6 10 14 1 5 9 13
3 7 11 15 3 7 11 15
18 22 26 30 17 21 25 39
19 23 27 31 19 23 27 31
1 Discrete mathematics is using your calculator on a test when the proctor is not looking.
Let’s now consider the magic trick. We will violate the fundamental rule of
magic and reveal the secret of the trick. Each card has an active region:
16 18 20 22 8 10 12 14 4 6
17 19 21 23 9 11 13 15 5 7
24 26 28 30
25 27 29 31
2 1
3
The numbers have been placed on the cards so that, for the first card for which
the answer is yes, the secret number will not only be on that card, but in the
active region. So if the answers are no, no, no, no, yes; then the active region
on the fifth card is only a single number, and the secret number is 1. Each sub-
sequent answer allows us to divide and shrink the active region in half, until at
the end it contains only the required number. Each time the region is shrunk,
it is shaped like the next active region. The secret number will be on the left
(top) half if the answer is no, and on the right (bottom) half if the answer is yes.
Shrinking the active region in this way will always yield a single number by the
fifth question.
Let’s try it out. If the number is 6, the answers would be: no, no, yes, yes,
no. So the active region starts out as 4 6 for the yes to question 3, and then
5 7
shrinks to the right half 6 for the next yes, and to the top 6 for the last no.
7
You should try the secret method with some other numbers to convince yourself
that it works. With just a little practice as MC you can give the answer before
the victim has even finished saying the last answer. That’s the magic. Nobody
would be impressed if the MC wrote down all the answers, thought for a few
minutes, and then answered correctly. Now, to decide if the method works, we
just have to try it with all thirty-one numbers. If it doesn’t work, we are done,
but what if it does work? We will still not know why it works, and have no clue
how the trick was ever designed in the first place.
So, just as with Wolf-Goat-Cabbage, we have a discrete problem, but is it
a problem in discrete mathematics? So far, the answer for both is no. What
is missing is the mathematical analysis of the problems. Just playing around
with discrete objects does not constitute mathematics, whether the objects are
numbers or not. And mathematical analysis is to be meant in the most general
sense, as in Problem 2, whose solution involved only evenness, oddness, and
Exercises
1. Order the problems in the list discussed in this section from least to most
discrete.
2. Consider methods people have of communicating. Identify three which are
essentially discrete.
Identify three which are essentially non-discrete.
Justify your responses.
3. Consider the following outdoor activities. Order them from least to most
discrete: jump-rope, frisbee, hopscotch, pogostick. Justify your ordering in a
few words.
O1 · O2 · · · · · On
The result seems clear, but when we applied it earlier no mention was made
of independence.2 If you have taken a course in probability, then the indepen-
dence idea is essentially the same. We say that the kth choice is independent of
the earlier choices if there is no sequence of choices c1 , c2 , . . . , ck−1 , such that
the kth choice is at all restricted from the full Ok options.
Were the choices in the Magic Trick independent? You would have to look
carefully at the cards to tell. But before you peak, just suppose that every number
occurring on the fourth card occurred at least once on one of the three previous
cards. Then the fourth choice would not be independent because it would not be
possible, after answering (no, no, no, _, _) for the first three cards, to answer yes
for the fourth card. In that situation, the choices would not be independent.
For the actual cards, we know that the answers must be dependent since the
victim chooses a number from 1 to 31, but the multiplicative principle predicts
25 = 32, so some sequence of choices does not occur.
In the absence of independence (or weak independence), the multiplicative
principle merely gives us an upper bound on the sequence of choices.
Exercises
1. An online order form for a winter coat allows you to choose up to four colors
for the coat, and four colors for an optional hood, and either ordinary or Red-
Sox themed buttons.
First give a guess as to the number of types of coats which can be ordered.
Then compute the number of different types of coats which can be ordered
2. You are in a restaurant and order the special, which has three choices of
appetizer, one of which is a salad with three choices of salad dressing. There
is a vegetarian option to the entrée and three choices of dessert.
Would you guess that ten different meals are possible?
Compute how many different meals can be ordered. Justify your response.
3. It is your first day of class and you have to fill out four feedback surveys orig-
inating from four different administrative offices, to measure your happiness
and efficiency.
The first survey has six true/false questions. The second and third surveys
were obviously edited with the same survey composition app, and both
have large animated smiley faces which read aloud to you twelve multiple
choice questions whose four alternatives are labeled comfortingly “choco-
late”, “sunsets”, “cuddle”, and “joy”. The fourth survey is exactly the same
as the first survey with the order of the questions shuffled – but it must be
filled out anyway.
How many different survey responses are possible?
The student must complete all surveys and nothing can be left blank.
5
6 9
10 11 1
3 15 2 14
7 4 8 12 13
Imagine placing the balls one by one from top to bottom, since any ball can be
in any position, it is tempting to take the number of options for the ith ball to
be Oi = 15. We will then get 1515 which will be a very generous upper bound
since the choices are not independent. Only the first placement has the full 15
options since no ball can be placed twice.
But it is not hard to see what to do next. Reset the number of options to take
into account the decreasing range of choice
We have almost solved the problem, but there is an interesting subtlety. Once,
say, ball 5 is chosen for the first position, that ball is no longer an allowable
choice to be placed in any of the other positions. But it would have been avail-
able if a different ball had been chosen initially. The available second choice is
dependent on the first one, and so are all the subsequent ones. On the other hand,
although the particular choices change, the number, Oi , of subsequent options
at each stage does not. Regardless of which ball was chosen first, there is the
same steadily decreasing number of choices after the first one; so by the same
argument we used before, the number of ways to rack the balls is the same as
the number of sequences of allowable choices, 15 · 14 · 13 · · · 2 · 1 = 15!.
We say that the kth choice is weakly independent of the earlier choices if,
regardless of what has been chosen so far, there are always Ok options available.
So the calculation above actually does follow from the Multiplicative Principle
(Theorem 1.1) as stated in the previous section.
Theorem 1.2. The number of ways to order n objects, with n > 0, is n!.
The factorial is defined by the familiar equations
1 k=0
k! = (1.1)
(k)(k − 1) · · · (1) k > 0
Choosing
Suppose we have a class of 11 kindergartners, and want to choose five of them
to take a bunch of flowers to the principal. How many ways are there to do
that? The teacher asks for volunteers, and all the kids raise their hands and wait
expectantly to be chosen. The teacher chooses the first kid, 11 choices, then for
each of these a second, weak independence giving 11 · 10, then a third 11 · 10 · 9,
a fourth 11 · 10 · 9 · 8, and finally a fifth 11 · 10 · 9 · 8 · 7. In particular, for little
Julie, it is very important to her not only to be chosen, but to be chosen first. If
she is not among the first three chosen, she might even throw a tantrum, and not
even be comforted if she is later selected fourth or fifth.
When the kids take the flowers down to the office, the principal notices of
course who has been chosen to bring the flowers, but has no interest in the order
in which they were chosen. All the 5! ways which the teacher had of choosing
those five kids, so important to little Julie, would be considered the same to the
principal.
So we have two answers to the counting problem. From Julie’s point of view,
there are
11!
11 · 10 · 9 · 8 · 7 =
6!
ways of choosing, in which the actual process of choosing is important, and for
the principal there are
11 · 10 · 9 · 8 · 7 11!
=
5! 5!6!
ways in which the manner of choosing not considered, only who was chosen.
The first is often called the ordered selection, and the second the unordered
selection. There
is a special notation for the unordered selection, in this case it
would be 11 = 11!/5!6!. Other notations, such as C 11 , are sometimes seen.
5 5
The numbers nk have been around for a very long time, and have been re-
discovered in many different contexts, so the notation and languagewhich has
evolved around them is a hodgepodge of that history. The number nk is most
often called a binomial coefficient, and the particular one referred to here is read
off as “n choose k”. That is often the source of many student, and non-student,
errors since the mathematical language does not mesh with the natural language
we use to express
the problems. So Julie, who cares so much about the choice,
does not use 11 5 to count from her point of view, but the other one. In English
you can get over this difficulty by, just to yourself, thinking of 11 5 not as “n
choose k”, but “n grab k”, since ‘grabbing’ has much more the connotation of
selecting altogether than ‘choosing’. (But don’t expect that if you say “n grab
k” that anyone else will know what you are talking about.)
Here is a summary:
Exercises
1. How many 10-digit decimal numbers (zeros in front ok) have at least five
1’s?
2. How many 10-digit decimal numbers (zeros in front ok) have exactly five
even digits (0, 2, 4, 6, 8)?
3. There is a drawer with three compartments, one filled with oil, one with
water, and one with gold paint. 15 billiard balls are to be distributed into the
drawers. How many ways are there to do this?
0
0
1 1
0 1
2 2 2
0 1 2
3 3 3 3
0 1 2 3
4 4 4 4 4
0 1 2 3 4
5 5 5 5 5 5
0 1 2 3 4 5
6 6 6 6 6 6 6
0 1 2 3 4 5 5
..
.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
in which you must not fail to identify the 20 at the bottom as 63 not 64 , since
it is only the 3rd entry on that row, “counting from 0”. The computed triangle
also makes plain the obvious mirror symmetry, because the number of ways to
grab k things from n things is exactly the same as the number of ways of letting
n − k things remain ungrabbed:
n n
= .
k n−k
It is also easy to show that the entries in each row increase to the middle, and
then decrease:
n n
< for k ≤ (n − 1)/2 (1.2)
k k+1
Computing the entries may seem tedious, since it involves so many multipli-
cations, and the numbers get big rather quickly. (How quickly? — Later.) But
there is an important shortcut for generating them. Each entry in Pascal’s trian-
gle which is not on the boundary, is the sum of the two entries right above it, one
to the left, and one to the right. For a binomial coefficient
not on the boundary,
n+1
both entries are at least 1, so let’s write it as n+1
k+1 The entry above k+1 and to
the right
n is
on the same forward diagonal, and so is in the same choose group,
so is k+1 , and the one to the left must be nk ; so we are claiming that
n n n+1
+ = . (1.3)
k k+1 k+1
There are several proofs of
this
key result. The one which follows now was
my professor’s favorite: For n+1
k+1 you want to grab k + 1 objects from n + 1
objects. Assume that one is precious, that
nit is made of gold. Either you grab the
golden object, or you don’t. There are k+1 ways to avoid the golden one. On
the other hand, once you have the golden one, there are nk to grab the ordinary
ones.
The preceding four sections are taken from a branch of discrete mathematics
called combinatorics. It is very useful, and your university probably has several
courses in just that.
Exercises
1. Write out
the
first 8rows
of Pascal’s triangle.
Circle 72 , 75 , and 84 .
100
2. Show that 10049 < 50 .
[Hint: decide if the
ratio
100is larger or smaller than 1.]
What about 100 50 < 51 ?
3. Check that
8 4 4 4 4 4 4 4 4 4 4
= + + + +
4 4 0 3 1 2 2 1 3 0 4
Can you find an explanation for this “coincidence”?
Can you find a similar statement for 12
6 ?
a decimal number like 1776 is represented by just four digits, the “digit” coming
from the Latin word for finger, by the clever system of scaling each of the digits
by a power of 10:
110,010,111 = 1 · 28 + 1 · 27 + 0 · 26 + 0 · 25 + 1 · 24 + 0 · 23 + 1 · 22 + 1 · 21 + 1 · 20 .
There is no standard about placing commas, and they are usually left out. Some-
times one adds a subscript, in this case 2, to indicate the number base of the
representation, especially if the base is not clear from the context: 810 = 108 =
223 = 10002 , which is somewhat inconsistent since the subscript is usually still
in base 10, but no system is perfect.
If you have never done so, it is instructive to list the 16 four-digit binary
numbers from 0000 to 1111 in order, and observe the developing pattern of 0’s
and 1’s, comparing it to what you would expect from the list of base 10 numbers.
You have probably heard that computers are fundamentally binary because
0 and 1 can represent “off” and “on”. And that still by and large is true, since
electrical circuits can easily be built like that, but many other architectures are
also possible. But even without that consideration, binary numbers would still
be of interest because of other fundamental dichotomies like “no” and “yes”,
“negative” and “positive”, “false” and “true”, etc.
For example, binary numbers play a fundamental role in Albertson’s Magic
trick, one of the problems we considered in Section 1.1. The “magic” was in
associating the sequences of yes’s and no’s for the five cards with the sequences
of bits of the binary numbers from 000012 to 111112 . So the number 2510 =
110012 would be associated with the object pictured on the zero’th, third, and
fourth card, but not on the first and second. The trick as presented takes as
objects the numbers themselves, undisguised beyond that they are represented
in base 10. The zero’th card consists of all five bit numbers whose zero’th bit is
1, the first card those whose first bit is 1, etc.
One can also do arithmetic on binary numbers. Binary numbers are added
and multiplied in the same way as decimal numbers, yet with many fewer digit
facts to be known, but many more carries. So 13 + 7 = 20 and 5 · 5 = 25 would
be done as follows:
1 0 1
× 1 0 1
11 11 01 1
1 0 1
+ 1 1 1
0
1 0 1 0 0
1 0 1
1 1 0 0 1
While it is true that the number bases 2 and 10 are by far the most popular, a
facility with others is often quite handy, or even essential.
Exercises
1. Let n = 1101101101 and m = 1110110110, be binary numbers.
Compute n + m, m − n, n/2, and n2 + 1 in binary format.
Compute 12123 + 21213 and 12123 × 21213 in trinary format.
2. How many 12-digit binary numbers between 100000000000 and 111111111
111 have at least 4 zeros?
4 2
3. Express 2(2 ) in binary. Express 2(4 ) in binary.
8 2
Try the same with 2(2 ) and 2(8 ) .
Since 1776 ≥ 210 , we must have that b10 = 1. That gets the first bit, and to
find the others, subtract 210 and continue in the same fashion for the remainder
1776 − 1024 = 754. In general, for the ith bit, if the number m remaining sat-
isfies 2i+1 > m ≥ 2i , we set the ith bit to one, and subtract 2i , otherwise we set
the ith bit to 0 and proceed with the same m, stopping only when the bit b0 is
determined.
Here is the precise description:
1776 = 2 · 888 + 0
888 = 2 · 444 + 0
444 = 2 · 222 + 0
222 = 2 · 111 + 0
111 = 2 · 55 + 1
55 = 2 · 27 + 1
27 = 2 · 13 + 1
13 = 2 · 6 + 1
6=2·3+0
3=2·1+1
1=2·0+1
1776 = 9 · 197 + 3
197 = 9 · 21 + 8
21 = 9 · 2 + 3
2=9·0+2
Exercises
1. Convert 6464 (decimal) to binary, using both methods. Show your work.
Convert 6464 also to base 8 (octal) and base 16 (hex, or hexadecimal. Use
A, B, C, D, E, F , for ‘digits’ 10, 11, 12, 13, 14, and 15). Use any method
you like. If you think for a minute or two, you might see that there is a trick.
2. Convert 6464 to base 3 and to base 5.
3. For base 3, you don’t have to use remainders 0, 1 and 2. Instead, you could
take remainders 0, 1, and −1. Since −1 is ugly to look at as a digit, we’ll
invent a font: one ↑ for 1; none 0 for 0; and mone (pronounced mun) ↓, for
−1.
So one mone none mone, or ↑↓ 0 ↓, or [1][−1][0][−1], represents the num-
ber 33 − 32 − 30 = 17.
Write out the first 20 numbers in one/mone notation.
Convert 1776 to the one/mone system.
The disks start all stacked, largest to smallest, on the post representing hell, and
your task is to move them, one at a time, from one post to another, so that in the
end the whole tower is moved to heaven. The restriction is, that you must never
place a larger disk on top of a smaller disc. So, for example, the merchant may
never be placed on top of the knight.
Can the task be done in fewer than 100 moves? What about 50 moves? What
is the most efficient method of solution?
As a first step, since the discs are stacked in decreasing size, and each legal
move preserves that property, we know that the configuration after any number
of legal moves has the discs stacked in decreasing size on the three poles. How
many such legal configurations are there? It is possible to use the multiplicative
principle to compute that number, and it is an upper bound on the number of
moves that it takes to complete the puzzle – why?
If you add up the rows of Pascal’s Triangle, from left to right, with each entry
scaled by an increasing power of two, they will sum to a power of three.
Let’s try:
4 0 4 1 4 2 4 3 4 4
2 + 2 + 2 + 2 + 2
0 1 2 3 4
= 1 · 1 + 4 · 2 + 6 · 4 + 4 · 8 + 1 · 16 = 81 = 34 .
Puzzling?
Here is another curious relation. You have certainly noticed that the rows of
Pascal’s triangle appear when multiplying polynomials:
noting that the 1 on either end of the row is often not written explicitly. These
two phenomena are coming from the same source, the Binomial Theorem. Bi-
nomial is not the name of a famous mathematician, it refers to a polynomial with
two terms, say p and q, so written as (p + q). The terms p and q may be individ-
ual letters, or something much more complicated, but regardless, the question
the Binomial Theorem addresses is, what happens when we take (p + q) to an
integral power?
Theorem 1.8. Let p and q be algebraic terms and let n be a positive integer.
Then
n
n k n−k
(p + q) =
n
p q .
k
k=0
the distributive law requires that you get one term resulting from, for each of
the n terms, a choice of p versus q. If n = 6 and you were alternating in your
choices, that would give you the term pqpqpq = p 3 q 3 . In general, if the number
of p’s you choose is k, then you have the term p k q n−k . How many times does
that
n
occur? Once for each way to choose k factors from all n factors, that is
. That is why, gathering them all together in the product, we have the term
nk k n−k
k p q .
This proof of the Binomial Theorem is only convincing if you have a thor-
ough understanding of how the distributive law works. We will see another proof
later on. The binomial theorem explains the two-three relation completely:
n
n
n k n−k n k
3n = (2 + 1)n = 2 1 = 2 .
k k
k=0 k=0
which state that the sum of the entries in any row in Pascal’s Triangle is 2 to the
power of that row number, and the alternating sum of the entries in any row of
Pascal’s Triangle must be 0. The last is obvious for odd rows by cancellation,
e.g., 1 − 3 + 3 − 1 = 0, but is certainly not obvious for the even rows like the
4th, which says, 1 − 4 + 6 − 4 + 1 = 0. There is a non-algebraic explanation for
this oddity in the next chapter.
Whenever you see it, you are encouraged to pause and think before reading on.
A favorite analysis is something like the following. There are nine squares
in the 3 × 3 array, with 8 on the outside, forming a ring. If you mentally deform
the ring, keeping the connections as they are, you can turn the 3 × 3 board into
a circle
and you can ignore the color of the central region, corresponding to the middle
square, since the knights never go there. They always stay on the boundary.
What does a knight’s move mean in this less familiar territory? If the moves
correspond to something very complicated, not matching the uniformity of the
circle, then this problem transformation will not be very helpful. (But even then,
the whole idea of “problem transformation” may make you think of something
even more clever!)
If you are ahead of me and have already tried it, then you have discovered
that knight moves on the 3 × 3 board transform very nicely indeed to rotations
of the knight around the ring by 135◦ , 3/8 of the way around, clockwise, or
counterclockwise. And that is just the hint you need. It says that the natural
thing to do is not to try to reflect the knights across the line of symmetry, but to
turn them around 180◦ degrees. As in the diagram below:
That means 4 moves for each knight, 16 altogether. That seems like a lot of
moves for this little problem, but if you paused at the symbol and tried on
your own, you probably gave up after many more moves than that! It is natural
to start trying to move the knights directly across, since an individual knight
with nothing in the way requires only two moves to cross, but the group of four
get in each other’s way very badly with that approach.
FIGURE 1.1 a) An ancient puzzle. b) Reduction: Spelling “murder” in the (SE) quadrant.
As you start to think of how to count the ways, you quickly abandon the idea
of actually listing them all. A methodical counting is clearly required. And as
you work out a strategy, pay particular attention to how the puzzle might involve
the multiplicative principle, and Pascal’s Triangle.
It is because the center is the only location to place a single checker so that the
board has rotational symmetry. Most people have a poor eye for 180◦ symmetry,
and so it is possible for this simple strategy to go undiscovered by the opponent.
On the other hand, you may find that 180◦ may be awkward to adhere to. Mirror
symmetry is much simpler to recognize and employ, but it is possible for the
second player to defeat a mirror image strategy. How?
It is said that Catherine de’ Medici knew and used the 180◦ strategy, but was
stymied when it was proposed to play the game with eggs instead of checkers.
She was at a loss for a first move until she thought of jamming the first egg,
hard boiled, firmly upright on its end in the middle of the board. After that, she
proceeded to win, tit-for-tat.
Cramcheck has continuous and discrete aspects, but the game of nim is com-
pletely discrete and has a similar tit-for-tat strategy. Nim starts with a quantity of
coins, distributed into piles. The two opponents take turns. Each player selects
one pile, and removes from that pile as many coins as he pleases, being sure to
take a least one. He may take the whole pile, but he may not alter any other pile
in that turn. The winner is the one who takes the very last coin. The game may
be played with large numbers of coins, say 50 coins in 10 piles of 5, or just a
few, say 15 coins in piles of 1, 2, 3, 4, and 5. Why not try?
If there are an even number of piles, with the numbers of coins occurring in
pairs, like 22, 75, 75, and 22, then the second player can win by copying the first
player, tit-for-tat. If the piles are almost balanced in pairs, like 22, 75, 100, and
22, then the first player can win by balancing the collection, that is, taking 25
coins from the pile of 100, and then following his opponent tit-for-tat.
But what if the piles are more random, like 65, 85, 19, and 21? The piles of
coins seem so far out of balance that we might have to consider several layers of
moves and countermoves. But, actually, the first player can “balance” them in a
single move! The balancing principle is not obvious. It is hidden in the binary
representations of the numbers of coins in the piles.
Given k piles of coins with pi coins in pile i, the collection of piles is in balance
if the number of 1’s in each bit position of the binary representations of p1 , p2 ,
. . ., pk is even.
In the example, the four piles are out of balance because of the bits in the
21 and 23 positions. Changing the bit in the largest out-of-balance position, 23 ,
from a 1 to a 0, such as for 85, 19 and 21, means decreasing the number of coins
in the altered pile, even if bits in smaller positions are increased from 0 to 1.
Once the pile to be altered is chosen, the number of coins to be left in that
pile follows the rule: The bit in position 2i is set to be 1 if the number of 1’s in
the 2i position for the remaining piles is odd. It is set to be 0 otherwise. This
balances the piles, and if balancing requires the largest bit to be altered being
changed from 1 to 0, the new value is smaller, and the change is made by taking
away coins.
Note that an odd number of piles can be in balance!
For the example, you get to a balanced position, and are on your way to
winning the game, if you take 14 coins from either the pile with 85 or the pile
with 21; or if you take 18 coins from the pile with 19. (If you apply the balance
rule to the pile with 65 you can balance the piles, but by adding 10 coins!)
If the opponent makes a move with the piles in balance, no matter which pile
he chooses or how much he takes, the result leaves the piles out of balance. Then
the next player can restore them to balance in the same way as before, ending
with the piles being put into balance by the taking of the last coin. The player
balancing the piles has won the game.
The tit-for-tat strategy for Nim is not practical without practice or without
being completely comfortable with binary numbers. For good simple test cases
to try with a partner, piles with three consecutive two digit numbers are recom-
mended, like 22, 23, and 24.
X = {m , i , s , p } = {i , m , p , s } = {m , i , s , s , i , s , s , i , p , p , i }
Special sets
The following sets are used throughout mathematics and computer science and
each has a special symbol. Most of our sets will be built from these.
Naturals The set of all natural numbers, the non-negative whole numbers, is
denoted by N = {0, 1, 2, 3, . . .}. So 3, 0, 1776 ∈ N and −1, 3/4 ∈ / N. (Beware
that we are taking 0 ∈ N. Other texts may differ.)
Integers The set of all integers, positive and negative whole numbers, is de-
noted by Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}. So 3, 0, −2223 ∈ Z, but −22−23 ,
−π/4, and ∞ are not elements of Z.
Rationals The set of all rational numbers, described as integer fractions or as
those decimals numbers which, after the √ decimal point, are finite or repeating,
is denoted by Q. So −1 ,
2 7
22
, 0.3532 ∈ Q. 2∈ / Q.
Reals
√ The set of all real numbers is denoted by R. So π, e, γ , 17762 ∈ R.
−1 ∈ / R.
The Empty Set The empty set is the set with no elements. It is written {} or,
preferably, with the special symbol ∅. The empty set is an essential component
in the theory of sets, and it must be handled and notated correctly. The empty
set has cardinality zero, |∅| = 0.
In addition to these, the following sets, primes, digits, bits, letters, will ap-
pear throughout this text.
Primes The set of all prime numbers, P, natural numbers at least 2 whose only
non-negative factors are themselves and 1.
Digits The set of all (decimal) digits, D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Bits The set of all (binary) bits, B = {0, 1}.
Alphabet The set of all 26 characters in the Roman alphabet, A = {a, b, c, d, e,
. . . , x, y, z}.
Bracket notation
In the previous section the listing notation started to fail us. A list which relies
on ellipses, the . . ., cannot really be said to properly specify its contents. Part of
this difficulty we will resolve later, when we specify sets recursively. In general,
a more valuable notation for an infinite set, or a large finite set, is the bracket
notation. One specifies first either the notation for the elements to be specified,
or a known set where the elements are to be taken from, and ends with a list of
properties which determine the membership in the set to be defined. Separating
the two parts is the | symbol, which is to be read as “such that”. So the notation
looks like this:
{x ∈ A | property 1; property 2; . . .}
or
{x | property 1; property 2; . . .}.
So {n ∈ Z | n < 10; n ≥ 0} describes precisely the set D.
Using this notation, we can specify the rationals in terms of the integers by
writing
Q = {p/q | p ∈ Z; q ∈ N; q = 0}.
If instead we write
Q = {p/q | p ∈ Z; q ∈ Z; q = 0}
then we get exactly the same set, but with more duplicates, more elements of
the set satisfying the conditions of membership in different ways.
Exercises
1. Which of the following sets are, in your opinion, well-defined? Justify your
response in a word or two.
— The set of football teams
— The set of ping pong balls
— The set of hairs on your head
— The set of laws in the USA
2. Which of the following sets are, in your opinion, well-defined? Justify your
response in a word or two.
a.
The set of integers which are products of two primes.
b.
The set of game positions in chess.
The set of all real numbers whose absolute value is greater than −1.
c.
d.
The set of integers which are useful in the study of the game Go.
e.
The set of integers which, when spoken aloud, cause a genie to appear
and grant you three wishes.
3. Write each of the following in set notation, without words if possible: (Your
answers will vary.)
a. A, the set of odd integers
b. B, the set of real numbers whose square is an odd integer
c. C, the set of rational numbers which are an integer power of π
d. D, the set of real numbers with a decimal representation using only digits
5 and 6
Showing A ⊆ B
To show that A ⊆ B, one must check every single element of A for membership
in the set B. This is fine for very small sets, but is not generally practical. What
is more effective is, if A is given by properties, you consider a general element
of A, (“Let a ∈ A”); then note the properties which a must satisfy because of
its membership in A; then show that, because of those properties, a satisfies the
properties required for membership in B; allowing you to finally conclude that
a ∈ B.
So, for instance, let’s establish that Z ⊆ Q. Recall that Q = {p/q | p ∈ Z; q ∈
N; q = 0}. Let k ∈ Z. We also have 1 ∈ N, and since k = k/1, and 1 = 0, we have
k ∈ Q, as required.
Definition 2.1. The power set of a set A, denoted by P(A), is the set of all
subsets of A, P(A) = {X | X ⊆ A}. ♠
So the elements of P(A) are themselves sets. This is not an unusual situa-
tion, or a weird special case. It often arises, and makes even more essential that
you are careful about using the correct vocabulary for the different notions of
containment.
Example 2.2. If X is a finite set, say X = {i, m, p, s}, then X has only a finite
number of subsets and we can easily list them all. Of course X ⊆ X. Don’t let
the “sub” in subset mislead you. Equality is clearly allowed by the definition.
The subsets with smaller cardinality are obtained by removing elements of X;
cardinality 3, {i, m, p}, {i, m, s}, {i, p, s}, and {m, p, s}; cardinality 2, {i, m},
{i, p}, {i, s}, {m, p} {m, s} and {p, s}; cardinality 1, {i}, {m}, {p}, and {s}; and
finally we are forced to consider the set with all elements removed, the empty
set, {}.
P(X) = {{i, m, p, s}, {i, m, p}, {i, m, s}, {i, p, s}, {m, p, s},
{i, m}, {i, p}, {i, s}, {m, p}, {m, s}, {p, s}, {i}, {m}, {p}, {s}, {}}.
The last subset considered, {}, cannot be omitted. In total |P(X)| = 16. ♦
For any set A, it is true that ∅ ⊆ A, since ∅ contains no elements to violate
the subset condition. As we saw in the previous example, it can also happen that
the empty set is an element of a set. So ∅ ∈/ {i, s, m, p}, but ∅ ∈ P({i, s, m, p}).
The set P({i, s, m, p}) has sixteen distinct elements, and one of them is ∅,
so ∅ ∈ P(X), {∅} ⊆ P(X) and, look carefully at this, |{∅}| = 1. The empty set
is not “nothing”. It is a set, so the fact that it is an element of {∅} counts. In
particular, ∅ = {∅}!
Definition 2.3. The set of k-subsets of a set A is defined by
For example, P2 ({i, s, m, p}) = {{i, m}, {i, p}, {i, s}, {m, p}, {m, s}, {p, s}},
and the set Pk (A) will be empty if |A| < k. What is Pk (A) for k = 0?
|P(A)| = 2|A|
since you can choose independently for each element of A whether or not it is
in the subset to be considered, and membership is the defining quality for any
set. Notice that choosing no for each element A is counted as a legal sequence
of choices, and that would be specifying the empty set.
To compute the cardinality of the set of k-subsets, |Pk (A)|, with k ≤ |A|, we
can also use the multiplicative principle. In fact, we have already done so, since
those subsets may be regarded as being obtained by an unordered selection of k
objects from |A| objects;
|A|
|Pk (A)| = .
k
In fact, this gives us a much better insight into many problems than the idea of
unordered selection. We don’t have to imagine artificially choosing the elements
of the subset. They are just there in the subset.
We can use the formula for the cardinality of the power set to predict the
number of elements in the sets P(∅), P(P(∅)), P(P(P(∅))), etc. We have al-
ready noted that |P(∅)| = 1 = 2|∅| , so it is consistent with that formula. There-
fore we must have |P(P(∅))| = 21 = 2. What are the two elements? We know
that the whole set, and the empty set must be subsets of every set, and for ∅ they
are the same set. For {∅} they are different: P(P(∅)) = {{∅}, ∅}. Continuing,
|P(P(P(∅)))| = 22 = 4. Try to write all four of them down. Be very careful of
the notation. (You will see that {∅} and {{∅}} are also different!)
Nothing prevents us from going further, and finding |P(P(P(P(∅))))| =
24 = 16, and then |P(P(P(P(P(∅)))))| = 216 = 65,536. You can stop there,
because the power set of that set has 265,536 elements, which I learned in school
was more than the number of atoms in the whole universe, but the universe
might have gotten bigger since then. We can hardly avoid being awestruck at
the progression, creating an increasingly complex variety of concepts from just
the contemplation of the empty set. This mathematical “big bang” was attention
getting when first discovered for the same reason that big bang is compelling in
physics. Mathematicians, logicians, and philosophers contemplated being able
to generate all of the intellectual universe from nothing. (It’s not so easy!)
Exercises
1. a) List all the elements in P({a, b, c, d}).
b) List all the elements in P2 ({a, b, c, d, e}).
2. Find three distinct elements in each of the following sets: You must use cor-
rect notation.
• P(P({a, b}))
• P2 (P(Z))
• P3 (P2 (P1 (Z)))
• P(P(P(∅)))
3. Show that P2 ({1, 2, 3, 4}) ⊆ P({1, 2, 3, 4, 5, 6}).
Is P2 ({1, 2, 3, 4}) ⊆ {1, 2, 3, 4, 5, 6}?
It is important to understand that the “or” used in the bracket notation of the
definition is meant in the scientific default, in other words, one, or the other, or
both. This is the inclusive or, which is contrasted with the exclusive or which
one hears in the restaurant when you are asked if you would like the vegetarian
or the non-vegetarian entré. In this text, specifically, every “or” is presumed to
be meant inclusively.
Example 2.7. With the same example A = {1, 0, a}, and B = {a, b, c, 0, π}, it
is not so easy to simply write down the intersection. It requires work. I must
check each candidate element of A for membership in the set B before it can be
placed in the intersection. A ∩ B = {0, a} records the result. ♦
knew what was meant, and chose automatically which of the meanings to take,
probably not even noticing the ambiguity. And that ambiguity was not in the
sketchy word “or”, but in our good friend “and”. This is normal. It happens all
the time if we communicate in natural language, which we must if we want to
work on problems which occur in the natural world. One of the purposes of the
use of set theory is to give us an unambiguous mathematical vocabulary to avoid
confusion. You lose all the advantage if you always take the precise set theoretic
formulation and re-express it back in familiar natural language and work with
that. You will end up just fooling yourself. You want to gain a facility with the
proper use of this new vocabulary, so don’t try to avoid it.
Definition 2.8. The complement of the set A, denoted by Ac , is defined by
Ac = {x | x ∈
/ A}. ♠
The complement is a unary operation, like the power set, in that it acts on a
single set to create a new set. The union and intersection are both called binary
operations. The complement has a few issues in its definition and requires some
care, and the notation for the complement has not reached the same degree of
standardization as the union and intersection. Another popular notation is Ā, but
there are other important concepts competing for the overbar.
Example 2.9. Let A = {1, 0, a}, and B = {a, b, c, 0, π} again. Clearly we have
π ∈ Ac , and a ∈ / B c . But we have
√ some curious things happening here, too.
We have ∅ ∈ B c , {∅, {∅}} ∈ B c , −1 ∈ Ac , and P ⊆ Ac . Yes, these are truly
gigantic sets, which they have to be. For Ac , the query as to membership will be
answered almost always “yes” except for the three queries associated with the
number 1, the number 0 and the letter a, where the answer as to membership in
Ac is “no”. ♦
The situation of the previous example suits many situations which mathe-
maticians encounter. But, practically, the complement is often encountered in
the context of a particular collection of elements outside of which we have no
interest. You may have restricted your attention to words in a computer program
which you are writing, or characters in a game you are developing. This par-
ticular set is called the universe, and usually denoted by U. If you are working
with a universal set, then all elements from all sets you consider while working
in that universe are drawn just from that universal set, U. You can work in a
large numerical universe consisting of numbers and sets of numbers, such as
R ∪ P(R) ∪ P(P(R)) ∪ . . ., or you may prefer to do work in a tiny universe
like U = D ∪ A. For that tiny one, Ac = {x ∈ U | x ∈ / A} and consists of just
33 elements, i.e., those digits and letters not equal to 0, 1, or 1a, which for
that universe is a lot. For this meaning of the complement it is also said that
Ac is the complement of A relative to U. If the universe is a finite set, then
|Ac | = |U| − |A|.
Definition 2.10. The Cartesian product of two sets A and B, notated A × B, is
defined by A × B = {(a, b) | a ∈ A; b ∈ B}. ♠
The Cartesian product is another binary operation but, like the power set, the
Cartesian product results not only in a new set of elements, but in a set whose
elements are a new type of thing, ordered pairs, of existing elements.
Example 2.11. Again with the same example sets A = {1, 0, a}, and B =
{a, b, c, 0, π}, in order to create A × B we have to, for each of the three el-
ements allowed to be in the first coordinate of the pair, place any of the five
allowable elements of B into the second coordinate, so A × B will have fifteen
elements
A × B = {(1, a), (1, b), (1, c), (1, 0), (1, π), (0, a), (0, b), (0, c), (0, 0), (0, π),
(a, a), (a, b), (a, c), (a, 0), (a, π)}.
Notice particularly that (a, a) and (0, 0) are included because a, 0 ∈ A ∩ B, but
no other pair of identical coordinates is included. Notice also that, even though
(a, a) ∈ A × B, a ∈/ A × B. ♦
Exercises
1. Let X = {0, ∅} and Y = {∅, π}.
a. List all elements of P2 (X ∪ Y ).
b. List all elements of P2 (X ∩ Y ).
c. List all elements of P2 (X × Y ).
2. Let A = {0, 2, 4, 6, 8}, and B = {1, 3, 5, 7, 9}.
a. List five different elements of A × (B × (A ∪ B)).
b. How many elements does this set have? (Use the multiplicative princi-
ple)
3. Let P = {a, b, c}, Q = {c, d, e} and R = {e, f, a}.
a. Find all elements of P((P ∩ Q) × (Q ∩ R) × (R ∩ P )).
b. Find all elements of P(P ∩ Q) × P(Q ∩ R) × P(R ∩ P ).
A∪A = A A∩A = A
A∪∅ = A A∩∅ = ∅
A∪B = B ∪A A∩B = B ∩A
A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∩ C) = (A ∩ B) ∩ C
(Ac )c = A ∅c = U
(2.1)
Distributive laws
Just like in ordinary algebra, where multiplication distributes over addition and
gives the identity a(b +c) = ab +ac, the set operations also satisfy a distributive
law. For sets the law works more generally in that ∩ distributes over ∪ and also
∪ distributes over ∩. So, for sets A, B and C:
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
De Morgan’s laws
The interaction of the complement with the basic operations is expressed in De
Morgan’s laws. For all sets A and B:
Theorem 2.12 (Condition for Set Equality). Two sets A and B are equal if and
only if A ⊆ B and B ⊆ A are both true.
Proof. The assertion hardly merits a proof. If the sets are equal, then the subset
relations hold because every set is a subset of itself. On the other hand, if each is
a subset of the other, then neither can have any element which the other does not
have, so the sets have the same elements, which means that they are the same
set.
The reason this obvious result comes up so often is that, generally, deciding
whether two collections are exactly the same requires us to divide our attention
between two sets, possibly different, at least specified in different ways, com-
paring all their many elements having perhaps many duplicate specifications. It
is very easy to get confused. Dividing the task into two parts helps right there,
but even more, showing the subset relation, instead of set equality, allows us
to focus our attention on one element and its properties, rather than the whole
set. Using the theorem in this way is such an essential trick that we call it the
Double Inclusion Method. This method comes up very often when people sus-
pect that they are looking at the same thing in two different ways. We devote
the next section to the method, where we apply it to simple examples mostly
based on the identities stated in this section. But keep in mind, it is Condition
for Set Equality, Theorem 2.12, which is important, and it is the double inclu-
sion method which we are trying to get practice using, not the simple identities
we are applying it to.
Exercises
1. Suppose A ⊆ B ⊆ C. Show that (A × B) ⊆ (B × C).
a. Use the method we discussed of showing the subset relation.
b. Need it be true that (B × C) ⊆ (A × B)?
2. As part of using the double inclusion method to show that A ∪ (B ∩ C) =
(A ∪ B) ∩ (A ∪ C) we would have to show A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C)
for any sets A, B and C.
Show A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C).
3. As part of using the double inclusion method to show that A ∪ (B ∩ C) =
(A ∪ B) ∩ (A ∪ C) we would have to show A ∪ (B ∩ C) ⊇ (A ∪ B) ∩ (A ∪ C)
for any sets A, B and C.
Show (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C).
[Hint: The two cases x ∈ A, and x ∈
/ A make the argument simpler.]
Commentary: The first thing to notice is “Let x”. You want to show that
the subset relation holds, so you have to show that each element of P(A) is
contained in the other set. You cannot do it by checking elements one by one.
You don’t even know which set A is referred to. Instead, you take a general
element, call it something, x, and then restrict your attention to that x, and the
properties it inherits from membership in P(A). Then you use those properties
of x in order to show that x also has the qualities required for membership in the
other set. This is the power of the double inclusion method mentioned at the end
of the last section; that we can focus on an individual element and its properties,
instead of the two sets and their many elements.
The second thing to notice is “as required”. Required by whom? If you are
the proof writer, then it is you who made that requirement when you announced
that you were going to show set containment, and made the first “let”.
The third thing to notice is that you can probably think of many ways that
you might have written this proof differently; maybe easier to follow, perhaps
shorter. Maybe you don’t like that I chose x for the general element when, since
it turned out to be a set, it could be clearer to use X. Maybe you think there
should be a little more detail, or a little less. Even in model proofs like this there
is room for expression, personality, and style. How do you avoid freezing up,
paralyzed by the choices? I think it helps tremendously to turn your attention
from yourself to the reader, and what the reader needs to be told. All a proof
is, ultimately, is a convincing argument – an argument convincing to an open
minded, but sceptical reader – someone willing to be persuaded, but only after
being convinced that the argument is sound and in which every detail is actually
correct. That is how you should listen to proofs.
And what if you, the reader, don’t agree? What then? It can happen that you
see an error and you can explain the problem. But probably not. Likely as not
you don’t follow the argument because it is too complicated for you, or because
the writer is confused and has made a mistake, or because there are differing
definitions. But whatever the reason, you cannot accept the result as having been
proven. That doesn’t mean you can conclude the assertion is false, just that you
are unconvinced by that argument.
Next, I will show you how to completely destroy the first half of the proof:
. . . . . . P(A) ∩ P(B) ⊆ P(A ∩ B). x ∈ P(A) ∩ P(B), x ∈ P(A), x ∈ P(B), x ⊆ A,
x ⊆ B, x ⊆ A ∩ B, x ∈ P(A ∩ B) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
This is by far the most common student mistake. The idea seems to be that a
proof gets more mathematical, and shorter, and truer, if you just leave all those
non-mathematical words out. But if you leave the words out, you leave the whole
argument out! Look at all those bare equations, some of which were goals to be
done, some just assumptions for the sake of argument, some conclusions. They
are now just asserted altogether as bare facts. As a proof, it must be wrong. You
cannot convince without an argument. So you might as well try putting in the
words and risk making a poor argument, rather than leaving them out and be
sure that it fails.
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
holds, and you would be wasting your time to add a third case to handle what
has already been done twice, even though it is valid to do so.
Our third proof moves us just a bit beyond the set identities which we are
using for practice. X will be the set of all even natural numbers, and Y and Z
those numbers divisible by 3 and 6.
Commentary: Many people don’t like that the letter z from the first half was
recycled in the second half for a different number. But one finds that in double
inclusion proofs quite often.
Exercises
Assertion: Let A be a set. Then A = P(A).
Proof: Part 1: Clearly A is in P(A), so A ⊆ P(A).
Part 2: Now to show P(A) ⊆ A. Let X be contained in P(A). Then every
element of X is contained in A, so X is contained in A. Since everything in
P(A) is contained in A, P(A) ⊆ A.
Part 3: Since P(A) ⊆ A and A ⊆ P(A), we have P(A) = A.
1. Find any flaws in Part 1 that you can.
2. Find any flaws in Part 2 that you can.
3. Find any flaws in Part 3 that you can.
Once we have the set of all sets, we can easily construct a universal set big
enough to suit to anybody anywhere by
U = {x ∈ S | S ∈ S}.
But S has a property not seen in any of the sets we have considered so far.
The set S is an element of itself: S ∈ S. This looks familiar, but isn’t. It is the
relation A ⊆ A which is true for all sets; every set is a subset of itself. What
about power sets? For any of the sets we have considered, X ∈ P(X), but we
have never had P(X) ∈ P(X), instead having P(X) ∈ P(P(X)).
Let’s try to build a small example, a set containing just itself and the num-
ber 1. So 1 ∈ X and X ∈ X, which gives X = {1, X}. That looks ok at first, but
then that says X = {1, {1, X}} = {1, {1, {1, {1, . . .}}}} and it is hard to figure out
what the . . . even means. After all, what is that other element? We seem to be
stuck. These guys seem not so easy to construct.
Suppose you are a conservative person, and this property makes you uncom-
fortable, and you don’t want to consider such sets. You might want a restrict
yourself to sets which are more ordinary:
R = {X ∈ S | X ∈
/ X}.
R looks much safer than S. R contains precisely those sets which are not ele-
ments of themselves.
But what about R itself, is R ∈ R? On the one hand if R ∈ R, then R fails to
satisfy the property specified in its definition for membership, so we would have
to conclude, contradictorily, that R ∈ / R. On the other hand, if you surrender and
accept that R ∈/ R, then R passes the requirement for being an element of the set
R, and we are confronted again with the reverse, R ∈ R. So we have arrived at
an impasse, a contradiction. Normally that is ok. Arriving at a contradiction just
means that some assumption which we have made is incorrect. Identifying the
false assumption is progress. But here we don’t seem to have assumed anything
at all. We were just getting started constructing things.
If this makes you scratch your head, you are not alone. This conundrum
was a bucket of cold water in the face of many people when Bertrand Russell
expounded it a century ago, and it is called Russell’s paradox. The problem was
quickly identified as resulting from the fact that the set S refers to itself in its
own definition; a trick used in other linguistic problems long known to logicians
and philosophers. That is what we encountered with {1, {1, {1, {1, {1, ????}}}}}.
There are essentially three ways out of this problem. One is to avoid self-
reference by forcing sets to be in a hierarchy, in other words, elements belong
to sets, sets belong to classes, classes belong to super-classes, etc. The second
way out is to make set theory axiomatic, as is done with Euclidean geometry,
where you seem to be proving theorems about points and lines in space, but you
are actually proving things about “points”, and “lines”, in a closed system of as-
sumptions. We will follow the third way, which is what is done by most people
who simply want to use sets to solve practical problems – which is to start with
the elements we are interested in, numbers, sets of numbers, letters, game char-
acters, words in a computer program, etc.; then expand this working universe as
necessary, and not even attempt to contemplate a whole and complete system.
So the moral of this very abstract story is, beware of definitions which refer
to themselves and, the universe is actually important.
Exercises
1. Overheard conversation between Pat and Mike:
Pat: Mike, you always lie.
Mike: Yeah, and I am lying right now.
Who is telling the truth?
2. Sign at the bus stop:
The sentence below is true.
The sentence above is false.
Which of these lines is true?
3. Which of these three problems involve self-reference?
perhaps better rendered than in this hand drawing by Johannes Kepler from back
in the day when four elements, earth, water, air and fire, seemed plenty. Other-
wise, all but one of these interesting objects, the common cube, are probably
unfamiliar to you.
One of the reasons people have been fascinated by these five objects is the
fact that there are only five. There may be an infinite number of interesting three
dimensional solids, but these are the only ones all of whose hedra, faces, are
congruent regular polygons, with the same number of polygons coming together
at each vertex.
In general, polyhedra may be thought of as being obtained by starting
with all of continuous three dimensional space, and methodically cutting away
chunks of it, leaving a solid with a finite number of flat faces on its surface where
the cuts were made. Of course, most polyhedra will not be regular or symmetric,
but in this case study we will only look at symmetric examples.
How do we make this idea of cutting away space precise? With set theory.
Instead of a knife, we use a set called a half-plane and instead cutting, we in-
tersect. A plane does “cut through space” with points on either side. Let v be a
point not at the origin, and let Pv denote the plane through v and perpendicular,
or orthogonal, to the segment from the origin to v. If you know some vector
algebra, Pv = {x ∈ R3 | x · v = v · v}, and the half-plane which Pv bounds and
which contains the origin is Hv = {x ∈ R3 | x · v ≤ v · v}. The cube can now be
expressed as the set C = Hi ∩ Hj ∩ Hk ∩ H−i ∩ H−j ∩ H−k . This is more than
a mere description. The set theoretic interplay of six cutting planes of C holds
the key to C’s “cubyness”. The top square face of the cube is fk = Pk ∩ C, just
one of the six faces of C.
The surface of the polyhedron, besides the finite set of faces, F , also has a
finite set of edges, E, line segments obtained from the intersection of two inci-
dent faces. For example, in C, find fk ∩ f−j . There is also a finite set of vertices,
V, whose elements are singleton sets of the form v = {(x, y, z)} corresponding
to isolated points where three or more faces have an non-empty intersection, see
Fig. 2.1, where faces f1 and f2 intersect in edge e, and f1 ∩ f2 ∩ f3 = v.
Given a set of labels of one type of object, set operations allow us to generate
natural labels for the others. For example, for the cube, take the eight vertex
labels to be V = {a, b, c, d, A, B, C, D}, always choosing the capital and lower
case version of the same letter to be opposite, and never labeling the endpoint
of any edge with letters of the same case.
Once the vertex labels are chosen, it is natural to label the elements of the
edge set E from the set P2 (V), labeling each edge with the pairs of vertex labels
for the endpoints of that edge. For our cube, the elements of the set E consist
of pairs, one upper case and one lower case, never belonging to the same letter.
The twelve edges have labels:
E ={{A, b}, {A, c}, {A, d}, {B, a}, {B, c}, {B, d},
{C, a}, {C, b}, {C, d}, {D, a}, {D, b}, {D, c}}.
{{A, B, c, d}, {A, C, b, d}, {A, D, b, c}, {B, C, a, d}, {B, D, a, c}, {C, D, a, b}}.
{{A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}}.
and the triangular faces are labeled by all 43 elements of P3 (V) = {{A, B, C},
{A, B, D}, {A, C, D}, {B, C, D}}.
There are 62 = 15 2-subsets of V, and all correspond to edges except {A, a},
{B, b}, and {C, c}.
Nice labeling choices for the icosahedron and the dodecahedron exist, but
are harder to motivate and describe.
No matter how their constituent parts are labeled, the five platonic solids all
satisfy
|V| − |E| + |F | = 2,
which turns out to be true not only for the five platonic solids, but all three-
dimensional polyhedra (cf. Theorem 9.14).
It seems no more than a coincidence that the number of regions for 5 points
is a power of 2, until one notices that the same is true for all the examples in
Fig. 2.3 except the last one. In fact, the first five cases all follow the simple
formula 2|V |−1 for the number of regions. Unfortunately, it is easy to count that
the last one has only 30 regions, not 32, which would be the next power of 2.
The last diagram does have that special point, the point in the very center,
where three diameters meet. Perhaps we have that special point at the cost of
The Missing Region Problem asks: Can we perturb again so that the missing
32nd region appears?
The method most people use is to try various combinations mostly at ran-
dom. A generally successful approach of this kind is to fill in first about half the
pieces, and then try to methodically vary the placement of the remainder to com-
plete the cube. For many puzzles, committing to a partial solution and trying to
complete from there would be a very bad strategy since it is common for puzzle
designers to allow only for a unique solution. But Soma has 240 ‘solutions’.
One question is whether mathematics helps speed up the solution process.
A more ambitious problem is to find and enumerate all possible solutions up
to symmetry. A quick and dirty computer program could be written to exam-
ine all the combinations of possible positions of each of the pieces and check
for compatibility. Unfortunately, unless one takes care, this approach yields a
combinatorial explosion. You may compute that the second piece in Fig. 2.5,
for instance, may be placed in the 3 × 3 × 3 cube in 144 ways. A more success-
ful approach is to apply a “branch and bound” strategy to avoid reconsidering
rejected configurations for different reasons. The most sophisticated computer
to have completely enumerated all possible solutions consisted of two self-
programming parallel organic processors, John Horton Conway and Michael
J.T. Guy, coming together in 1961, the job taking all of a Saturday to com-
plete.
The most important observation to simplify this problem is to notice that
the set S of 27 subcubes of a solution is partitioned into 4 subsets, S = V ∪
E ∪ F ∪ C, having empty intersection with one another, corresponding to the
different parts of the cube. The set V contains the 8 subcubes at the vertices of
the large cube, the set E the 12 subcubes at the edges, the set F the 6 subcubes
at the face centers, and C the one subcube at the center. It helps to imagine the
subcubes of different sets in different colors. Another interesting partition is the
‘checkerboard partition’, S = (V ∪ F ) ∪ (E ∪ C). The set V ∪ F has cardinality
14 and we’ll imagine its elements colored red, and the set F ∪ C has cardinality
13 and we’ll imagine its elements colored blue.
Let’s consider the red/blue coloring with regard to the individual Soma
pieces. There is a 4-subset of the set of pieces which must be colored two blue
and two red in any solution, see Fig. 2.7. That leaves 6 red and 5 blue to be
accounted for with the three elements of the complement, the subset of biased
pieces. Two elements of that subset, look in Fig. 2.5 for which ones, must have
either three red and one blue, or the reverse. They both cannot be biased in the
same way, since then those two pieces would account for 6 cubes of one color
all by themselves.
Thus the two larger biased pieces must be biased oppositely, their bias can-
celing one another out. Therefore it must be true that the little piece must be
biased in favor of red.
So we have found two conditions which obstruct a partial solution ever being
completed. (There is another nice one you can find by considering the corners
alone.) If the two larger biased pieces are placed so that their biases do not
cancel, it is impossible to complete the Soma cube, just like if the smallest piece
is not placed to be biased in favor of vertex/face positions. If your start has
violated either of these, you may as well disassemble and restart from scratch.
(A ∩ B ∩ C) ⊆ (A ∪ D) ∩ (B ∪ D) ∩ (C ∪ D).
(A ∪ D) ∩ (B ∪ D) ∩ (C ∪ D) ⊆ (A ∩ B ∩ C)
(A ∪ B) ∩ (C ∪ Ac ) = (A ∩ C) ∪ (B ∩ C) ∪ (Ac ∩ B).
(A ∪ B) ∩ (C ∪ Ac ) = (A ∩ C) ∪ (B ∩ C) ∪ (Ac ∩ B).
X ∪ (Z ∪ Y ) = (Y ∪ X) ∪ Z.
9. Let A and B be sets. Prove carefully by the double inclusion method that
Ac ∩ B c = (A ∪ B)c .
10. Let X, Y , and Z be sets. Prove using the double inclusion method that
X ∩ (Y ∪ Z) = (X ∩ Y ) ∪ (X ∩ Z).
11. Let X, Y , and Z be sets. Prove using the double inclusion method that
X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ (X ∪ Z).
12. Let A and B be sets. Either prove carefully by the double inclusion method
that
B ∪ Ac = (Ac ∩ B)c
is true, or give an example of two sets for which the equation is false.
|∅| = 0 (3.1)
max(|A|, |B|) ≤ |A ∪ B| ≤ |A| + |B| (3.2)
0 ≤ |A ∩ B| ≤ min(|A|, |B|) (3.3)
|A | = |U| − |A|
c
(3.4)
|A × B| = |A| · |B| (3.5)
|A|
|P(A)| = 2 (3.6)
|A|
|Pk (A)| = (3.7)
k
n
n n
2 =
n
= |Pk ({1, 2, . . . , n})| (3.8)
k
k=0 k=0
n n
k n
0= (−1) = (−1)k |Pk ({1, 2, . . . , n})| , n>0
k
k=0 k=0
(3.9)
subset obtained by removing that golden element. In this match, one subset has
even cardinality, and the other odd, so the two types of subsets are in balance.
Exercises
1. Let X and Y be sets. Suppose 25 ≤ |X| ≤ 26 and 24 ≤ |Y | ≤ 27 .
a. What can you conclude about |X ∪ Y |?
b. What can you conclude about |X ∩ Y |?
2. Let A = {1, 2, 3, 4}, B = {a, b, c, d, e}.
a. Compute |P(P2 (A) × (B × A))|.
b. Compute |P2 (P(A) × (B × A))| + |P3 (A ∩ B)|.
|A∪B|
c. Compute k=0 (−1)k |Pk (A ∪ B)|.
3. Find the 10th and 11th rows of Pascal’s triangle. Verify that the sum of all
the entries in each row is a power of 2, and that the alternating sum of each
row is 0.
Example 3.1. Let A = {a, b, c}. There are 23 = 8 subsets in P({a, b, c}) and so
the 23 bit vectors of length 3 are associated and ordered as follows:
∅: 000
{a} : 001
{b} : 010
{a, b} : 011
{c} : 100
{a, c} : 101
{b, c} : 110
{a, b, c} : 111
As you can see, the ordering on the bit vectors, thought of as binary numbers,
naturally starts with 0 recording ∅, which we will regard as the “least”, and
proceeds to 001, recording a subset with the single element a, the least in the
ordering on A. If we had ordered the queries (B(a), B(b), B(c)), then the set
following the empty set would be {c}, and that would seem backwards to most
people, though not in any sense incorrect. ♦
Example 3.2. What is 1776th subset of A in the bit vector ordering, using the
alphabetical ordering of A?
For this, we naturally want to first either recall or compute that 1776 in bi-
nary is 11011110000. Written as a binary number, 1776 can be written with
only 11 bits, but as a bit vector for subsets of A one should write 1776 as a
string of length 26 = |A|, 00000000000000011011110000, and that bit vector
encodes the subset {e, f, g, h, j, k}. The next three subsets following that one
are {a, e, f, g, h, j, k}, {b, e, f, g, h, j, k}, and {a, b, e, f, g, h, j, k}. Notice that
the answer depended on our decision, made earlier, to always order from 0. So
the first subset is {a}, not ∅. The zeroth subset is ∅. (If you try to rewrite our
description of the encoding to accommodate ordering from 1, then you will ap-
preciate the simplification.) ♦
When sets were defined, it was emphasized that membership in a set imposed
no ordering on the elements, and you might have expected that order would not
play a role in set theory. As you have now seen, it plays in fact a key role. The
fundamental assumption that the elements come with no ordering a priori leaves
one free to consider not just one hardwired order, but any convenient or useful
order; or perhaps several at once, comparing and contrasting them.
Exercises
1. List the sixteen subsets of {a, b, c, d} in bit-vector order, using the usual
ordering on the letters.
2. List the elements of P2 ({1, 2, 3, 4, 5}) in bit vector order. Give the subsets,
the bit vectors, and the decimal equivalents.
3. What is the 999th subset of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} in bit vector order,
(starting from 0 for ∅) using the usual ordering on the set of digits?
Give the next 6 subsets as well.
3.3 Inclusion/exclusion
The cardinality of a union of two finite sets A and B, follows
with equality on the left if one set is a subset of the other, and equality on the
right if the two sets A and B are disjoint, that is, that A ∩ B = ∅. In between
those two extremes, the two sets just have a non-empty intersection, and every
element in that intersection is double counted in the expression |A| + |B|. That
observation of double counting leads us to the identity
Here is the formula for the cardinality of the union of three sets,
which can be justified by using the top formula twice, along with the associative
law of set union. (Try it if you are interested.) Alternatively, we can consider
which elements are over-counted in |A| + |B| + |C|. The expression −|A ∩ B| −
|A ∩ C| − |B ∩ C| removes all the over-counts, no matter what the cause, with
the only problem being that those elements in all three sets have been removed
three times. Those same elements were included three times in |A| + |B| + |C|,
so excluding them three times leaves them totally uncounted, that is until the
last term |A ∩ B ∩ C| includes them once in the end. So the 7-term expression
counts each element exactly once overall. This justification gives the formula its
name, the inclusion/exclusion principle, called a principle and not a formula by
virtue of its use in solving practical and theoretical problems.
There is an inclusion/exclusion principle for any number of sets. In general,
for n finite sets A1 , A2 , . . . An , we have
and if you don’t see how to fill in the “. . . ”, here is the principle of inclusion/ex-
clusion written more precisely:
n
|I |+1
Ak = (−1) Ai (3.10)
k=1 ∅=I ⊆{1,2,3,...,n} i∈I
In this form, it is a bit intimidating. Let us leave it and a general explanation for
a bit. First let’s see how it is used. Student exercises mostly use the principle
with at most four sets.
Even then, you may think that the inclusion/exclusion formula is just ridicu-
lous. A simple count should tell you that, in computing |A1 ∪ A2 ∪ · · · ∪ An |
by inclusion/exclusion you would have to accurately compute the cardinalities
of 2n − 1 different sets, and do all the accounting assembling the results, and
not making any sign error. Even for n = 3 that is seven intersections, the cardi-
nalities of seven sets to compute, seven terms to keep track of. How could that
ever be simpler than simply computing the cardinality of |A1 ∪ A2 ∪ · · · ∪ An |
directly?
Example 3.3. How many six letter words on A either start with an a, like
abcabc, or end with a b, like xxbbbb, or repeat in pairs, like xyxyxy?
So, actually, we were quite happy to trade the single complicated union cardi-
nality problem for the 7 routine intersection cardinality problems. ♦
This doesn’t exactly refute the objection above. That objection noticed that
applying inclusion/exclusion would involve us in a combinatorial explosion,
that is, a situation where each incremental increase in the size of the problem
multiplies our work in solving it by an unyielding factor. That explosion is there,
and using inclusion/exclusion does not cure that explosion at all, but at least it
does help us to manage it as efficiently as can be expected.
Now, to justify the general result in Eq. (3.10) we fix an element x and,
to examine how often x is included and excluded, we consider the set B =
{X ∈ {A1 , A2 , . . . , An } | x ∈ X} of those Ai which contain x. The expression
in Eq. (3.10) counts x only in intersections containing only elements of B. The
expression counts x once with a positive sign for every non-empty subset of B
with an odd cardinality, and once with a negative for each non-empty subset of B
with an even cardinality. Adding up all those inclusions and exclusions doesn’t
give 0 as you might think from the alternating row sum of Pascal’s triangle,
since the empty set, an even subset, is excluded. So x is counted overall exactly
once.
Also, using De Morgan’s laws, you can discover an analogous formula which
rewrites the cardinality of an intersection of many sets as an alternating sum of
cardinalities of unions. The formula, which you will discover, will be true but
not very useful in solving practical problems, at least not useful enough to give
it a catchy name.
Exercises
1. How many strings of length 5 on {a, b, c, d, e} either start with a, end in a,
or have all the same letter?
2. How many strings of length 5 on {a, b, c, d, e} either start with three iden-
tical characters, end with three identical characters, or have c exactly in the
middle?
3. How many strings of length 25 on {a, b, c, d, e, . . . , z} either start with 5
identical characters, repeat every 5, (like acadcacadcacadcacadcacadc)
or are palindromic, that is, read the same forwards and backwards (like
aabbbbbbccacacaccbbbbbbaa)?
they are a member. By the multiplicative principle, if all the sets are finite, then
The use of the ∗ above is called the Kleene Star. Do not be misled by the ∞
symbol: k takes every integer value from 0 up to but not including ∞, so every
string in ∗ belongs to one of the sets Ak , and therefore must have length k. That
is, every string has finite length. Another thing to notice, at the other end of the
union, is the case when k = 0. 0 is defined to be the empty string, commonly
denoted by or λ or the empty tuple (). Strings, beyond their mathematical
applications, are a fundamental object of study in theoretical computer science,
modeling not only the typical input and output of computer programs, but the
programs themselves.
For a completely different application, while it is sufficient theoretically to
distribute two sets at a time, using A ∪ (B ∩ C) or A ∩ (B ∪ C), practically it
is much better to have a more general rule describing how to handle multiple
terms at once. Up until now, however, we have not had the notation to write the
rule down efficiently. The multiple Cartesian product is the last piece that we
need.
Theorem 3.6 (General Distributive Law for Sets). Let X1 , . . . Xn be non-empty
sets such that each element of each set is itself a set. Then the following hold;
⎡ ⎤
n
n
⎣ X⎦ = Xi , (3.11)
i=1 X∈Xi (X1 ,...,Xn )∈X1 ×···Xn i=1
⎡ ⎤
n
n
⎣ X⎦ = Xi . (3.12)
i=1 X∈Xi (X1 ,...,Xn )∈X1 ×···Xn i=1
This useful rule uses three different forms of notation for general union
and intersection. The easiest are the two on the left, where the multiple union
and intersections are indexed by either a set of consecutive natural numbers,
{1, 2, . . . , n}, or a more general set. On the right hand side the format of the
‘dummy variable’ is used to specify the required term.
Example 3.7. X1 = {A, B, C}, X2 = {D}, and X3 = {A, E}, the left side of
Eq. (3.11) gives
⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤
3
⎣ X⎦ = ⎣ X⎦ ∪ ⎣ X⎦ ∪ ⎣ X⎦
i=1 X∈Xi X∈X1 X∈X2 X∈X3
= (A ∩ B ∩ C) ∪ D ∪ (A ∩ E).
Exercises
1. Let A = {1, 2, 3}.
a. Find 5 elements in A5 × A × P(A).
Under this definition, the order on the elements of a multiple product de-
pends only on the relative order of the first differing coordinate, just as do the
words in the dictionary.
So for example, set D × {−, +} × D × {≤, =, ≥} × D, which we used to
model first grade arithmetic, contains 6000 elements. If we take the usual order-
ing on D and the order in the listing for the other two sets, the first element
in lexicographic order is 0 − 0 ≤ 0, and the last one is 9 + 9 ≥ 9, both of
which happen to be true. For any choice of the first four coordinates, there are
10 choices of the final coordinate, ordered sequentially in lexicographic order,
say from 5 + 7 = 0 to 5 + 7 = 9, all of which are false, but that is not the is-
sue. Incrementing 5 + 7 = 9, we have 5 + 7 ≥ 0, and then the sequence of 10
restarts. Incrementing any element, say 5 + 7 ≥ 9, involves moving ahead in the
rightmost coordinate for which that is possible, 5 + 8__, and resetting all the
coordinates further to the right to the least element in the relevant set, 5 + 8 ≤ 0.
We see that the lexicographic list is organized in the same way that the list of
natural numbers in base 10 is organized, except that instead of the columns being
sequences of 10 identical characters in the 10’s place, and 102 identical charac-
ters in the 102 ’s place, etc., there will be 10 identical characters in the {≤, =, ≥}
place, 3 · 10 identical characters in the middle D place, 10 · 3 · 10 identical char-
acters in the middle {−, +} place, etc. And it is no surprise that the backwards
method of computing a number to a different base adapts easily to this situation.
Lexicographic order on k
Lexicographic order on a multiple Cartesian product has a nice interpretation
in the case where all the sets in the product are the same, for example when
considering strings of length k and an alphabet . To find the mth string in k ,
the divisions with remainder are all done with respect to the same number, ||.
In fact, we can observe that, in the special case of ordering strings of length
k from an alphabet , the problem is essentially the same as counting k-digit
numbers in base ||, (and one can even regard the ordered elements of as the
digits!)
Theorem 3.9 (Lexicographically Ordering Strings). Let = {a0 , a1 , . . . aN −1 }
be a set of cardinality N with ordering a0 < a1 < · · · < aN −1 on its elements.
Let m = dN −1 N k−1 + dN −2 N k−2 + · · · + d1 N 1 + d0 N 0 , with each dj sat-
isfying 0 ≤ di < N , be the representation of the number m as a k digit num-
ber in base N . Then the mth string in k , regarding a0 a0 · a0 as the 0th, is
(adN−1 , adN−2 , . . . , ad0 ), or more compactly adN−1 adN−2 · · · ad1 ad0 .
Example
Let = {a, b, c, d, e, f, g, h, i, j } be an alphabet of 10 letters, and the usual or-
dering. The 5280th string of 4 in lexicographic order is f cia, because 5280 is
already represented in base 10 and the entries of f cia are the 5th, 2nd, 8th,
and 0th characters of . The 5280th string of 8 in lexicographic order is
aaaaf cia.
Exercises
1. Let B = {a, b}.
How many strings are between abbbb and baaaa in the lexicographic order
on all strings of length 5 on B?
2. Which number is the string γ αγ αββ in lexicographical order on the
strings of length 10 on {α, β, γ , δ, }?
3. Let A = {1, 2, 3} and B = {a, b}. Taking the usual ordering on the elements
of both sets, what is the 88th element of A × B × A × B × A × B × A in
lexicographic order?
metic problems, what if we want to restrict to those elements for which the
mathematical expression is true?
Permutations
The set of permutations of the six characters in = {a, b, c, d, e, f } can be
regarded as a subset of 6 , specifically the subset
You may take a general element of P (), say df beca, and ask what follows it
in P () in lexicographic order. You cannot increment just the final a, because
it is forced by the first part of the string. You cannot increment the c next to it
because, fixing the characters to the left, it is already the highest value among
a and c. You cannot increment the e next door for the same reason. It is the b
which may be incremented, holding the initial df fixed, to c. So the next permu-
tation after df beca in lexicographic order is df cade, taking the leftover letters
{a, d, e} in order. (After that come df caed, df cdae, df cdea, . . . ). Observing
the list above we see the pattern that, reading from right to left, the rightmost
coordinate has no freedom at all, its neighbor to the left has two alternatives
it must cycle through, and its neighbor to the left has three alternatives it must
cycle through in pairs, so its neighbor to the left must cycle through its four
possibilities in groups of 2 · 3 = 3!, etc.
How many permutations are ahead of a general permutation σ1 σ2 σ3 σ4 σ5 σ6 ?
We ask first how many permutations were on the list before σ1 appeared in
the first position? Each element of {σ2 , σ3 , σ4 , σ5 , σ6 } which is smaller than σ1
occupied the first position ahead of σ1 , and for each one, there were (6 − 1)! per-
mutations. So if we set r1 to be the number of elements in {σ2 , σ3 , σ4 , σ5 , σ6 } less
5 · 9! + 7 · 8! + 2 · 7! + 3 · 6! + 5 · 5! + 3 · 4! + 1 · 3! + 0 · 2! + 1 · 1! + 0 · 0!
Exercises
1. List all 24 permutations of {a, b, c, d} in lexicographical order.
2. How many numbers with 10 distinct decimal digits are less than 8,214,
596,073? (The smallest such number is 0,123,456,789.)
3. Starting with 8,214,596,073, what are the next 12 numbers with distinct dig-
its in order?
m = rN −1 · (N − 1)! + rN −2 · (N − 2)! + · · · + r2 · 2! + r1 · 1! + r0 · 0!
in ten divisions. This shows that the only remainders which are non-zero are
r4 = 4 and r5 = r6 = 2, and we may check that, indeed, 1776 = 2 · 6! + 2 · 5! +
4 · 4!.
To complete the process, we have to find, given r0 , r1 , . . . , the desired per-
mutation σN −1 σN −2 · · · σ1 σ0 . So far we have been working backwards, from
right to left, but this will no longer help us. The fact that r0 = 0 only tells us that
σ0 is forced by the coordinates to the left. We need to find those first, and so we
better work now from left to right.
For the N − 1th position, take the rN −1 th element from the N elements in
. For the N − 2th position, take the rN −2 th element from the N − 1 elements
remaining, and at each stage both fill the coordinate position, and remove that
value from the next and all subsequent choices. ♦
Example 3.14. Continuing with our example, we have r9 = r8 = r7 = 0, so we
start the permutation with abc, very much at the front of our dictionary, which
is to be expected since it has 10! = 3, 628, 800 entries, and we are only looking
for the 1776th. The entries remaining are {d, e, f, g, h, i, j }, and r6 = 2, and the
2nd from the left, ordering from the 0th, is f , so abcf . Next we want the 2nd
from {d, e, g, h, i, j }, which is g, and form abcf g. Next we want the 4th from
{d, e, h, i, j } which is j , and so form abcf gj . All the remaining r’s are 0, we
put in the remaining {d, e, h, i} in order, and form at last abcf gj dehi. ♦
The general description we are leaving as an exercise. A hint is, in the pre-
vious general description, it was done by introducing the sequences of numbers
ri and mi , here one of the sequences of objects to be introduced are strings, and
the other are sets. To get you started, here is another example whose answer can
be checked from the list begun in Section 3.6.
Example 3.15. What is the 32nd permutation of {a, b, c, d, e, f }? We begin by
finding the sequence of remainders:
32 = 1 * 32 + 0 5 = 4 * 1 + 1
32 = 2 * 16 + 0 1 = 5 * 0 + 1
15 = 3 * 5 + 1 0 = 6 * 0 + 0
Exercises
1. Compute with the backwards method the 0th, 10th, and 20th permutations
of {α, β, γ , δ} in lexicographical order.
Verify your results by listing them.
2. What is the 720th permutation of {a, b, c, d, e, f, g} in lexicographical order,
counting from 0?
We will return to the case study for more analysis, but most readers I think
will have a solution in 7 before then.
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 x 0
0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 x x 0
1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 x x x x 1
1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1x x x x x x x x1
If now we noticed that there was a fifth switch above these, say, 01011, we
could extend by flipping that now, and reverse the flips of the other four:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0x1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1x0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0x1 1 1 1 1 1 1 1
0 0 0 0x1 1 1 1 1 1 1 1x0 0 0 0 0 0 0 0x1 1 1 1 1 1 1 1x0 0 0 0
1 1x0 0 0 0x1 1 1 1x0 0 0 0x1 1 1 1x0 0 0 0x1 1 1 1x0 0 0 0x1 1
1x0 0x1 1x0 0x1 1x0 0x1 1x0 0x1 1x0 0x1 1x0 0x1 1x0 0x1 1x0 0x1
If we follow this procedure starting with 00000, the resulting sequence of bit
vectors is called the Gray code, and for five bits it is
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0x1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0x1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1x0 0 0 0 0 0 0 0
0 0 0 0x1 1 1 1 1 1 1 1x0 0 0 0 0 0 0 0x1 1 1 1 1 1 1 1x0 0 0 0
0 0x1 1 1 1x0 0 0 0x1 1 1 1x0 0 0 0x1 1 1 1x0 0 0 0x1 1 1 1x0 0
0x1 1x0 0x1 1x0 0x1 1x0 0x1 1x0 0x1 1x0 0x1 1x0 0x1 1x0 0x1 1x0
So, for example, if you want the 13th element of the Gray code, you first
express 13 in binary 13 = 11012 , then, moving from right to left, record all the
places where 0 switches to 1 and vice versa in 01101, so 01011.
Decoding from a Gray string back to a binary string will have to wait.
orders to the proper customer without asking who ordered what. Our forget-
ful waitress is very busy and has other things on her mind. Everybody ordered
something different and she has forgotten completely who ordered what, but
still she doesn’t want to ask, so she distributes the orders randomly, hoping
that she will guess correctly. Her probability of success is an easy exercise in
the multiplicative principle. The Forgetful Waitress Problem, however, asks the
probability that nobody gets the correct order.
The number of ways to distribute the orders is 12!, the number of permuta-
tions, so we need only compute the number permutations of, say, abcdef ghiklm
such that no letter is in its correct alphabetical position.
A permutation of this type is called a derangement. So we are asking what
fraction of permutations of 12 elements are derangements.
That problem also looks like an easy problem for the multiplicative principle,
but a naive left to right approach won’t work. There are 11 choices for the first
position, true. But then the number of choices for second position depends. If
you picked b for first position, a legal choice, then any of the remaining eleven
letters can be placed in second position. If, on the other hand, you picked c, then
there would be only 10 choices for second position, since both b and c would be
forbidden. You can split into two cases, but then it gets even worse further on.
A clever trick is to, first of all, count the complement – the number of per-
mutations for which at least someone gets the correct order, and secondly, to
count that with inclusion/exclusion. This is a bit more difficult than our exercise
problems, but follows the same pattern. First we have to define our sets. Let Pi
be the number of permutations of abcdef ghiklm such that the ith letter is fixed.
So P0 if the set of those permutations which start with a and P11 is the set of
those which end in m. We want to count |P0 ∪ P1 ∪ · · · P10 ∪ P11 |.
With 12 sets, inclusion/exclusion will involve us with 212 − 1 = 4, 095 cardi-
nality of intersection problems, but don’t panic! First |Pi | = (12 − 1)!, since one
letter is fixed and the rest are permuted. There are 12 such sets, so the first posi-
tive terms in the inclusion/exclusion formula give us, altogether, 12 · (12 − 1)!.
For the pairwise intersection |Pi ∩ Pj | = (12 − 2)! since 2 elements are fixed,
and the rest are permuted. There are 12 2 terms like this, and they are all sub-
12
tracted so − 2 (12 − 2)! altogether are excluded.
case for an intersection of k, we have (12 − k)!
Skipping ahead to the general
permutations, and there are 12 k such terms, and they are subtracted if k is even,
12
k (12 − k)!. You were right not to panic, by
and added if k is odd, i.e. (−1) k−1
gathering all thelike terms together, we only have 11 terms, and not 4,095. For
k = 6, since 12 6 = 924 we were able to handle almost one thousand of those
4095 sets all at once!
clean up the first one, which was 12 · (12 − 1)! and rewrite it as
Let’s
(−1)0 12 1 (12 − 1)!, so that it fits the pattern. Now we add:
12
k−1 12
(−1) (12 − k)!
k
k=1
Before you program that in, recall that these are the permutations we do not
want, the ones where somebody does get the
correct order. We have to subtract
these from 12!, which we will write as 120 (12 − 0)! to make it fit the pattern.
With that, the number of derangements is
12
12
(−1)k (12 − k)!
k
k=0
12 (12 − k)! (12 − k)!
12 12 12
12! 1
(−1)k = (−1)k = (−1)k
k 12! k!(12 − k)! 12! k!
k=0 k=0 k=0
so the number we will get for the finite sum is very close to e−1 = 1e , a little
more than 1/3 of the time. Moreover, the more people at the table, the closer
the probability that nobody receives what they ordered gets to 1/e. Except that
it doesn’t, unless you have a science fiction restaurant where billions of people
can order billions of different things.
But mathematically, we can still say that the fraction of permutations which
are derangements approaches 1/e as the number of objects permuted approaches
infinity.
Formal logic
4.1 Statements and truth value
The study of logic begins well into the text because, at least in some sense,
we are all familiar with its informal application. Logic is the use of careful
reasoning applied to statements. Considering statements in terms of grammar,
you might conclude that statements are very common, with any sentence being
classified as either a question or a statement. But most non-questions are not
statements in the sense of logic. For logic, a statement is either true or false.
Sherlock Holmes applies logic to solve crimes. He reasons that Sir Albert is
the only man on the island who is left-handed, has knowledge of firearms, and
knew where the rubies were hidden, and therefore, Sir Albert is the murderer.
But Sherlock Holmes has a huge advantage over the police; not because he
is well-educated and incredibly smart; but because he is a fictional character.
Holmes inhabits a world of rigid facts created by an author. In the real world,
there are right-handed people who sometimes use their left hand, there are war
veterans who can’t or won’t use firearms, and there are men who look right at a
heap of rubies hidden in a drawer but just don’t notice them.
In the real world, treating facts as “facts” is a dangerous game which can
let you build a structure as fragile as a house of cards. In detective fiction, the
pleasure is often in the description of a long sequence of logical card houses
built by minor characters and then blown down by new “clues”, until the final
structure is constructed by the protagonist. And that final one is only not blown
away because the book is over.
The simplest assertion in natural language can have hidden problems which
make it problematical. “Puerto Rico is a state” – True or False? What are we
to say? It is not one of the fifty states of the United States, but it is a state
in the sense of being a governmental unit. Right away we have two different
reasonable interpretations. The problem is not that it is questionable whether
the sentence is true or not. The problem is that it is not clear what is meant.
Without context, it is not a logical statement at all.
It is much easier to find statements on which to apply logic in mathematics,
games, or the law – areas where we humans make the rules and control the
language which is used to express them.
• In chess, the bishop moves diagonally. (TRUE)
• π
√ > 3. (TRUE)
• 2 is rational. (FALSE)
Exercises
1. For each of the following, argue whether or not it qualifies as a statement in
the sense of logic.
a) Gas burns. b) Canada is a peaceful nation.
c) You can get anything you want at Alice’s restaurant.
2. For each of the following, argue whether or not it qualifies as a statement in
the sense of logic.
a) The derivative of x 5 is 5x 4 . b) Every rational number is a real number.
100
c) π (2 ) is prime.
3. Suppose that p, q, and r are statements. The expression “p and q or r” is
ambiguous. Explain why.
It may help if you let p stand for “Eddie has a penny”, q stand for “Eddie
has a quarter”, and r stand for “Eddie has a ruby”.
In particular, just as with ∩ and ∪, each operator distributes over the other,
making them more on an equal footing than + and ×. In terms of order of
operations, the negation ¬ gets the highest preference, just as −, so ¬p ∨ r is
read as (¬p) ∨ r, not ¬(p ∨ r). For the binary operators ∧ and ∨, however, we
First we should notice that the upper one is much easier to parse. Each term,
or clause, is connected by an OR, so each clause may be examined separately.
Since p = r = 1 and q = 0 makes the first clause TRUE, that assignment makes
the whole expression TRUE.
For the second one, all three clauses must be TRUE so none can be ignored.
Each clause is an OR statement, so can be satisfied in different ways. But we do
not have to resort to checking all possibilities. Instead we look for commonal-
ities and notice that p is an alternative for the first two terms, so taking p = 1
makes both of those terms TRUE, and leaves freedom in assigning q for the
third term. Assigning p = 1 and q = 0 works independently of the truth value
of r. ♦
Exercises
1. Suppose p and q are TRUE and r is false. Determine the truth value of each
of the following:
a) (p ∨ ¬q) ∧ (¬q ∨ r) b) (p ∧ ¬q) ∨ (¬q ∧ r)
2. Suppose p = 0, q = 0, r = 1, and s = 0. Find the Boolean value of each of
the following:
a) (p ∧ ¬s) ∨ (¬q ∧ r) b) (p ∨ ¬s) ∧ (¬q ∨ r)
3. Find Boolean values of each of p, q, r and s so that
4.3 Implications
The logical operations that form the building blocks of Boolean algebra are ∨,
∧, and ¬. There are several other minor operations which we will not concern
ourselves with. But there is one other operation which we must learn: the im-
plication. It is the fundamental underpinning of logic as it is used in arguments
and reasoning, and it must be carefully studied to avoid common mistakes. Its
definition in logic often comes as a surprise.
Definition 4.3. The implication, symbolically ⇒, is a binary logical operation.
The statement p ⇒ q asserts that q is true or p is false:
(p ⇒ q) = (q ∨ ¬p). ♠
In text, the implication p ⇒ q can be variously expressed as, “p implies q”, “if
p then q”, or “q is a consequence of p”.
Beware that implications, are often not used the same way in logic as in
natural language, so there are many pitfalls in understanding their meaning. In
particular
• No Temporality: Unless time is part of the statement, the conclusion is not
thought of becoming true after the antecedent is true, as is meant by saying
“If you will just read this book then you will be rich.”
• No Causality: In logic, the implication does not require that the truth of the
antecedent causes the truth of the consequence. The connection is in truth
value alone. In natural language, if you say “If you don’t pay your taxes
then you go to jail”, the jail term is understood to be a consequence of tax
avoidance.
Temporality is usually not a confusion in mathematical statements, but
causality definitely is a common source of error.
(π > 3) ⇒ (3 is prime)
is a perfectly valid implication, since the consequence is true, but one is tempted
to reject it as false because there is no obvious causal link.
This is even more pronounced in the equally valid
which logic requires us to accept before we even read the consequence, since
the hypothesis is false; and the frankly disturbing
(27 is prime) ⇒ (1 + 1 = 7)
If Empire apples are deadly poison, then you should not eat them.
You would start your argument by asking the reader to grant you the truth of
the hypothesis for the sake of the argument. “Let Empire apples be deadly poi-
son”, you say, to the consternation of the apple industry. Once the hypothesis is
granted, the argument to the conclusion is very easy, since you should not eat
anything which is deadly poison, whatever it is. Now that the implication is es-
tablished, our knowledge of the nature of an Empire apple returns to its former
state, both with regard to it being poison, and the injunction not to eat it. Only
the truth of the implication remains. ♦
and those who use mathematics, are careful to preserve this ancient and rigid
formulation of the implication despite natural language’s drift in giving it other
connotations. The implication in its pure form is too practically useful to alter.
Exercises
1. Which of the following implications do you regard as true?
a) If it snowed in Boston last year then there will be a full moon there some-
time next August.
b) If you eat cauliflower every day then smoking cigarettes is a bad idea.
c) If a leprechaun appears on St. Patrick’s Day and gives you a pot of gold
then U.S. federal law requires you to give all that gold to your parents.
2. Establish the following implications.
a) If 18 is odd, then 20 is odd.
b) If π is irrational, then 20 is even.
3. Establish the following implications:
a) (p ∨ ¬p) ⇒ (q ∨ ¬q)
b) (p ∧ q) ⇒ (q ∨ r)
[p = q] = [p ⇔ q] = [(p ⇒ q) ∧ (q ⇒ p)]
This identity justifies a technique that, like the double inclusion we studied ear-
lier, is widely used, fundamental, and gives good practice in logical thinking and
using logical notation. In this text it is called the double implication method of
showing logical equivalence.
Definition 4.5. To establish the equivalence of two logical expressions p and
q by the double implication method, show separately that p ⇒ q and q ⇒ p.
♠
As a first application of the double implication method, we will show one of
the distributive laws,
Commentary: The pattern is in the same form as the double inclusion proof,
but the language and notation are different. Specifically, the requirement at each
stage is different. Notice that to assert p, is the same as saying p is true, and,
though not appearing in the argument above, to assert ¬p, is to say p is false.
You could rewrite the whole argument without the words true and false, and
substitute their bit equivalents 1 and 0.
Like with double inclusion, you should learn to write proofs of this form, and
the best practice is using basic logical identities. But keep in mind, we are not
concerned with reproving well-known identities. It is implication, and double
implication that we are practicing.
Eq. (4.2) can quickly be shown from Definition 4.3 and Boolean algebra. In-
stead, it is instructive to prove [p ⇒ q] ⇐⇒ [¬q ⇒ ¬p] as another example of
the double implication method.
Commentary. The argument is tricky because, inside the proof of one im-
plication you have to prove a different implication, and that in different places
in the argument you have to correctly establish and use implications. Notice
what is known and what hypotheticals have been granted at ♥. The implication
¬q ⇒ ¬p has been shown, so the assumption ¬q and the consequence ¬p are
no longer to be granted in the argument, as well as anything concluded from
them except ¬q ⇒ ¬p. The overall implication [p ⇒ q] ⇒ [¬q ⇒ ¬p] is still
being argued, so at ♥ the hypothesis p ⇒ q is still granted to be true. Fortu-
nately, we have just what we need to establish the desired implication, and once
that is done, at ♦, the first half of the argument is over, and the granted hypothet-
ical p ⇒ q and the concluded ¬q ⇒ ¬p are released. All that remains proven
is [p ⇒ q] ⇒ [¬q ⇒ ¬p].
Exercises
1. Prove by double inclusion the associative law for ∧, the AND operator:
2. Prove one of De Morgan’s Laws for formal logic, or one of the distributive
laws, see Eq. (4.1), by the double implication method.
3. Consider the implication a ∧ (b ∨ c) ⇒ d.
a) Which of a, b, c, and d can you immediately assume to be true?
b) What is the consequence of the implication?
c) What is the antecedent of the contrapositive?
d) What is the hypothesis of the converse?
e) What is the conclusion of the inverse?
Example 4.6. Is the negation of the implication p ⇒ q its inverse, its converse,
or its contrapositive?
Actually, none of these, since ¬(p ⇒ q) = ¬(q ∨ ¬p) = ¬q ∧ ¬(¬p) = p ∧
¬q, so the negation of an implication is not an OR statement at all, and is a
stronger AND statement. ♦
Commentary. In the second part, count how many implications and hypo-
theticals we are juggling at ♥. This is certainly the most complicated double
implication proof one would ever want to read. But remember, we are not study-
ing double implication to play with identities, but to learn the reasoning method
to use later on other discrete problems. If you can get through this example,
you can really say that you have mastered that method, and understand how
implications work.
Here is the same expression approached via Boolean algebra, which is de-
signed exactly to fit this type of problem.
You should definitely justify each step in the “calculation” above from the list
in Eq. (4.1), and note the name of the property used.
Exercises
1. Express p ⇒ (q ⇒ (r ⇒ s)) only in terms of ∨, ∧, and ¬.
2. Express p = (q ⇒ r) only in terms of ∨, ∧, and ¬.
3. Express (p ⇒ q) = (q ⇒ p) only in terms of ∨, ∧, and ¬.
(¬p ∧ q ∧ r ∧ s ∧ t) ∨ (p ∧ ¬q ∧ r ∧ s ∧ t) ∨ (p ∧ q ∧ ¬r ∧ s ∧ t)∨
(p ∧ q ∧ r ∧ ¬s ∧ t) ∨ (p ∧ q ∧ r ∧ s ∧ ¬t)
Exercises
1. For p, q, r and s, express “they can’t all be true” in terms of ∨, ∧, and ¬.
2. For p, q, r and s, express “all are true or none are true” in terms of ∨, ∧,
and ¬.
3. For p, q, r and s, express “any three imply the fourth” in terms of ∨, ∧,
and ¬.
(p ∨ ¬q ∨ s) ∧ (q ∨ ¬t ∨ z) ∧ (r ∨ s ∨ t) ∧ (¬p ∨ ¬r ∨ t)
This follows either from first expressing the negation in disjunctive nor-
mal form, and then negating that expression in disjunctive normal form using
De Morgan’s laws, thereby switching all the ANDs to ORs, all the ORs to
ANDs, and reversing which variables are negated in each clause. A second way
to see this, is start with an expression of the desired Boolean function in disjunc-
tive normal form, and use the distributive law to “multiply it out”, just like you
would multiply out (x + y + z)(x − y + w)(−x + w + t). You can do that in
reverse to convert a conjunctive normal form into an, easy to solve, disjunctive
normal form, but that doesn’t solve the NP-completeness problem since, in gen-
eral, by the multiplicative principle, multiplying out the algebraic expression is
still a lot of work.
Exercises
1. For p, q, r, and s, express “they can’t all be true” in boolean notation.
a. Rewrite in DNF.
b. Rewrite in CNF.
2. For p, q, r, and s, express “all are true or none are true” in boolean notation.
a. Rewrite in DNF.
b. Rewrite in CNF.
3. For p, q, r, and s, express “any three imply the fourth” in boolean notation.
a. Rewrite in DNF.
b. Rewrite in CNF.
Daniel Kilraine was killed on a lonely road, two miles from Pontiac, at
3:30am on March 17. Otto, Curly, Slim, Mickey, and The Kid were arrested
a week later in Detroit and questioned.
Each of the five made four statements, three of which were true, and one of
which was false.
One of these men killed Kilraine. The statements were:
Otto: “I was in Chicago when Kilraine was murdered. I never killed anyone.
The Kid is the guilty man. Mickey and I are pals.”
Curly: “I did not kill Kilraine. I never owned a revolver in my life. The Kid
knows me. I was in Detroit the night of March 17.”
Slim: “Curly lied when he said he never owned a revolver. The murder was
committed on St. Patrick’s day. Otto was in Chicago at this time. One of us is
guilty.”
Mickey: “I did not kill Kilraine. The Kid has never been in Pontiac. I never
saw Otto before. Curly was in Detroit with me on the night of March 17.”
The Kid: “I did not kill Kilraine. I have never been in Pontiac. I never saw
Curly before. Otto lied when he said I am guilty.”
The employees of a small loan company are Mr. Black, Mr. White, Mrs. Cof-
fee, Miss Ambrose, Mr. Kelly, and Miss Earnshaw. The positions they occupy
are manager, assistant manager, cashier, stenographer, teller, and clerk, though
not necessarily in that order.
The assistant manager is the manager’s grandson, the cashier is the stenog-
rapher’s son-in-law, Mr. Black is a bachelor, Mr. White is twenty-two years old,
Miss Ambrose is the teller’s stepsister, and Mr. Kelly is the manager’s neighbor.
Who holds each position?
Each spy will not be given all these fancy gadgets, just a subset. But the spy
must have enough gear to be survivable. To be survivable he must have among
his gadgets a weapon, something valuable, a method of communication, and
transport. {a, b, c, d, e, f, g, h} are Boolean variables which are true if the spy
possesses the corresponding gadget, and false otherwise.
Here is a proposed survivability function:
(b ∨ d ∨ g ∨ h) ∧ (b ∨ c ∨ d ∨ e ∨ g) ∧ (a ∨ e) ∧ (a ∨ c ∨ h)
Each of the four OR clauses has a meaning in the game. Can you identify which
is which?
Each represents one of the four conditions of survivability, possession of
weapon, valuables communicator, and transport respectively. So the brick of
gold is a valuable which the spy, at necessity, could use as a weapon, but not for
transport or for communication. Of course, the faithful sidekick doesn’t help the
spy survive at all, and doesn’t occur in the survivability function.
The survivability function, which is naturally and easily written in CNF, il-
lustrates that CNF is not nearly so useless as it seemed when considering the
Boolean function only from the point of view of finding Boolean values which
evaluate it to TRUE.
The negation, and a little Boolean algebra, quickly gets us an expression for
the non-survivable function in DN F :
(¬b ∧¬d ∧¬g ∧¬h)∨(¬b ∧¬c ∧¬d ∧¬e ∧¬g)∨(¬a ∧¬e)∨(¬a ∧¬c ∧¬h)
1 1 1 1
2 4 5 5
3 9 14 2·7
4 16 30 2·3·5
5 25 55 5 · 11
6 36 91 7 ·13
7 49 140 22 · 5 · 7
8 64 204 22 · 3 · 17
9 81 285 3 · 5 · 19
10 100 385 5 · 7 · 11
After a while, in desperation, they factor each of the totals into their prime fac-
tors, placing the results in column 4, and are quite disappointed with the results.
But there is a sort of pattern, intermittent but persistent, like a glimpsed shadow
in the fog which might be a prize ship to be attacked. The pattern is underlined
in column 4: skip the first entry, 5, 7, skip, 11, 13, skip, 17, 19, skip.
We would be happy to fill in the pattern even with non-primes to get 3, 5, 7,
9, 11, 13, 15, 17, 19, 21, but each of those skipped entries is missing a factor
of 3. So, to make the pattern work, and at a loss for anything better to do, they
add a factor of three to all entries, dividing it right back out again, so that the
number is unaltered. The result is column 4 in Table 4.2, with the numbers in
the desired pattern in parentheses.
Looking for a pattern in the numbers not in parentheses is still quite disap-
pointing. But something is there, again not a regularly ascending or descending
sequence, but one hobbling along in twos – from bottom to top you see 5, 5, 4,
4, 3, 3, 2, 2, skip 1. The pirates add the missing factor of 1 at no cost and isolate
those numbers in square brackets. That takes them to column 5, with the leftover
numbers in angular brackets. In the angular brackets we have another hobbling
pattern, bottom to top 11, 9, 9, 7, 7, 5, 5, 3, 3, 1, but this is actually progress.
Why not write down separate formulas for the even and odd cases? For the even
height stacks they quickly get (n/2)(n + 1)(2n + 1)(1/3). For the odd height
stacks get n((n + 1)/2)(2n + 1)(1/3).
Break out the rum – algebraically it is the same formula in both cases!
The next thing they do is just what you or I would do. They add 112 to 385
to get 385 + 121 = 506 for a stack of height 11. Then they compute
11(11 + 1)(2 · 11 + 1)
= 506
6
and find – hurrah! – that their formula works!
Hurrah! – but now they are completely stuck. They can check their formula
against new cases, 12, 13, 14, . . . , but that does not provide a convincing logical
argument to prove the general formula. Their “successful” method started with
the pattern of primes – for which they had no formula in 1600, and there is no
formula even now. So those pirates, even with the help of logic, had no way
scaling their method to show that their formula was true in the general case.
But that mathematician had a way. That will have to wait until the next chap-
ter.
Induction
5.1 Predicate logic
Formal logic is based on statements, equivalently propositions, equivalently
Boolean variables. Predicate logic is based on predicates. You may know the
word predicate from grammar, the study of languages in which sentences are
taken apart and their structure analyzed. A sentence may be decomposed gram-
matically into a subject, a noun phrase; followed by a predicate, consisting of
most everything else – the verb, the objects, the prepositional phrases, and all
the other parts of speech which come together in the sentence to express what
you want to say about the subject.
“Benedict Arnold is a filthy traitor and ought to be tarred and feathered.”
This is a simple sentence with the subject in bold and the predicate in italics.
Logically the sentence might stand for a proposition which could be true or
false depending on your opinion of Benedict Arnold.
In predicate logic, the idea is to hold the predicate fixed, and to vary the
subject.
“John Adams is a filthy traitor and ought to be tarred and feathered.”
“Wyatt Earp is a filthy traitor and ought to be tarred and feathered.”
“John Philip Sousa is a filthy traitor and ought to be tarred and feathered.”
This idea of predicate may be conveyed by using a generic unspecified subject,
a pronoun indicating the set of people under consideration: “The accused is
a filthy traitor and ought to be tarred and feathered.” The particular instances
above are said to have been instantiated, or quantified from this general version.
Here is a more mathematical example, “The number is a prime number”;
which may be quantified to be true, “Twenty-three is a prime number”, or false
“Avogadro’s number is a prime number”.
This linguistic game is how predicate logic got its name, but mathematically
it is more efficient to regard the predicate as a function which assigns a truth
value, that is, a Boolean value to each element of the set of subjects.
Definition 5.1. A Boolean function P on a set S is an assignment P (s) ∈ B for
each element s ∈ S. ♠
Note, P (s) is often written as Ps .
The Boolean functions we had in formal logic fit this scheme as a special
case. For example for r ∨ (p ⇒ q) the elements of S are triples of Boolean
values, and r ∨ (p ⇒ q) is TRUE if quantified with r = p = q = 1, and FALSE
Example 5.2. With predicate logic, you may see even greater utility in the def-
inition of the implication in logic: the consequence is true or the antecedent is
false; since there are various instantiations to compare.
“The customer over six feet tall may not rent a rowboat.”
The rule is TRUE for Hans who is 6’8” and may not rent a rowboat (antecedent
and consequence both true). It is true for Ignaz, who is 5’2” and may rent a
rowboat (antecedent false and consequence false). It is valid also for Jörg, who
is 5’1” but may not rent a rowboat because he weighs 288 lbs. (antecedent false
and consequence true). The company violates the height rule if it rents a rowboat
to Hans. It does not violate the height rule if it rents rowboats to Ignaz and Jörg,
or refuses to do so. The point of this example is not to focus just on Hans, but on
the totality of customers. The implication should be valid for all, but is written
solely to prevent tall people from renting rowboats. ♦
Exercises
1. Underline the predicate of each of the following, and instantiate each subject
twice, once resulting in TRUE, once resulting in FALSE.
a. The man was born after 1888.
b. The state is north of North Carolina.
2. Underline the predicate of each of the following, and instantiate each sub-
ject twice, once resulting in TRUE, once resulting in FALSE. Context: Our
universe are the natural numbers.
a. The number is the sum of three distinct cubes.
b. The number is the product of three primes.
3. The point lies between one and two units from either (1, 1) or (−1, −1).
Draw a sketch of the points in the plane in which the points making this
Boolean function true are colored red, and those making it false are colored
blue.
One difference between the algebra of real functions and general Boolean
algebra is that predicate logic has two very important special forms of evalua-
tion.
Definition 5.3. The universal quantification of the Boolean function P defined
on the set S is the statement that P (s) is true for all elements s ∈ S. ♠
There is a special logical symbol ∀, read as “for all”, defined by
[∀s ∈ S; P (s)] = P (s)
s∈S
√
So ∀n ∈ N; n2 > 20 is simply false, while ∀n ∈ Q; n2 = 2 is true, since 2
is irrational. How about ∀n ∈ N; n3 − n is divisible by 3? Can you determine its
truth value?
In contrast to universal quantification is existential quantification, which
sounds very exotic and intimidating, but is just the OR version of the previous
concept:
numbers, because −1 ∈ / Z.
[∃s ∈ S; Ps ] ⇐⇒ [∃ ∈ S; P ]
Exercises
1. Decide whether or not the following is true or false, and prove it.
∃n ∈ N; n2 + 5 = 6n
2. Decide whether or not the following is true or false. If it is true, then prove
it.
∀n ∈ N; n2 is even or n3 is odd
3. State whether the expression is a statement or merely a predicate. If a state-
ment, state whether or not it is true.
a. ∀n ∈ N; ∃m ∈ N; n3 ≥ m2
b. ∃m ∈ N; ∀n ∈ N; n3 ≥ m2
c. ∃n ∈ N; ∀m ∈ N; n3 ≥ m2
d. ∀m ∈ N; ∃n ∈ N; n3 ≥ m2
e. ∀n ∈ N; ∀m ∈ N; n3 ≥ m2
f. ∃n ∈ N; ∃m ∈ N; n3 ≥ m2
Proof of Eq. (5.1). This is to show why induction is a valid method. We use the
double implication method. If the left hand side is true then all instances Pi are
true, in which case P0 is true and for any given n the implication Pn ⇒ Pn+1 is
true because the consequence is true. (That was fast.)
Now suppose the right hand side is true. So P0 is true and every instance
of the implication Pn ⇒ Pn+1 is true as well. Now we want to use those im-
plications to show that all the individual instances of Pi are also true. Since P0
is true, we know that at least some of the Pi ’s are true. If any are false, there
must be a smallest number k, with Pk false. Since k is the smallest, and k = 0,
Pk−1 is true. But we have the implication Pk−1 ⇒ P(k−1)+1 , which means that
Pk cannot be false after all, a contradiction. Thus [∀n ∈ N; Pn ] is true.
If you don’t like that formal approach, at least you notice that it is the second
half of the double implication method, which is the difficult part. A more direct
argument is: P0 is true, and because P0 ⇒ P1 , we conclude P1 is true; but now,
Exercises
1. Suppose you wanted to prove by induction that 3 · n! > n2 for all n ≥ 0.
What is the base case?
What implication would you have to show for the induction step?
What induction hypothesis would you be allowed to assume to prove the
induction step?
2. Suppose you wanted to prove by induction that, for every natural number,
(2n + 3)! ≥ 102(n+2) .
What is the base case?
What implication would you have to show for the induction step?
What induction hypothesis would you be allowed to assume to prove the
induction step?
3. Suppose Pn is a predicate defined on n ∈ N. Suppose that ∀n ∈ N; [Pn ⇒
Pn+1 ], and that P21 ∧ ¬P12 is true. For each of the following, state whether
n
n(n + 1)(2n + 1)
k2 =
6
k=0
If you read that, we left off with a formula which we strongly suspected was
true for all n, but for which we had no argument whatever, which applied in the
general case.
We will give an inductive proof and then a commentary.
Proof. Base case: For n = 0 (♥0 ) the left hand side of the formula is 02 and the
right hand side is 0(0 + 1)(2 · 0 + 1)/6 = 0. So they
are equal.
Induction step: Let n be given and suppose nk=0 k 2 = n(n+1)(2n+1) (♥1 ).
n+1 2 (n+1)(n+2)(2n+3) 6
We want to show that k=0 k = 6 (♥2 ). Isolating the last term
of the sum, we have
n
n+1 n(n + 1)(2n + 1)
k =
2
k + (n + 1)2 =
2
+ (n + 1)2
6
k=0 k=0
Commentary: This proof is much harder to read and follow since it leaves
much of the inductive structure to the reader to fill in. It is also much harder
to write since all the aspects which have been left off must be considered and
checked by the writer. The only hint that the proof is an inductive argument is
in the sentence preceding the proof. The reader is presumed to be able in fill all
in the missing details, and most will.
The most annoying feature of this argument is that the proof refers to a vari-
able n which is not mentioned in the statement of the problem at all! It is often
the case, when composing an inductive argument, that the statement to be proved
must be recast in terms of a variable on which induction can be done. In this case
it would be pn : For all n ∈ N, n3 − n is divisible by 6.
The author leaves all the algebra to the reader, ♥2 , which is ok for some
readers, and at least makes sure that the reader knows that the equation at ♥1
is only assumed. But the reader is never alerted that the induction step is over
and the final conclusion is left off as well, so an inexperienced reader has the
impression that the proof is unexpectedly over.
But the skeleton is there, and when confronted with an argument like this, the
unconvinced reader should at least write out specifically the implication being
The problem is not that it is ugly, but that it does not show what is intended. It
shows the implication
which is trivial because the consequence is true. That implication does not show
that (n + 1)3 − (n + 1) = (n3 − n) + 3(n2 + n). Something valid in a similar
style is
(n + 1)3 − (n + 1) = n3 + 3n2 + 3n +
1 − n −
1
= (n3 − n) + 3(n2 + n)
Exercises
1. Rewrite both the statement and the proof of the second example in the style
of the first one.
2. Weave the following bit of algebra
(n + 1)2 − (n + 1) = n2 + 2n +
1 −
1 = (n2 − n) + 2n
into an induction proof that n2 − n is always even. Write out carefully the
statement to be proved, identify and prove the base case. Include explicitly
the implication you establish in the induction step.
Exercises
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
and isn’t that just how we would write the bit vector for the set {n ∈ N | n ≤ 10}.
That is the connection. Predicate logic, with the predicates confined to the natu-
ral numbers, is equivalent to Boolean functions defined on the natural numbers.
That in turn is directly linked by the bit vectors to sets defined on the universe
U = N. Here we really can completely link ∪ and ∨, ∩ and ∧, (−)c and ¬, and
mostly importantly, ⊆ and ⇒.
Yes, the subjects are different in total, but with the correct restrictions, they
are exactly the same.
Exercises
1. Write the set whose bit vector corresponds to the predicate (n < 4) ∧ (n = 2)
for n ∈ D.
2. Consider the true implication, “If n is prime and n is even, then n = 2”. Try
to express this using set theory alone.
3. Consider the set X = {n ∈ N | n = 5k + 1; k ∈ N}. Re-express it as a Boolean
function.
Note that we naturally take bn+1 = 0. An alternative, if you want to interpret the
0 and 1 as FALSE and TRUE, is to write gk := [bk = bk+1 ]. Either formulation
allows us to find the bits of the Gray code.
What if we wanted to reverse the process and determine from gn gn−1 · · · g1 g0
which ordinal it had, in other words, how many bit vectors are ahead of it in the
Gray code order. It is natural to look for a formula for n in terms of its binary
bits, bj , and a bit of trial and error would take you to the following:
Theorem 5.8. bk = 0 if the number of 1’s in the sequence gk , gk+1 , gk+2 , . . . is
even, and bk = 1 otherwise.
Let’s do a quick check. Start with 1776 in binary, 11011110000, and translate
to the Gray code using gk := [bk = bk+1 ], giving 10110001000. Now, following
the reverse procedure of Theorem 5.8, move from left to right recording at each
bit the number of 1’s encountered so far, which gives 11233334444, and then
using 0 and 1 to record even versus odd returns us to 11011110000 as predicted.
The actual proof of the theorem is by induction, but in this case it is a back-
wards induction, starting from the nth bit, and proceeding to the 0th. Of course,
we may use in the proof the relation we already have between the bits in the
Gray code gk and the binary bits bk , namely that gk := [bk = bk+1 ].
Proof. Base case: For the nth bit of an n digit binary number, or n digit Gray
code, the nth bits correspond, and the claim is true in this case.
Induction step. Let k be given, n ≥ k > 0, and suppose bk satisfies the claim.
There are four cases for the pair bk and bk−1 .
If bk = bk−1 = 0 or bk = bk−1 = 1 then it follows that gk−1 = 0, and the
number of 1’s in the sequence gk , gk+1 , gk+2 , . . . is exactly the same as in
gk−1 , gk , gk+1 , gk+2 , . . ., and bk−1 = bk correctly records whether that number
is even or odd by the induction hypothesis.
On the other hand, if bk = bk−1 , then gk−1 = 1, and the number of 1’s
in the sequence gk , gk+1 , gk+2 , . . . is exactly one fewer than that in gk−1 , gk ,
gk+1 , gk+2 , . . ., since bk correctly measured the evenness of the number of ones
in the first sequence by the induction hypothesis and bk−1 = bk , bk−1 correctly
measures the parity of the number of 1’s in the second.
There is a fast direct proof which uses some number theory but even that one
requires care. Here there are two different binary strings and an index set to be
kept in line, together with the inductive variable, so you should not be surprised
if you need to read it through more than once to get the complete picture.
So for example abcde is even because all pairs are in order. For edcba all
pairs are out of order, but there are 52 = 10 of them, so edcba is also even. Re-
versing four characters dcba is also even since the 42 = 6 is even, but f edcba
6
is odd because 2 is 15. The number of out of order pairs is called the inversion
number of the permutation. In general it can be computed by counting, for each
character, how many characters to the right of it precede it in the ordering on
the set. So for bcedf ga we have 1 + 1 + 2 + 1 + 1 + 1 + 0 = 7 which tells
us it is an odd permutation. You may recognize the numbers in the sum since
we computed exactly the same values to determine that bcedf ga had exactly
1 · 6! + 1 · 5! + 2 · 4! + 1 · 3! + 1 · 2! + 1 · 1! + 0 · 0! permutations ahead of it in
lexicographic order.
There is a key observation about the evenness of permutations, which we
may prove by induction, which involves transposing pairs in a string. Transpos-
ing two characters in permutations exchanges their positions. So transposing 3
and 5 in 6234157 gives the permutation 6254137. Of course, if you transpose a
pair twice, you return to the original.
Theorem 5.10. Given any permutation, transposing any two characters trans-
forms the permutation from even to odd, or vice versa.
Base case. If the characters transposed are next to one another, then trans-
posing them puts them in order if they were out of order, and puts them out of
order if they were in order. Other than that, all other pairs have the same relative
position and have the same order type they had before. Thus the total number of
misordered pairs is changed by exactly one, and the inversion number is changed
from even to odd, or the reverse.
Induction step. Let k be given and suppose the result is true for all transpo-
sitions separated by k characters. Suppose the pair σi and σj are separated by
k + 1 characters. Then the permutation σ can be written σ = Xσi Y σm σj Z with
the string Y having k characters. Make the following three transpositions:
FIGURE 5.1 Sam Loyd’s 14–15 puzzle. Initial position on the left.
an even number of transpositions. Loyd knew not only that it was impossible
for anybody to ever be able to bring the squares into order and collect the prize
money, but also that very few people would be able to understand why it was
impossible and why they were failing over and over and over.
It is easy to find inexpensive plastic versions of the sliding squares mecha-
nism, but they are always sold with the squares in the proper order, with the idea
that children can amuse themselves by disordering and reordering the squares.
If you want to use one of these toys but achieve the same feeling of frustration
that Loyd’s contestants did, then try to return the blank to the original position
with
15 the squares in reverse order. That is an odd permutation of the squares since
2 = 105.
FIGURE 5.2 The Towers of Hanoi with 7 disks in states 0000000 and 2100212.
If you have paused to come up with a formula on your own, you probably got
the formula 2d − 1, and that is what we will prove.
Theorem 5.12. In the d-disk Towers of Hanoi problem, the disks may be moved
from state 0 to state 3d − 1 in at most 2d − 1 moves.
Note that, since the states are encoded with ternary numbers, state 3d − 1
has all d disks on post 2, and state 0 has all d disks on post 0. As expected, the
proof is by induction on d, and the base case will be d = 1. (Even though the
formula sort of works for d = 0 too.)
Proof. For d = 1, the disk is unrestricted and can be moved from hell to heaven
in one move.
Let d be given and suppose the theorem is true for d disks. We want to
show that a tower of d + 1 disks can be moved in at most 2d+1 − 1 moves.
Temporarily swapping the labels on posts 1 and 2, the induction hypothesis says
that we can move the top d disks from hell to earth in at most 2d − 1 moves.
Now the bottom disk is free to be moved to heaven, where it can stay for the
remainder of the procedure without violating any rules. Then, relabeling posts 1
and 0, the induction hypothesis allows us to move the d disks on earth to heaven
in at most another 2d − 1 moves. See Fig. 5.3.
Virtually the same proof, and the same figure, proves the following compan-
ion observation. This is a tribute to the power of the inductive method, which,
with a little care, can leverage many results from one very small insight.
Theorem 5.13. In the d-disk Towers of Hanoi problem, the disks cannot be
moved from state 0 to state 3d − 1 in fewer than 2d − 1 moves.
Try to write out the proof. You just need to modify the words in the first
proof, leaving all the equations and variables right where they are. These two
theorems work together to tell us that the optimal solution takes exactly 2d − 1
moves.
Can you show it is the unique optimal solution?
So, what if we start in some other legal position? Here is an informal induc-
tion that we can again stack everything on post 0 in at most 2d − 1 moves. The
base case is trivial. Assume it works for d disks, and suppose we have a legal
position with d + 1 disks. If the largest disk is on post 2, leave it there, and we
can move the remaining disks on top of it in at most 2d − 1 moves by the induc-
tion hypothesis, and 2d − 1 < 2d+1 − 1. If the largest disk is not on post 2 then,
by the induction hypothesis, we can move all the other disks legally on the other
post, not 2 and not the one containing the largest disk. Then move the largest
disk onto post 2, and use the induction hypothesis again to pile the smaller disks
on top of it, altogether a total of, at most, (2d − 1) + 1 + (2d − 1) = 2d+1 − 1
moves.
This is essentially the same argument again! Now, what if the disks are
stacked illegally, say an evil Genie randomly dropped the disks on the posts
regardless of the rules, but we still want to move them to heaven using only
legal moves. Can it be done? How quickly?
Here is a completely different question. For d = 7, the fraction of legal states
used in the optimal solution is (2/3)7 , less than 6% of the states. How do we
recognize the states in the optimal solution? Or, given a state, what is the best
move to make? How many problems can be solved by just tweaking the original
inductive proof? There are so many interesting questions one can ask.
Definition 5.14. The Fibonacci sequence is obtained recursively from the equa-
tions
f0 = 0, f1 = 1, fn+1 = fn + fn−1 . ♠
The sequence starts innocently enough, and at the end of six months the
number of pairs is still in the single digits, but after only two years there are
almost fifty thousand pairs:
The growth looks exponential, and that is one way of analyzing the behavior. In
any case, the growth depends on the fraction of the population which is at least
one month old, fn−1 /fn , which, after the first few months have passed, seems
to be about 2/3, and is at least 1/2.
Theorem 5.15. For n ≥ 2, fn−1 /fn ≥ 1/2.
Of course we prove this by induction.
Proof. Base case: If n = 2 then f1 /f2 = 1/2, which is spot on, and for n = 3,
then f2 /f3 = 2/3 ≥ 1/2.
Induction step: Let n ≥ 3 be given and assume fn−1 /fn ≥ 1/2 and
fn−2 /fn−1 ≥ 1/2. Rearranging the inequalities gives fn ≤ 2fn−1 and fn−1 ≤
2fn−2 , and adding these gives fn + fn−1 ≤ 2fn−1 + 2fn−2 , or fn+1 ≤ 2fn
using the recursive formula. Thus fn /fn+1 ≥ 1/2, as required.
So the theorem is proved by induction.
You should check that the inductive argument is correct, that the base cases
are correct and fit together with the strong induction step.
By the theorem, for months beyond 2, the next month’s rabbits will be at
least the current month’s rabbits, plus the number of leverets born to at least
half the population, altogether at least 1 + 1/2 = 3/2 of the current population.
This gives an exponential lower bound on the Fibonacci sequence:
fn+2 ≥ f2 (3/2)n .
Perhaps one of the most surprising results about the Fibonacci numbers is
the equation
√ √
(1 + 5)n − (1 − 5)n
fn = √ (5.4)
2n 5
The proof by induction just follows the model above, but it takes persistence
and there is some tricky algebra. Even if you get through the proof, the result
still looks quite mad. Only the cases n = 0 and n = 1 seem easy to verify. Still,
it is a good exercise to verify that
√ √
(1 + 5)5 − (1 − 5)5
f5 = 5 = √
25 5
using the Binomial Theorem. And, if you really like algebra, you can try to find
a direct non-inductive proof of Eq. (5.4) using only the Binomial Theorem.
10. Let e0 = 1 and e1 = 3, and define en+1 = 5en − 6en−1 for n ≥ 1. Prove
en = 3n for all n ≥ 0.
11. Let e0 = 0 and e1 = 1, and define en+1 = 5en − 6en−1 for n ≥ 1. Prove
en = 3n − 2n for all n ≥ 0.
12. Let the recursive sequence gn be defined by g0 = 2, g1 = 5 and satisfying
gn+1 = gn + 6gn−1 for all n ≥ 1. Show that for all n ≥ 0, the formula
gn = [3n+2 + (−2)n ]/5 is valid.
Set structures
6.1 Relations
With mathematical sets to describe our objects of interest, and predicate logic
to communicate what is true about them, we can now be said to have reached
a critical juncture in our study of discrete mathematics, “this is not the end,
this is not even the beginning of the end, this is just perhaps the end of the
beginning”. From here one can see, stretching out in many directions and with
much intertwining, the many and various branches of discrete mathematics. But
wherever you travel, logic and sets will be the underpinning.
This chapter is the introduction to a huge area of set structures, in which
sets and their elements are not just to be thought of in isolation, but in con-
cert with other sets. There are many forms of set structures; a vast array of data
structures, algebraic structures, combinatorial structures, geometrical and topo-
logical structures, only a few of which we will touch upon. We have already
seen several set structures, such as strings and bit vectors, both data structures.
Those are key examples because they illustrate the two most common ways of
building set structures – via subsets and via the Cartesian product.
In this chapter we will concentrate on relations, arguably the most basic ex-
ample. ‘Set structure’ is an idea, like discreteness, but in mathematics “relation”
is not the vague term which floats about in natural language, it has a set mathe-
matical definition, which you must learn.
That seems very innocent, but it is surprisingly powerful. If you are program-
ming a chess game, then you have many sets of interest, certainly the pieces P
and the set of squares S. The most basic relation would be the board relation
B ⊂ P × S with the elements of B being those pairs (p, s) for which piece p is
currently on square s.
Here is a more mathematical example:
L = {(n, m) ∈ Z × Z | n < m}
also commonly writes 2L18 or 2 < 18, with the symbol infix, instead of writing
(2, 18) ∈ L or the, admittedly ugly, (2, 18) ∈ <. Many of the common math-
ematical symbols you know, ∈, ⊆, =, etc. are examples of relations, and are
usually written in infix notation.
Another common notation, which is particularly valuable for small sets, is
the relation diagram: You place a labeled point for each element a ∈ A, and for
each element b ∈ B, and draw an arrow between the points associated with a
and b if a is related to b by R, that is if (a, b) ∈ R, that is, if aRb.
Example 6.2. In Fig. 6.1 we have a set of four common household ingredients
and a set of four recipes in which they are used, and the diagram defines a
relation U . So we have that (eggs, treacle) ∈
/ U , but milkU ice cream. For small
sets it is not hard to make a diagram which is far easier to understand than listing
the elements in the relation set. ♦
Exercises
1. Let R ⊆ A × D be the relation between the set A of letters and the set D of
digits by setting aRd if the letter a occurs in the spelling of the English word
for the digit d.
Draw the relation diagram for R.
2. Let ♥ be the relation between P3 ({0, 1, 2, 3, 4}) and P2 ({2, 4, 6, 8}) by set-
ting A♥B if two elements of A sum to an element of B. Draw the relation
diagram of ♥.
3. Consider all relations between the set X = {2, 4, 8} and itself. How many
relations do not have any element related to itself?
Note that these notions are only defined for functional relations. In Fig. 6.3
we see the diagrammatic features of the one-to-one and onto functional rela-
tions. The onto relation has at least one incoming arrow at each target node,
and the arrows of the one-to-one diagram are all completely separated from one
another.
FIGURE 6.3 Four functional relations, one onto, and one one-to-one.
Example 6.5. For the set of pieces in play in the game of chess, the relation
between those pieces and the 82 positions they can occupy on the board is func-
tional, because each piece occupies exactly one square on the board. The relation
is also one to one because each square on the board can have at most one piece.
The relation is not onto, because, no matter the configuration, there are sixty-
four positions and at most thirty-two pieces in play. So there will always be
target positions without pieces.
The relation between the pieces in play and the colors black and white, indi-
cating to which side the piece belongs, is also functional. Each piece is assigned
exactly one of the two colors. The relation is also onto since the two kings,
one of each color, are never removed from the board, so both target colors are
represented. The only way for the relation to be one-to-one is in a stalemate
configuration with only the two kings, one of each color.
If the positional relation is expanded to the whole set of 32 chess pieces, the
positional relation will often fail to be functional. As soon as a piece is captured,
that piece is removed from the board and so has no position related to it. (If a
competing chess analyst insists on a functional relationship, he may define a
special 65th position, off the board, to act as the “graveyard” for the captured
pieces.) ♦
The obvious cardinality conditions mentioned in the example occur quite
often, and are stated here as a theorem.
Theorem 6.6. Let D and T be finite sets. If |D| > |T |, then there can be no
one-to-one function f : D → T . If |D| < |T |, then there can be no onto function
g :D →T.
Exercises
1. Define a relation on Z × Z which has no element related to itself, and is not
functional.
Theorem 6.7. Let D and T be finite sets. The number of functions with domain
D and target T is |T ||D| .
|T |!
Of those, if |D| ≤ |T |, there will be one-to-one functions.
(|T | − |D|)!
|T |
k |T |
If |D| ≥ |T |, then (−1) (|T | − k)|D| functions will be onto.
k
k=0
If |D| = |T |, then |D|! = |T |! will be both one-to-one and onto.
The results for general functions and the one-to-one functions are an easy
consequence of the multiplicative principle, choosing target elements for each
domain element, using straight independence for general functions, and weak
independence for one-to-one.
For a function that is both one-to-one and onto, we must have that |D| = |T |,
and |T |!/(|T | − |D|)! = |T |!. In this case we also have the following special
situation, whose proof is left as an exercise.
Theorem 6.8. For finite sets with |D| = |T |. Every one-to-one function is also
onto, and every onto function is also one-to-one.
It is a common error to misread this; the theorem does not say that, if |D| =
|T |, then all functions are one-to-one and onto. The only case where all functions
are one-to-one is |D| = 1, and the only case where all functions are onto is
|T | = 1.
Counting the number of onto functions has been left for last, because that
is the hardest case. Let us compute the number of non-onto functions by inclu-
sion/exclusion. Let t ∈ T and define Ft to be set of all functions D → T for
which the target element t is unrelated.
The set we want to count, the set of
non-onto functions, is the union t∈T Ft and inclusion/exclusion gives, taking
Exercises
1. Let A = {1, 2, 3, 4, 5} and B = {a, b, c, d}.
How many functions are there from P2 (A) to P2 (B)?
How many are one-to-one?
How many are onto?
How many are one-to-one and onto?
2. How many functions are there with domain and target both P(P(P(∅)))?
How many are one-to-one?
How many are onto?
How many are one-to-one and onto?
3. Let A = {a, b, c, d, e}, and B = {1, 10, 100, 1000}. How many functions are
there from B × B to A × A which are one-to-one but not onto?
the existence of the related target element, Eq. (6.1) and the uniqueness of the
related target element, Eq. (6.2).
These conditions, with domain and target reversed, are the conditions for
one-to-one and onto. A function f : D → T is one-to-one if
To show a function is one-to-one: Let two domain elements be given with the
same target, f (d) = f (d ), and show those two domain elements must coincide,
d = d .
To show a function is not one-to-one: Exhibit any pair of distinct domain
elements which are related to the same target element.
Neither of the previous examples were one-to-one. For f , we have the
violating pair f ({1}) = f ({1, 2, 3}) = 1. For g, we can take g(1) = g(3) =
{1, 3, 5, 7, 9}.
Exercises
1. Let D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Define a function
h : P8 (D) → P2 (D)
by setting h(X) to be the subset consisting of the largest and smallest ele-
ments of X. So h({0, 1, 2, 3, 4, 5, 6, 7}) = {0, 7}.
Show that h is not onto.
Define any onto function, g, from P8 (D) → P2 (D).
2. For the function h of the previous exercise, show that h is not one-to-one.
3. Let D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Define a function f : P(D) → N by set-
ting f (∅) = 0 and f (A) to be the number of different numbers which can
be expressed in some base b, with 1 < b ≤ 10 using the digits in A, each at
most twice.
So, for f ({1, 2}), we would consider numbers like 2 or 22 or 1212 all in base
10, or 5 in base 3, 5 = 123 , or 10 in base 8, 10 = 128 , 56 = 2115 , etc.
Show that f is not onto.
2n n>0
f (n) = .
3−n n≤0
hand, if f (n) is odd, then it can only be a power of 3, and the same algebra
starting with m = 3−n = 3−n , gives the result in this case as well. ♦
n/2 if n is even
g(n) = .
−(n + 1)/2 if n is odd
Both of these examples are counterintuitive, in the sense that, for the first,
we have a one-to-one function from a set to a smaller subset, and in the second,
an onto function from a subset to a larger set. This situation could not happen
for finite sets, and is sometimes called a Hilbert’s Hotel phenomenon.
You can think of the first example as a way of assigning an infinite number
of guests, labeled by the integers, to the infinite number of beds, labeled just
by the natural numbers, in the Hilbert Hotel. Each guest is assigned exactly one
bed, so the relation is functional. Moreover, at least for the function f , no bed
is assigned to two people – a one-to-one function. It sounds impossible, since
there are infinitely many more guests than beds. But the one-to-one function
f manages the task and even has an infinite number of beds left over! The
sequence of beds labeled from 100 to 200 is almost completely unused. The
only power of 2 in that range is 27 = 128. So the 7th positive guest has that
whole wing to himself since the powers of 3 skip those beds completely, going
from bed 34 = 81 to bed 35 = 243.
The second example seems just as strange in the hotel interpretation. Here
the guests are labeled by the natural numbers, and they show up at an even big-
ger Hilbert Hotel with beds labeled from the set of integers. But the function
g is onto, so somehow, under this assignment, the guests labeled by the natu-
ral numbers fill up the entire hotel, filling every single positive bed and all the
negative beds too!
We end this curious section with yet one more curiosity.
Example 6.15. Let A be a set and let h : A → P(A) be any function from A to
its powerset. So for each a ∈ A we have h(a) ⊆ A.
Define now another subset of A by Ch = {a ∈ A | a ∈ / h(a)}. The curious
property of this definition is that, for any element a ∈ A, we must have Ch =
h(a). This is because the subsets Ch and h(a) disagree over the membership of
the element a. Since the subset Ch is not any of the sets h(a), the function h
cannot be onto. ♦
You may think this is not much of a curiosity. After all, if A = {a, b, c} then
|A| = 3 and |P(A)| = 23 = 8, so the domain is simply too small to support
an onto function to the target. So for finite sets, the fact that there is no onto
function A → P(A) is not a surprise since |A| is always far too small.
But the argument in the example is valid for any domain set, even an infinite
set. There is no onto function N → P(N) either. But how can it be true that the
set of natural numbers is too small? There is an infinite number of them. There
are so many that, in the Hilbert Hotel example, we can fit in all the integers and
have plenty of room left over. But there is no way to fill a hotel with beds labeled
by P(N) if you only have enough guests to be labeled by N. We are forced to
write |N| < |P(N)| and to accept the fact that there are different types of infinite
sets, and that they are compared by one-to-one and onto functions.
Exercises
1. Define f : Z → P(Z) by f (n) = {m ∈ Z | m ≥ n2 }.
Define Cf by Cf = {n ∈ Z | n ∈ / f (n)} and verify that Cf is not f (n) for
any n.
2. Define a function f : {a, b, c, d, e, f, g} → P({a, b, c, d, e, f, g}) so that
Cf = {a, d, e, g}.
3. Here is a “proof” that P(N) is countably infinite. What’s wrong with it?
We define an one-to-one function f : P(N) → N as follows. Pick a set in
P(N) at random, A, assign f (A) = 0. Continue inductively, at the nth step,
choose any set you haven’t chosen already, X, and assign f (X) = n. There
are an infinite number of sets in P(N), so you don’t run out, and the function
is one-to-one since you never reuse a number. So |P(N)| ≤ |N|, hence, since
we already know |P(N)| ≥ |N|, Cantor is an idiot and |P(N)| = |N|.
1 You may sometimes see the notation |N| = ℵ , but we will not use this. Look up “infinite cardi-
0
nals” if you are curious.
Naively we would expect that all infinite sets have equal cardinality, but this
is contradicted by our general cardinality result that |A| < |P(A)|, which is valid
even for infinite sets. In fact, there must then be an infinite number of different
cardinalities of infinite sets, for instance
Let’s conclude this section by listing our conclusions about cardinality which
relate to infinite sets.
Theorem 6.16 (Cantor’s Theorem). There is no onto function f : X → P(X).
Definition 6.17. We write |X| ≤ |Y | if either of the following is true.
• There exists a function f : X → Y which is onto.
• There exists a function g : Y → X which is one-to-one.
If |X| ≤ |Y | is false, we write |X| > |Y |. ♠
Please note that this definition signals a new use of the familiar symbol ≤,
extending its meaning for ordinary numbers, 1 ≤ 17, or for cardinalities of finite
sets |B| ≤ |D| to the new territory of cardinality of infinite sets. We have seen
that it has hidden subtleties and should not be taken for granted.
There is an infinite number of distinct infinite cardinals:
All sets A with cardinality |A| ≤ |N| are said to be countable. If |X| > |N|,
we say X is uncountable.
Theorem 6.18 (Useful Countability Results). The sets N, Z, and Q are all
countably infinite, |N| = |Z| = |Q|.
If A ⊆ B and B is countable, then A is countable.
A subset of a countable set is countable.
If A is countable and k ∈ N, then Pk (A) is countable.
A countable union of countable sets is countable. That is, if I is countable,
and for each i ∈ I , Ai is countable, then
Ai
i∈I
is countable.
If A and B are countable, then A × B is countable.
Theorem 6.19 (Useful Uncountability Results). The sets R and C are both
uncountable.
If A is an infinite set, then P(A) is uncountable.
If A ⊆ B and A is uncountable, then B is uncountable.
The set of all infinite sequences of 0’s and 1’s is uncountable.
Exercises
1. Decide whether R × R is countable or not, and give an explanation. You can
use any of the properties we discussed.
2. Decide whether P5 (Z) is countable or not, and give an explanation. You can
use any of the properties we discussed.
3. Consider the set of all real numbers x, with 0 ≤ x < 1), which are expressible
as decimals in base 10 such that digits do not decrease as you proceed to
the right, like 0.00000112233344444444444444444777777777 . . . . Decide
if this set is countable or not, and give an explanation. You can use any of
the properties we discussed.
Note. The numbers like 0.5 and 0.2224 with invisible zeros at the end are in
the set, since 0.5 = 0.49999 . . . and 0.2224 = 0.222399999 . . . .
Exercises
1. Consider the relation ⊆ on P(N).
Which of the named properties, (reflexive/symmetric/transitive) does it
have? Explain.
2. Consider the relation on six elements whose reduced relation diagram is
FIGURE 6.9 An equivalence relation on {1, 2, 3, . . . , 10} and the corresponding equivalence
classes.
Equivalence relations are very common and are often denoted by symbols
.
such as ≡, ∼, , , ≈, ∼ =, =, ⇔, ↔, , etc. The same pair of objects may be
equivalent in one sense and non-equivalent in another, or equivalent in several
different senses. So, for example, two bishops b and b in chess might be equiv-
alent in the sense they are both black, b ∼
= b , or that they both move on black
.
squares, b = b , or that they are among the bishops, b b . Analyzing or pro-
gramming a chess game probably involves several equivalence relations among
the pieces.
Exercises
1. Draw the reduced relation diagram of an equivalence relation with equiva-
lence classes {a, b, c}, {e}, and {d, f }.
For any equivalence relation on {a, b, c, d, e, f }, how many arrows can it
have? List all possibilities.
2. Define a relation ∝ on Z by setting n ∝ m if there is a k ∈ Z with n − m =
10k.
Show that ∝ is an equivalence relation and describe the equivalence classes.
3. Define a relation on Z by setting n m if there is a k ∈ Z with n + m =
10k.
Decide whether or not is an equivalence relation. If it is, give the equiva-
lence classes. If not, show why not.
This is a geometric puzzle, and it does not hurt to take out a set of dominoes
and try to arrange them in a 6 × 6 grid with no through-roads. It might take you
just a few minutes to succeed. But what if you don’t. Maybe the solution is very
tricky, or maybe it cannot be done. Either way, it is time to analyze the problem
mathematically.
We have plenty of sets which look promising. There is the set of points
in the plane, R2 , the set 10 of possible through-roads, call them R = {e1 , e2 ,
e3 , e4 , e5 , n1 , n2 , n3 , n4 , n5 }, the set of 62 = 36 squares in the grid which are nat-
urally arranged as a Cartesian product, {1, 2, 3, 4, 5, 6}2 , the set B of 18 blocks
with which the grid is to be tiled. We have many relationships we can model.
For instance, the 36 squares are not occurring in isolation. Some pairs share a
side and so could be made into a block. Other pairs do not and can not. This
relation of adjacency is obviously important to the problem.
However, let’s focus on one particular relation, that of obstruction. Once
you have designed an arrangement of blocks, some roads become obstructed by
some blocks, since the road can only go around, and not pass though the block.
In the diagram above, the blocks have been placed so that block 8 obstructs road
n2 . Each block arrangement comes with an obstruction relation
of the subset recording which objects are on the initial side of the fjord. So
{M, W, G, C} is the initial state, and the solution state is ∅.
Now we want to define a relation which encodes when two states are con-
nected by the man starting in a stable state and traveling across the fjord exactly
once. If he traverses the fjord alone, then the new state is obtained from the old
state by either adding or removing M from the state. If he takes object X, then
that object also is added or removed from the state set. We call this the travers-
ing relation and use the symbol . If (A, B) is in the traversing relation set, we
write A B.
So starting from the state {M, W, G, C} we have the sequence of related
pairs
{M, W, G, C} {W, C} {M, W, C} {C} {M, C}
taking us to state {M, C} where we must stop, because {M, C} is not a stable
state, since the Wolf and the Goat are alone on the opposite shore, and no moves
are defined for unstable states. The complete relation diagram for the traversing
relation is shown in Fig. 6.11 where the reader should see the huge advantage of
relation diagrams. So much of the hidden structure of this problem is revealed
first by encoding the problem as a relation, and second by viewing the relation
diagrammatically. It is now not only easy to solve the problem, but also possible
to study and compare different solutions.
Here is a question you can now answer. Suppose someone advises the Viking
to adopt the following strategy. “Only move to a stable state, and, if there is a
choice of stable states, just choose the one you prefer”. Will this result in the
Unfortunately, a viking who really loved his goat and following this strategy
could be caught up in an infinite loop like
in which he rows the goat back and forth and never does anything else. To avoid
this, the strategist adds the rule “Never perform the same action twice in a row”.
Now must the Viking win?
two by winning against the worst team in the league, not against the second
ranked team.
The only case left is if both winners actually lose on day two. Again, those
who watch sports would not be overly surprised, since there is always some
element of chance. Nevertheless it would be regarded as a fluke, an unexpected
result, something outside the game, if the results so far looked like
P ≺ S
R W
FIGURE 6.12 Magic Dice: {2, 2, 2, 2, 8, 8}, {3, 3, 4, 4, 5, 5}, {0, 0, 6, 6, 6, 6}, {1, 1, 1, 7, 7, 7}.
We might expect that such a simple match-up must have results in a strict
partial order, but it is easy to check that
{2, 2, 2, 2, 8, 8} {1, 1, 1, 7, 7, 7}
{3, 3, 4, 4, 5, 5} ≺ {0, 0, 6, 6, 6, 6}
with dice whose numbers seem to have only two aspects; the extreme values on
the die versus how often those extreme values are represented; we have non-
transitivity. Just those two aspects are enough to explode the notion of “skill
level” which makes the strict partial order seem to be the obvious relation type
to expect for sport tournaments. ‘Skill level’ is one of those ideas which leads
us to expect a one-dimensional result, but even for our simple dice we find a
multi-dimensional phenomenon.
So even in something so direct and pure as four sailors on a submarine
contesting by arm wrestling, there are enough aspects, bicep strength versus
arm length, to make the contest results interesting, complex, and perhaps non-
transitive.
Notice in Fig. 6.13 that each equivalence class has even cardinality. Let prove
that true in general by induction. You might ask, what is the “for all n” statement
that we want to prove? The induction will be very short. We will show that each
of the 5 north/south roads is obstructed by an even number of blocks.
Base case: The leftmost road. The first column of squares is filled partially by
some north/south aligned blocks, which uses up an even number of squares, and
partially by some east/west aligned blocked, which stick out and obstruct road
one. Since the north/south aligned used up an even number of the six squares in
column one, road one is obstructed by an even number of blocks.
Inductive step. Suppose the nth road is obstructed by an even number of
blocks. Consider the column of squares on its right edge. An even number of
squares are used up by the north/south aligned blocks, and an even number of
stick out to the west obstructing road n by the inductive hypothesis, so there are
an even number left to stick out to the right and obstruct road n + 1.
So all 5 north/south roads are obstructed by an even number of roads by
induction. The same finite inductive argument works for the five east/west roads.
This completes the proof.
Now let’s define a new obstruction function O whose domain is the set of
equivalence classes, to the set of roads, assigning each class to the road which
each element in the class obstructs. Again, we want to know if it is possible for
O to be onto, and obstruct all the roads.
How many equivalence classes can there be? Equivalence classes are never
empty, and these are of even cardinality, so the 18 blocks can be in at most 9
equivalence classes. But there are 10 roads. So the new obstruction function O
can never be onto for any design, and so it is impossible to obstruct all 10 roads.
Observe that in Fig. 6.13 the blocks are partitioned into 6 equivalence
classes, so four roads are unblocked. Can you find them? In a sense, the de-
sign in Fig. 6.10 is optimal since there is only one unblocked road.
Note that for the 8 × 8 grid we have, by the same arguments, 16 possible
equivalence classes and only 14 roads to block. Identify the 14 equivalence
classes for the 8 × 8 design in Fig. 6.10.
The relation can be a bit quirky in some special situations. So, if nec-
essary, turn the figure slightly so that the lowest point of the circle is not an
element of V , and so that no chord is either horizontal or vertical. Also, we
know that we don’t get the maximum number of regions in situations like the
regular hexagon, where all the chords meet in the middle, so let’s only consider
the situation where at most two chords meet at any interior point. Call this a
general collection of chords, see Fig. 6.14.
FIGURE 6.14 Illustrating the relation for non-empty sets of a general collection. The region r
is shaded.
Theorem 6.26. For general figures, the function is one-to-one and onto.
Proof. is onto: Let r be a region. It has a lowest point. If that lowest point
is an interior point of the circle, then it is the intersection of two chords, which
have four endpoints {a, b, c, d}, and ({a, b, c, d}) = r. On the other hand, if
the lowest point is on the boundary, that lowest point is either an element of V ,
or it is the very lowest point of the circle. If it is an element b ∈ V , then either
one or two chords at b are boundaries of r, and one of them, ab, separates r
from the lowest point, so ({a, b}) = r. Lastly, if the lowest point of r is the
lowest point of the circle, then (∅) = r.
f (x) = {A ⊆ X | x ∈ A}
Theorem 7.2. If n > 1 is not prime, then n has a prime divisor no larger than
the square root of n.
Theorem 7.2 is the basis for a method of determining primes known as
the Sieve of Eratosthenes. You start with a list of all primes up to N , P1 =
{2, 3, 5, . . . } and then form a second list L of all values in N up to N 2 . Then
cross off from L the values 0, 1 and all multiples of elements in P1 . When that
is done, all remaining elements of L are added to P1 to form P2 , which by
Theorem 7.2 contains all the primes up to N 2 .
Example 7.3. If P1 = {2, 3, 5, 7}, which are all the primes up to N = 10, then,
indicating the crossed out terms with subscripts, the sieved list L
0x 1x 22 33 42 55 62,3 77 82 93
102,5 11 122,3 13 142,7 153,5 162 17 182,3 19
202,5 213,7 222 23 242,3 255 262 273 282,3,7 29
302,3,5 31 322 333 342 355,7 362,3 37 382 393
402,5 41 422,3,7 43 442 453,5 462 47 482,3 497
502,5 513 522 53 542,3 555 562,7 573 582,3 59
602,3,5 61 622 633,7 642 655 662,3 67 682 693
702,5,7 71 722,3 73 742 753,5 762 777 782,3 79
802,5 813 822 83 842,3,7 855 862 873 882,3 89
902,3,5 917 922 933 942 955 962,3 97 982,7 993
records all the primes P2 = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79, 83, 89, 97} up to 102 = 100. ♦
We could now use the list in the example to sieve out a list of the primes up to
1002 = 10, 000. In doing so, we certainly would use a computer, but historically
the automation has been done also with various mechanical methods, such as
strips of paper with appropriately punched holes – ‘the sieves’.
Example 7.4. The 132 problem. Show that 132 = 11 · 19 using only the primal-
ity of 11, 13, and 19.
Of course, you can multiply, 132 = 169 and 11 · 19 = 209, but that is “cheat-
ing”. The solution should look more like what you naturally will do to show
that 52 = 2 · 13, where you don’t multiply at all and just note that the number
on the left is odd, and the number on the right is even. So we are looking for an
argument that only uses the fact that 11, 13, and 19 are primes. ♦
Primality arguments involve the unique factorization of an integer into
primes, and the 132 problem highlights that this fact is not obvious.
1. Use the Sieve of Eratosthenes to find all the primes up to 166.
2. Suppose you wanted to decide if 507 was prime. What is the largest prime
you need to check?
Is 507 prime? If not, give a prime factorization.
3. Give a prime factorization of 1776. Begin as efficiently as possible.
Proof. We will show that, in fact, the pair {n, m} has the same set of common
divisors as the pair {m, r}, and we’ll use the double inclusion method.
Let d be a common divisor of m and r, so m = id and r = j d. Then n =
mq + r = idq + j d = (iq + j )d, and d | n, and so d is a common divisor of n
and m.
On the other hand, let d be a common divisor of n and m, so n = ud and
m = vd . Then ud = vd q + r, so r = ud − vd q = (u − vq)d , and so d is a
common divisor of m and r.
Example 7.8. To compute gcd(1776, 5280) using Theorem 7.7, divide 5280 =
1776 · 2 + 1728 giving gcd(5280, 1776) = gcd(1776, 1728). But don’t stop
there. Divide again 1776 = 1728 · 1 + 48 giving gcd(1776, 1728) = gcd(1728,
48). Then 1728 = 48 · 36 + 0, so 48 | 1728, and of course gcd(1728, 48) = 48.
And that means gcd(1776, 5280) = 48. ♦
This repeated use of Theorem 7.7, as in Example 7.8, is called the Euclidean
Algorithm.
Exercises
1. Use the Euclidean Algorithm to find the greatest common divisor of 123 and
321.
2. Use the Euclidean Algorithm to find gcd(988887, 888887). Take any short-
cuts you like. (But only hand calculations.)
3. Show using the Euclidean algorithm that 100 and 169 are coprime.
58 = 21 · 2 + 16 (scale by 4)
21 = 16 · 1 + 5 (scale by −3)
16 = 5·3+1 (scale by 1)
5 = 1·5+0
we find that gcd(58, 21) = 1, that is, the coins A and B are coprime, so it is
conceivable that there is a solution.
In fact, the four equations above for the divisions with remainder in the Eu-
clidean algorithm hold the key to finding the solution to Euclid’s coin problem.
Adding the three upper equations, appropriately scaled, will cause the terms in
the unwanted remainders, 5 and 16, to cancel out. The surviving terms combine
into (4)(58) + (−3)(21) = (8)(21) + 1, or (4)(58) + (−11)(21) = 1. So with
coins A = 58 and B = 21 we can pay one talent by paying 4 Alexanders, and
getting back 11 Bucephaluses in change.
How were the scaling factors chosen? Bottom to top. Factor 1 was chosen so
that the gcd(58, 21) = 1 would not be altered. Scaling factor −3 was chosen to
cancel out the two terms for remainder 5. Then scaling factor 4 was chosen to
cancel out the three terms for remainder 16. ♦
Euclid’s Coin Problem is not just recreational mathematics. It turns out to
be an important problem in understanding number theory, and the Euclidean
Algorithm has an extension specifically designed to compute the scaling factors
needed to solve the coin problem. This is an alternative to the linear algebra
approach of the previous example.
Theorem 7.13. Given positive integers A and B, there exist integers s and t
with sA + tB = n if and only if gcd(A, B) | n.
So we not only know when the coin problem has a solution, using the ex-
tended Euclidean algorithm, we can find the required numbers “quickly.”
Let’s now return to the 132 problem. Why, just by the primality of 11, 13,
and 19 is it impossible that 132 = 11 · 19?
We may not know much more about primality, but we now know a lot more
about coprimality. The numbers 13 and 19 are coprime, so we can solve Euclid’s
Coin Problem: there are numbers s and t with s · 13 + t · 19 = 1. Multiplying
both sides by 13 gives s · 132 + t · 19 · 13 = 13. But if 132 = 11 · 19, then we
could substitute: s · 11 · 19 + t · 19 · 13 = 13, or (s · 11 + t · 13)19 = 13, which
says 19 | 13, violating 13’s primality.
Notice that we did no arithmetic, and we did not even bother to actually
figure out the solution to the coin problem. We just used the fact that there was
a solution.
The argument solving the 132 problem, with just a little attention to detail is
used in Section 7.9 to show that integers satisfy unique prime factorization.
Exercises
1. Suppose Alexander is worth 34 talents and the Bucephalus is worth 21 tal-
ents. How can you pay a bill of 7 talents?
2. Find s and t such that s · 449 + t · 106 = 1.
3. Find s and t such that s · 111 + t · 99 = 1 or prove that none exists.
Why not try the same split to express threeness, and call those numbers di-
visible by 3 “threven”, and those not “throdd”. But that setup does not respect
the arithmetic: 2 and 3 are throdd, and 2 + 3 = 5, which would say that adding
two throdds gives a throdd, but 4 and 5 are also both throdd, and 4 + 5 = 9,
threven.
You have probably already anticipated from division with remainder that
we need three classes. So let’s redefine throdd as those numbers which, when
divided by 3, leave a remainder of 1, and invent a new word thweird, for those
which leave a remainder of 2. Threven numbers have remainder 0 when divided
by 3, so now every number is in exactly one of the classes – threven, throdd, or
thwierd. Now we have new pseudo equations and if you test, you find that they
all actually do work, like
and there are several more. Everything favors pursuing this analogy in the study
of the trinary aspects of the natural world except the notation. Not only are the
words ugly and awkward, we will need many more of them, since we will also
want to pursue the fourfold analogy, and the fivefold . . . .
So let’s proceed immediately to the general case, to the n-fold analogy to
even/odd in which the number n is called the modulus. Two integers a and b
are said to be congruent modulo n, and we write a ≡ b mod n, if a = b + kn
for some k ∈ Z. Congruence modulo n is a relation which is reflexive, symmet-
ric, and transitive; hence congruence modulo n is an equivalence relation. We
are particularly interested in the equivalence classes since they are exactly the
sets of numbers which have the same remainder when divided by n. There are n
equivalence classes, one for each remainder 0, 1, 2, . . . (n − 1), and those sym-
bols are used to denote the equivalence classes. The set of equivalence classes
for modulus n is denoted by Zn = {0, 1, 2, . . . , n − 1}.
For modulus 2, the equivalences classes are the even and odd numbers,
with the even numbers denoted by 0 and the odd numbers denoted by 1, Z2 =
{0, 1}.
For modulus 3, Z3 = {0, 1, 2}, and the symbol 1 stands for the equivalence
class of numbers whimsically called throdd above. This abuse of notation ac-
tually causes less confusion that you might imagine, but you should still be
cautious. We know that the number 1 is not equal to the set of odd numbers, and
the set of odd numbers is not equal to the set of numbers which have remainder
1 when divided by 3; but we are now using the symbol “1” for all three of them,
and many others.
But the set theory is secondary. What gives the numbers modulo n so much
power is the arithmetic. The classes with the same modulus can be added and
multiplied consistently, just as the even and odd numbers can.
Even better, this modular arithmetic inherits all the important properties of
arithmetic in Z. Addition and multiplication in Zn is commutative and asso-
ciative, and the distributive law holds. There is an additive unit, always written
with symbol 0, and a multiplicative unit, with symbol 1. You will have to prac-
tice this new arithmetic, in which 7 + 6 ≡ 13 mod 20, 7 + 6 ≡ 0 mod 13, and
7 + 6 ≡ 4 mod 9. Each set Zn has its own addition and multiplication table, such
as the ones below for Z5 .
+ 0 1 2 3 4 × 0 1 2 3 4
0 0 1 2 3 4 0 0 0 0 0 0
1 1 2 3 4 0 1 0 1 2 3 4
2 2 3 4 0 1 2 0 2 4 1 3
3 3 4 0 1 2 3 0 3 1 4 2
4 4 0 1 2 3 4 0 4 3 2 1
Note that, if the modulus is clear from the context, many authors will abbreviate
17 + 6 ≡ 10 mod 13 to 17 + 6 ≡ 10, or often just 17 + 6 = 10.
Exercises
1. For each of the following, compute the results modulo 2, 3, 5, 10, and 11. In
each case express the answer from 0 to the modulus minus one: 6 + 7, 8 + 8
2 · 8, 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9, 5280 + (65)(88), 5280 − (65)(88).
2. Make addition and multiplication tables modulo 7. Find all pairs of additive
and multiplicative inverses.
3. Make addition and multiplication tables modulo 8.
Find all pairs of additive and multiplicative inverses.
Example 7.17. Find the multiplicative inverse of 1776 modulo 2021. Find a
few other pairs of multiplicative inverses in Z2021 .
For Z11 , we need the multiplicative inverse of 3. We can always use the Ex-
tended Euclidean Algorithm, but it is never a bad idea to look for a quick
shortcut first. 1 ≡ 12 mod 11, and 12 = 3 · 4, so the multiplicative inverse of
3 in Z11 is 4. So 3x = 2 gives 4 · 3x = 4 · 2. Modulo eleven we have
In Z12 , the number 3 has no multiplicative inverse. But maybe we can solve
3x ≡ 2 mod 12 anyway. That would mean 3x = 2 + k · 12 for some k. That
would give us 3x − 12k = 2 or 3(x − 4k) = 2, which is impossible since 3 does
not divide 2. We conclude that 2/3 cannot be defined in Z12 , and the equation
3x ≡ 2 mod 12 has no solution. (The obstruction was that 2 was not divisible by
3. What about the solving 3x ≡ 9 mod 12?) ♦
Exercises
1. Find the multiplicative inverse of 5 modulo 66.
Solve the equation 5x = 3 in Z66 .
2. Find the multiplicative inverse of 12 modulo 25.
Compute 5/12 modulo 25.
3. Find all multiplicative inverses in Z25 .
Let’s return to the parade problem. Suppose that, on more careful examina-
tion, it is found that on Main Street the last row was short, having only three
men, while on Park Avenue the last row was also short, having only two men.
Would those few men change anything?
The number theoretic equations change. From the information on Main Street
we have n ≡ 3 mod 8 and from Park Avenue we know n ≡ 2 mod 11.
One way to proceed is to check one by one all the integers consistent with
Main Street, 3 + k · 8, so 3, 11, 19, 27, 35, . . . , against the requirement of Park
Avenue. This is sufficient for a small problem like this, but will not scale.
It is more effective to take the general expression 3 + k · 8 for the solutions
for Main Street and to solve 3 + k · 8 ≡ 2 mod 11 for k to find which also work
for Park Avenue. We quickly get k · 8 ≡ −1 mod 11, and the next step to isolate
bs · n + at · m + knm
for k ∈ Z.
Proof. The equation guaranteed by the Extended Euclidean Algorithm s · n +
t · m = 1 implies that bs · n ≡ b mod m and bs · n ≡ 0 mod n; while at · m ≡
0 mod m and at ·m ≡ a mod n. Adding them x = bs ·n+at ·m gives the desired
result modulo n and modulo m.
So x is one solution. If y is another, then x − y ≡ a − a ≡ 0 mod n, so
n | x − y, and also m | x − y. Since gcd(n, m) = 1, nm | x − y, and y = bs · n +
at · m + knm.
What if the two moduli are not coprime? There may be a solution: n ≡
11 mod 45 and n ≡ 38 mod 63 has solution n = 101. On the other hand, there
may not: n ≡ 16 mod 45 and n ≡ 32 mod 63 has no solution whatsoever.
This aspect of the problem was also worked out hundreds of years ago and
with the advantage of our modern notation, you have a pretty good chance of
figuring it out.
Exercises
1. Find any integer n such that n ≡ 17 mod 19 and n ≡ 11 mod 13.
2. Find all integers n such that n ≡ 2 mod 19 and n ≡ 5 mod 13.
3. Find any integer n such that 3n ≡ 17 mod 19 and 5n ≡ 11 mod 13.
Diophantus
This tomb holds Diophantus. Ah, how great a marvel!
The tomb tells scientifically the measure of his life.
God granted him to be a boy for the sixth part of his life,
and adding a twelfth part to this,
He clothed his cheeks with down;
After consoling his grief by this science of numbers for four years
he ended his life.
Metrodoros, Epigram 126
Metrodoros gave his epigrams in Greek verse, so you might prefer this more
modern poetical rendering without the strange Greek idioms:
which was old when reprinted in the “Yearbook” of the National Council of
Teachers of Mathematics, 1926.
The challenge is to work out the chronology of the life of Diophantus, ideally
without resorting to a computer or even the use of pencil and paper.
This first key to the puzzle is to understand that the solution is to be a whole
number of years, and approach it as a Diophantine problem, not as one in which
we want to measure his life on a continuous time scale. The second is to notice
that in one couplet his age in years is declared divisible by 12, and another to
be divisible by 7. Since gcd(7, 12) = 1, unique prime factorization requires his
age to be divisible by 7 · 12 = 84. Unless Diophantus were truly marvelously
old, that gives his age as 84, and the remaining spans of years are then easy to
unravel. No equations and algebra, just number theory.
One can also use number theory on the Guarini Problem, the case study
of Section 1.9, a problem in recreational mathematics inspired by chess. The
problem can be successfully recast and attacked using Z9 . Try it.
Consider also the next puzzle which Sam Loyd syndicated in the newspapers
of his day, about the turn of the previous century. Loyd asked “How can you
score exactly 50 points?”
Modular arithmetic holds the key both to how the puzzle was designed, the
way to a super fast solution, and the fact that the solution is unique. Pedestrian
puzzlists trying methodically
10 each selection of 3 or 4 dolls and adding their tags
will be looking at 10
3 + 4 = 120 + 210 = 330 tasks.
Looking at the puzzle modulo 2, the sum of the dolls must be congruent to 0,
and you conclude that you need an even number of odd dolls – but that is not
the best modulus. . .
Ready for more, or want to design your own? New and original puzzles
involving number theory appear all the time. The Pi Mu Epsilon Journal, for
example, always has a section for new and original problems accessible to stu-
dents.
a = n2 − m2 , b = 2nm, c = n2 + m2 . (7.1)
Reading through the logical notation, you might recognize that the upper
condition simply expresses the definition of the primality of p, that is, that p
only factors as p times 1. The second condition, is just what we needed for the
132 problem.
The theorem says that the two conditions are equivalent. That equivalence
implies that the lower condition could also function as the definition of primality.
Actually, in more algebraic expositions, that is exactly what is done. So the
lower condition may be regarded as the definition of primality, and the upper
condition the definition of being irreducible, and the theorem would then be
stating that, for Z, primes and irreducibles are the same.
Of course, the proof will use the double implication method.
Proof. Suppose the lower condition is true. To prove the upper one, let n, and
m be given, and assume that p = nm. So p = 1 · nm and p | nm. From the
lower condition we know that p | n or p | m. If p | n, then n = kp for some
k ∈ Z, and p = kpm. Canceling p gives km = 1. Thus k and m are both 1 and
(n = 1) ∨ (m = 1), as required. If p | m, exactly the same argument applies. So
[p = nm] ⇒ [(n = 1) ∨ (m = 1)], completing the first half. (That was the easy
half.)
Suppose now that the upper condition is true. To prove the lower one, let n
and m be given, and assume that p | nm, that is pk = nm for some integer k.
Case 1: p | n. Then (p | n) ∨ (p | m).
Case 2: ¬(p | n). Then gcd(p, n) = 1. So (Euclid’s Coin Problem again!)
there are integers s and t with sp + tn = 1. Multiplying by m, we have spm +
tnm = m, and substituting pk = nm gives spm + tpk = m, or p(sm + tk) = m.
So p | m, hence (p | n) ∨ (p | m).
So [p | nm] ⇒ [(p | n) ∨ (p | m)], concluding the second part.
Now we can show unique prime factorization! We just had a fancy exercise in
the double inclusion method and implications. The next proof is a fancy exercise
in induction.
Proof. The proof will be by induction on k + k and we have to show the propo-
sition is true for all k + k ≥ 2.
Base case: k + k = 2. Since neither side can be 1, each side contains a prime,
so k = k = 1, and p1 = p1 .
Inductive step. Let k + k be given and assume the strong induction hypothe-
sis, that is, unique factorization holds true for all shorter prime expressions. We
have p1 | p1 p2 · · · pk .
Let’s prove by induction on k that p1 is one of the primes in the product
p1 p2 · · · pk for all k ≥ 1. If k = 1, there is nothing to show, establishing the
10. Let k be given. Find two numbers n and m, n > m, such that n ≡ m mod 3k
but n ≡ m mod 3k+1 .
11. Many people know the equation 32 +42 = 52 . Show that every Pythagorean
triple, a 2 + b2 = c2 with a, b, c ∈ N, has one side divisible by 3, one side
divisible by 4, and one side divisible by 5.
12. Let N be a fixed natural number. Define a relation ≡ on the integers by
setting n ≡ m (mod N ) if n − m is evenly divisible by N .
Show that this relation is an equivalence relation.
It is 2. The first path was invalid. Theorem 7.15 says that modular equivalence
respects addition and multiplication, but says nothing about exponents. The ‘dis-
crepancy’ above illustrates that we must not assume that a i and a j are equivalent
modulo n just because the exponents satisfy i ≡ j mod n. It is the bases of an
exponential which behave as expected, as in the next example.
Example 8.1 (The Rule of Nine). The remainder of a number modulo 9 is same
as the remainder of the sum of its digits.
Let n be a k digit decimal, n = dk−1 · · · d0 , so we may write n = k−1 i
i=0 di 10 .
Since 10 ≡ 1 mod 9, we have 10i ≡ 1i ≡ 1 mod 9. So n ≡ d0 + d1 + · · · dk−1
mod 9.
So 10607 has the same remainder modulo 9 as 1 + 6 + 7 = 14, or 5. ♦
Z10 a1 a2 a3 a4 a5 a6 a7 a8 a9 a 10 a 11 a 12 ···
0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1
2 2 4 8 6 2 4 8 6 2 4 8 6
3 3 9 7 1 3 9 7 1 3 9 7 1
4 4 6 4 6 4 6 4 6 4 6 4 6
5 5 5 5 5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6 6 6 6 6
7 7 9 3 1 7 9 3 1 7 9 3 1
8 8 4 2 6 8 4 2 6 8 4 2 6
9 9 1 9 1 9 1 9 1 9 1 9 1
You see various behaviors for the different elements a ∈ Z10 , but one thing is
common, as one keeps multiplying by a, sooner or later a duplicate appears,
establishing a pattern, and that pattern must continue forever.
So if we want to compute 888888 in Z10 , we reduce the base, not the expo-
nent, and compute instead 8888 . Then, since the powers of 8 repeat every four,
we use the fact that 888 ≡ 4 mod 4, and use 8888 = 84 ≡ 6 mod 10. Of course
666666 ≡ 6 mod 10, since the powers of 6 never seem to get off the ground
modulo 10.
Notice in the table above that the exponentials modulo 10 all return to their
starting values in the a 9 column. It would be nice if that type of thing happened
generally, but exponentials can be stranger still. Here is the table for Z8 .
Z8 a1 a2 a3 a4 a5 a6 a7 a8 ···
0 0 0 0 0 0 0 0 0 ···
1 1 1 1 1 1 1 1 1 ···
2 2 4 0 0 0 0 0 0 ···
3 3 1 3 1 3 1 3 1 ···
4 4 0 0 0 0 0 0 0 ···
5 5 1 5 1 5 1 5 1 ···
6 6 4 0 0 0 0 0 0 ···
7 7 1 7 1 7 1 7 1 ···
in which we see the powers of 6 just drop to 0 and where, of course, they must
stay forever, and the sequence never returns to 6.
You see more regular behavior if the base a is coprime to the modulus, so
the base has a multiplicative inverse modulo n. For such a base, we see in both
Z10 and Z8 that the sequence of powers passes through a sequence of distinct
values until it reaches 1, and then the sequence repeats forever. This is always
true.
Exercises
1. Compute 10200 modulo 11.
2. a) Compute the first 12 powers of 2 modulo 12. Use what you discover to
compute 21776 modulo 12.
b) Compute the first 17 powers of 2 modulo 17. Use what you discover to
compute 21776 modulo 17.
3. Compute 21776 modulo 33.
Even the tricky exponents are better behaved if the modulus is prime. In
Z11 , since every non-zero element has a multiplicative inverse, we have from
Theorem 8.2 that the list of powers of every non-zero element will have a 1
before a 11 . Check that in the table below.
a a0 a1 a2 a3 a4 a5 a6 a7 a8 a 9 a 10 a 11
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 2 4 8 5 10 9 7 3 6 1 2
3 1 3 9 5 4 1 3 9 5 4 1 3
4 1 4 5 9 3 1 4 5 9 3 1 4
5 1 5 3 4 9 1 5 3 4 9 1 5
6 1 6 3 7 9 10 5 8 4 2 1 6
7 1 7 5 2 3 10 4 6 9 8 1 7
8 1 8 9 6 4 10 3 2 5 7 1 8
9 1 9 4 3 5 1 9 4 3 5 1 9
10 1 10 1 10 1 10 1 10 1 10 1 10
One thing which is striking about this table is the column of 1’s precisely at a 10 .
We see the same phenomenon in the table of exponents modulo the prime 13.
a a0 a1 a2 a3 a4 a5 a6 a7 a8 a 9 a 10 a 11 a 12 ...
0 0 0 0 0 0 0 0 0 0 0 0 0 ...
1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 2 4 8 3 6 12 11 9 5 10 7 1
3 1 3 9 1 3 9 1 3 9 1 3 9 1
4 1 4 3 12 9 10 1 4 3 12 9 10 1
5 1 5 12 8 1 5 12 8 1 5 12 8 1
6 1 6 10 8 9 2 12 7 3 5 4 11 1
7 1 7 10 5 9 11 12 6 3 8 4 2 1
8 1 8 12 5 1 8 12 5 1 8 12 5 1
9 1 9 3 1 9 3 1 9 3 1 9 3 1
10 1 10 9 12 3 4 1 10 9 12 3 4 1
11 1 11 4 5 3 6 1 11 4 5 3 6 1
12 1 12 1 12 1 12 1 12 1 12 1 12 1
You see some occurrences of 1 scattered about earlier, but always in the column
for a 12 for every element except 0.
This behavior of exponentials for prime modulus was noticed for centuries.
The mathematician Fermat was able to prove the general statement. The result
has come to be called his “little theorem”, and sometimes his “little lemma”,
that is, his little minor result.
Theorem 8.3 (Fermat’s Little Theorem). For p a prime, a p−1 ≡ 1 mod p for
every non-zero element a ∈ Zp .
Some people prefer to word it this way,
Theorem 8.4 (Fermat’s Little Theorem). For p a prime and for all a ∈ Zp ,
a p ≡ a mod p.
Example 8.5. What is 512303 mod 101?
The base we can reduce immediately. 512303 ≡ 7303 mod 101, but do not reduce
the exponent to 0 because 303 ≡ 0 mod 101. Instead, note that 101 is prime and
so 7100 ≡ 1 mod 101. Thus 7303 ≡ 7300 · 73 ≡ (7100 )3 · 73 ≡ 73 mod 101.
You may balk at 73 , but you have to admit that it is a lot better than 512303 ,
you might find it faster to compute 73 = 343 ≡ 40 mod 101 with pencil and
paper than to punch the problem into a computer. ♦
You may wonder, what is Fermat’s “Big Theorem”? Most people think it
was his “Last Theorem”, which was so big that its proof was too large to pencil
into the margin of Fermat’s notebook. The full written up proof had to wait for
centuries of effort by many famous mathematicians, and was only finished rela-
tively recently. It is Theorem 7.21 in Section 7.8, the case study on Pythagorean
Triples. After all that work, now that we know that Fermat’s Last Super Gigantic
Theorem is true, what is the consequence? Well, not much – so far it is mostly
just a cute story. But Fermat’s Little Lemma? That is much more important. It
is hugely consequential in coding theory and cryptography, as we will see soon.
Exercises
1. In the previous exercise set we found that 102n ≡ 1 mod 11. Is that consistent
with Fermat’s Little Theorem?
2. Make a table of all the powers in Z7 , and show it is consistent with Fermat’s
Little Theorem.
3. a) Compute 71252 mod 13.
b) Compute 21710 modulo 101.
and you might have heard the artful dodgers of the day whispering Ixnay, Op-
perscay, Amscray!
Mathematicians and computer scientists do not use the word ‘code’ in this
way. Mathematically a code is just a way of cataloging information for process-
ing, like Morse code for letters, or the Gray code for bit vectors, or bit vectors
for subsets, or the Prüfer code for labeled trees. Basically, a code is just a one-
to-one and onto function from a set to a code set. If secrecy is needed, then the
code is called a cypher, and the data is said to be encrypted.
The hobo markings, Cockney rhyming slang, and pig Latin are not very se-
cure as cyphers. Over time their meaning is discovered. But, since such cyphers
require effort to devise and learn, they are hard to change.
Example 8.6. Caesar’s Cypher was used by Julius Caesar in his wars with
the Gauls. In the language of modular arithmetic it may be described as follows.
Start with an encoding of the letters of the alphabet A into Z26 . Simply assigning
a to 0, b to 1, etc., is fine since the encryption comes later. Once encoded, the
message, M, which started out as a string on the alphabet A, has been encoded
as string of elements of Z26 .
Now pick an encoding key, , to be kept secret from the enemy, and encrypt
the coded message by adding to each element of Z26 in the message. The
resulting encrypted message M is also a string in Z26 . M can be decoded back
into a string of A. That will probably be a string of unreadable text which can
be sent by courier without fear of it being intercepted and read by the enemy.
When the encrypted message is received, it is re-encoded to M , and the
decrypting key, δ = 26 − is applied to each element of Z26 in the string to
recover M, which is then decoded to yield the original text.
The message happy birthday with encoding key = 5 would be sent as the
encrypted string mfuud gnwymifd. ♦
The reason Caesar’s Cypher was so successful is the existence of the keys.
There are 26! permutations of A, that is, 26! one-to-one and onto functions
A → A, most of which could work very well as an encryption function. But
how are such functions to be communicated and used efficiently? The mere 26
different functions associated to the encoding and decoding keys make the code
description fast, make encoding/decoding efficient, and can be changed with
little trouble.
Using number theory, we can create more complex systems with the same
flavor as Caesar’s Cypher.
Example 8.7. A Multiplicative Cypher has a different encryption step than
Caesar’s cypher. The permutation of Z26 is accomplished by the function
f : Z26 → Z26 defined by f (n) = n · . There is still an encryption key, but
it is applied multiplicatively.
There is also a decryption key, δ, which is the multiplicative inverse of in
Z26 , and the decryption function is g(n) = n · δ, and that works since g(f (n)) =
(n · ) · δ = n(δ) ≡ n mod 26.
For Caesar’s additive cypher, any of the elements of Z26 can be used as
an encryption key, since each element in Z26 has an additive inverse. For the
multiplicative cypher, not every element has a multiplicative inverse. Using =
10 will not work in Z26 since gcd(10, 26) = 2 = 1. But there are many pairs
which do work, = 3 and δ = 9, for instance. ♦
One way to get more keys is to expand the alphabet set so that it has prime
cardinality. If we add five punctuation marks to the alphabet, say [.,:;?], then
we can work instead in the prime modulus 31. That is what we will do for our
third example.
Which of these three is the best, the additive (Caesar’s) cypher, or the mul-
tiplicative, or the exponential versions? Unfortunately, they are all three more
or less equally bad. The first problem is – there are too few keys. There are so
few keys that the enemy, more sophisticated than the ‘barbarians’ Caesar was
faced with, can simply try them all. Even if we abandon keys and the modular
arithmetic approach and use one of the 26! other possible codes, the result is still
insecure since, as Sherlock Holmes describes in “The Adventure of the Dancing
Men”, any letter code can be easily broken noting that different letters occur
differently often – the frequency attack.
In order for any version to be credible, the text message must be broken into
much larger blocks, not individual letters but hundreds of characters per block,
so that one is working not in Z31 but in ZN where the modulus N has hundreds,
or even thousands of bits in its binary representation. That is the absolute bare
minimum for this type of encryption.
In the examples and exercises of this and the next section, all the primes
are chosen to be very small, but the method is meant to be applied using large
primes, essentially as large as one can handle.
Exercises
1. Encode “WPI” in Z26 and encrypt it additively with key = 7, and multi-
plicatively with key = 7.
Find the decoding keys, δ for each, and check that they work.
2. For the 11 letter alphabet {a, b, c, d, e, g, h, i, j, k, l} encode “da” and en-
crypt it exponentially with key = 7. Find the decoding key, δ, and check
that it works.
3. Find all values in Z11 which do not work as exponential encoding keys.
Find all values in Z11 which do not work as multiplicative encoding keys.
Find all values in Z11 which do not work as additive encoding keys.
q he must factor N into prime factors. If Alice was clever enough to pick large
enough primes p and q, the task of factoring will be too difficult for the attacker.
Example 8.9. Here is a toy example to illustrate what the issues are. Suppose
Alice has chosen p = 11, q = 7, with = 13 and δ = 37.
Bob has been given the encoding key 13, has been told the modulus, 77, and
he wants to send the secret message (10, 20, 30). He computes x = 1013 mod
77, y = 2013 mod 77, z = 3013 mod 77 and sends (x, y, z) to Alice.
The attacker hears (x, y, z) and knows about 77 and 13. In this tiny toy exam-
ple, the attacker factors 77 = 7·11 and concludes that he needs the multiplicative
inverse of 13 modulo (7 − 1)(11 − 1) = 60. That is done with the Extended Eu-
clidean Algorithm, starting with division with remainder on 60:
Exercises
1. Suppose we have an RSA Scheme with primes p = 13 and q = 17. Suppose
the encoding key is = 5. What is the decoding key δ?
2. In the scheme above, encode (010, 020, 030).
3. Suppose we have an RSA scheme based on 303. Suppose Alice has encoding
key 67. What is Bob’s decoding key?
Alice could be able to pick a b for which her cost was reasonable, but Vladimir’s
cost was prohibitive. In the situation above, we say Ca (b) = o(Cv (b)) in the
little-o notation.
The o notation is widely used although the notation is eccentric for many
reasons. In the expression o(g(n)), o is not a function, even though it is written
like one, and o(g(n)) has no value, so when you see f (n) = o(g(n)) it does
not mean that the value of f (n) is equal to the value of o(g(n)). It is easy to
check that n2 = o(n3 ) and 3n2 + 5 = o(n3 ) but of course n2 = 3n2 + 5, and
even n2 = o(3n2 + 5).
Instead, the o notation defines a relation on functions which is not reflexive,
not symmetric, but is transitive, since f (n) = o(g(n)) and g(n) = o(h(n)) im-
plies f (n) = o(h(n)), as is easy to check. If f (n) = o(g(n)) then it means that,
as n gets large, not only is f (n) eventually smaller than g(n), but it is even-
tually smaller than (1/2)g(n), (1/4)g(n), (1/8)g(n), eventually smaller than
(1/2n )g(n) for any n. So f (n) is vanishingly small relative to g(n) as n grows.
In the language of limits
f (n)
lim = 0 ⇒ f (n) = o(g(n))
n→∞ g(n)
an2 + bn + c 1 1 1
lim 3
= lim a + b 2 + c 3 = 0
n→∞ n n→∞ n n n
if you like limits, otherwise you have to do more algebra. ♦
Exercises
1. Suppose we want to compute gcd(5280, 1117) in 100 steps. Is that possible?
What about 10 steps?
2. Show that 500n5 + 1000n3 = o(n6 ).
3. Show that 2n + 3n = o(5n ).
√
if Vladimir uses ancient sieve and factors with n = 2b divisions, the little-o
comparison gives 2b = o(22b − 2 · 2b + 1), and Vladimir wins by a lot.
We saw before that, in modular arithmetic, exponentiation must be handled
specially. Reducing the exponent using Fermat’s Little Theorem will not help
us because the exponents are already reduced.
Fortunately, there is an algorithm which saves RSA. This is the idea. Suppose
you wanted to compute
71776 mod 2027.
That is 1776 − 1 multiplications, but 1776 = 2 · 888. If you write 71776 =
(72·888 ) = (7888 )2 , that calls for only 888 multiplications, 887 for the inside
exponent and just one for the square at the end. If you apply the trick a second
time, you have 71776 = 72·888 = (7888 )2 = ((7444 )2 )2 there are only 445 multi-
plications.
That is fine for even exponents, but what if it is odd? 71783 = 7 · 71782 =
7 · 72·891 = 7 · 72 · (7890 )2 = 7 · 72 · ((7445 )2 )2 with 449 multiplications, still
fantastic savings – and we can continue to get more. Using these hints, you
might be able to write up the multiplication saving algorithm on your own.
Exercises
1. Suppose we want to compute 1776666 . Naively we need 665 multiplications
of 1776.
How many are required by fast exponentiation?
Give an algebraic expression that illustrates how this is to be done.
Do not compute the result.
2. Use fast exponentiation to compute 722 mod 100.
3. We know from little Fermat, that 2100 ≡ 1 mod 101. Verify this with fast
exponentiation.
a a
Define a relation ≈ on X by setting x ≈ y if y ≡ xa j for some j ∈ Z.
a
The relation ≈ is reflexive since, for all x ∈ X we have x ≡ xa k .
a a
The relation ≈ is symmetric: Let x, y ∈ X, with x ≈ y. So y ≡ xa j and,
multiplying both sides by a k−j we have ya k−j ≡ xa j a k−j ≡ xa k ≡ x, which
a
says y ≈ x.
a a a
The relation ≈ is transitive: Let x, y, z ∈ X, with x ≈ y, and y ≈ z. So y ≡
a
xa i and z ≡ ya j . Substituting z ≡ (xa i )a j ≡ x(a i a j ) ≡ x(a i+j ) and x ≈ z.
a
Since ≈ is reflexive, symmetric, and transitive, it is an equivalence relation
and, as always, we are interested in the equivalence classes.
a
Let E be an equivalence class of the relation ≈ and let b ∈ E. Define a func-
tion f : {1, 2, . . . , k} → E by setting f (i) = ba i . The function is well defined
since each element ba i is equivalent to b.
The function f is onto. Every element e ∈ E is equivalent to b, and so of the
form ba i for some i, and since the powers of a i repeat after k by Theorem 8.2,
we can assume i ≤ k, so f (i) = e.
The function f is one-to-one. Let i, j ∈ {1, 2, . . . , k} be given and suppose
f (i) = f (j ). Then ba i ≡ ba j . Since b ∈ X, the element b has multiplicative
inverse c, with cb ≡ 1. So cba i ≡ cba j , and a i ≡ a j . By Theorem 8.2, i = j
and the function f is one-to-one.
a
Since f is one-to-one and onto, |E| = k. So every equivalence class of ≈
has cardinality k. If there are m equivalence classes, then |X| = km. Thus
What does this mean if n = p is prime? In that case every non-zero element
in Zp has a multiplicative inverse, and |X| = p − 1. Thus a p−1 ≡ 1 mod p,
establishing Fermat’s Little Theorem.
FIGURE 8.1 a) A symmetric relation on 10 letters, a “tree”. b) The relation after four removals.
a b a r
To encode r, since r does not occur in ◦ ◦, we subdivide to form ◦ ◦
b
◦. You can check that Algorithm 8.15 encodes this as r, and the end nodes
a and b are smaller than all the unused letters, as required.
To encode er, since e does not occur in the tree for r, we subdivide the edge
a r e b
to end node b with the node labeled e to form ◦ ◦ ◦ ◦. The algorithm
encodes this as er, and the end nodes are still a and b.
To encode eer, we must change strategy since e already labels a node in
the diagram. In that case, we take the smallest unused letter, in this case c, and
attach it to the node labeled e. Since c is larger than a and b, it will be the first
node removed under the algorithm, recording e, then continuing as before to
eer. The end nodes are now labeled a, b, and c, each satisfying the smallness
requirement.
The same thing must be done continuing to beer, since the letter b is also
already in the diagram. The end nodes will then be labeled a, c, and d.
So we continue. The steps are illustrated in Fig. 8.2.
FIGURE 8.2 Intermediate trees: beer, ebeer, eebeer, reebeer, and f reebeer.
If you want to try a harder one, try “Danger ahead, go back!” on the alphabet
of letters from a to s.
d a k c b o g e
You should have ◦ ◦ ◦ ◦ ◦ ◦ ◦ ◦ when you get to
“go back”, after 4 subdivision and 2 additional moves. The final answer is in
Fig. 8.3.
FIGURE 8.3 The Prüfer decoded relation tree for “Danger Ahead, Go Back!”
i 1 2 3 4 5 6 7 8
ψ(ei ) {1,2} {1} {2,3} {2,4} {4,5} {3,6} {1,4} {2,4}
Then G = (V , E, ψ) is a graph. ♦
Note that graphs are discrete, not geometric objects. However, if the graph
does not have too many vertices and edges, it can be conveniently represented
with a diagram of dots and lines connecting them. See Fig. 9.1a for an example
of such a representation of the graph from Example 9.1.
FIGURE 9.1 A graph (a) and a simple graph (b) on the same vertex set.
is an equivalence relation, and hence its equivalence classes partition the vertex
set of the graph. A graph is said to be connected if the connectedness relation
has only one equivalence class, that is, if any two vertices are connected by a
path. See Fig. 9.2. The connected components of a graph G are its maximal
connected subgraphs. Note that the vertices of a connected component of G =
(V , E) always comprise an equivalence class of V under .
Given a positive integer n, the complete graph of order n is the simple graph
Kn with exactly n vertices, any two of which are adjacent. Every finite simple
graph can be regarded as the subgraph of a complete graph. Given two positive
integers m and n, the complete bipartite graph Km,n is a graph with vertex
set V = B ∪ W , with |B| = m, |W | = n, B ∩ W = ∅, and E = {{b, w} | b ∈
B, w ∈ W }. You should think of the vertices in B as colored black, and those in
W as colored white. The subgraphs of the complete bipartite graph are called
bipartite, or 2-colorable. One of the graphs of Fig. 9.2 is bipartite.
Exercises
1. How many edges can a simple graph on 5 vertices have? How many edges
can a simple graph on n vertices have? What about a general graph on n
vertices?
2. Consider the graph G(V , E, ψ) of Example 9.1. Let V = {1, 3, 6} and E =
{e6 }. Specify ψ such that G(V , E , ψ ) is a subgraph of G. Draw G . How
many connected components does G have?
3. Consider the graph G(V , E, ψ) of Example 9.1. Let V = {1, 3, 6} and E =
{e1 }. Can you specify ψ such that G(V , E , ψ ) is a subgraph of G? Justify
your answer!
9.2 Trees
We have already encountered trees as reduced diagrams of certain special sym-
metric relations when discussing the Prüfer code in Section 8.8. We now give
a characterization of trees and discuss their importance in a practical scenario
arising in network design.
Spanning trees
In Section 8.8 we learned about the Prüfer code, a way to encode any tree relat-
ing k + 2 objects with an output string of length k. Since any string of this type
can be realized this way and also uniquely decoded, this yields a one-to-one and
onto functional relation between the set Tk+2 of all trees relating a given set of
k + 2 objects and the set Sk of all strings of length k over an alphabet of size
k + 2. By the multiplicative principle, the number of such strings is (k + 2)k . We
therefore have |Tk+2 | = |Sk | = (k + 2)k . Writing n for k + 2 and considering
the special case n = 1 separately, we obtain the following result, also known as
Cayley’s formula.
Theorem 9.4. For every positive integer n, the number of trees with a given set
of n vertices is nn−2 .
A spanning tree in a graph G is any spanning subgraph of G that is a tree.
Thus, Cayley’s formula can be equivalently phrased as follows: For every posi-
tive integer n, the complete graph Kn with a given set of n vertices has exactly
nn−2 spanning trees. The sequence of numbers nn−2 grows very fast. Its first ten
terms are 1, 1, 3, 16, 125, 1296, 16807, 262144, 4782969, and 100000000; in
particular, there are 108 trees with 10 vertices.
Cayley’s formula was discovered in the late 19th century, approximately
around the time when the car was invented. Clearly, cars could only become
widely popular after the cities and villages around the world became sufficiently
well connected by road networks. This brings us to problems such as the follow-
ing one. In a rural area there are 20 villages. We would like to connect them by
roads. The distance between any two villages is known, and the area is geo-
graphically sufficiently simple that the cost of building a direct road connection
between two villages is proportional to the distance between them. What is the
cheapest way of connecting all the 20 villages?
We can represent the desired road network with a connected graph whose
vertices are the 20 villages, an edge joining two villages A and B means that
there will be a direct road connection between A and B, and the cost of such an
edge will be given by the distance between A and B. Our goal is to construct
a graph of this type such that the total sum of the costs of the edges will be as
small as possible.
Can such a graph have a cycle? If it did, then one of the edges in a cycle
could be removed from the graph, without losing connectivity, but resulting in
a decrease in the total cost of the road network. We are therefore looking for
an acyclic connected graph, that is, a tree, connecting the given villages and of
smallest total edge cost. Such a tree is called a minimum spanning tree, and the
problem is known as the Minimum Spanning Tree problem.
Is this a difficult problem? According to Cayley’s formula, we are looking for
an optimal tree out of 2018 trees. This looks hopeless. However, in the 1920’s–
1950’s, several efficient methods for solving this problem were developed that
avoid an explicit enumeration of all possible trees. Here is a particularly simple
one.
Algorithm 9.5 (Kruskal’s algorithm). We are given a set V of vertices and
a non-negative cost function c({i, j }) on all possible edges {i, j } joining two
vertices in V .
Sort the edge costs from the smallest to the largest and set F = ∅.
Keep adding to F one edge at a time until the graph (V , F ) becomes con-
nected. At every step, add to F a cheapest edge whose endpoints are not yet
connected by a path consisting of edges from F .
Return (V , F ). ♥
Theorem 9.6. Kruskal’s algorithm correctly computes a minimum spanning
tree.
Example 9.7. Consider a set of five villages {a, b, c, d, e} and the following
distances between them:
edge {b, d}, which means that b and c are not yet connected by a path consisting
only of edges chosen so far. The next edge considered for addition is the edge
{c, d}, of cost 9. However, since its endpoints c and d are already connected to
each other via the vertex b using only of edges in F , the edge {c, d} is not added
to F . The next edge considered for addition is the edge {a, c}, of cost 10. This
edge is added. The next edge considered for addition, {a, b}, is not added, and
neither is {a, d}. The last edge added is the edge {c, e}, at which point the tree
in Fig. 9.6 is computed. As the graph is connected, no further edges are added.
The total cost of the road network is 7 + 8 + 10 + 13 = 38. ♦
FIGURE 9.6 The cheapest way to connect five villages by roads using Kruskal’s algorithm.
Since any connected graph admits a spanning tree, Kruskal’s algorithm can
be applied to any connected graph equipped with a weight function on the
edges.
Exercises
1. Given a set S of positive integers, let us denote by RS the symmetric relation
on the set S in which two elements a, b ∈ S are related if and only if one
of them divides the other one and their quotient is prime. For example, if
S = {2, 3, 6, 8}, then there are only two pairs of elements in relation, namely
{2, 6} and {3, 6}; two distinct elements may be unrelated for two reasons:
either none of them divides the other (for example, 2 and 3) or their quotient
is not prime (for example, 8 and 2).
Decide for which of the following sets Si the reduced diagram Gi of the
symmetric relation RSi is a tree.
(a) S1 = {1, 2, 3, . . . , 9},
(b) S2 = {2, 3, 4, . . . , 9},
(c) S3 = {1, 2, 3, 5, 6, 7, 8, 9},
(d) S4 = {1, 2, 3, 5, 6, 7, 8, 9, 10},
(e) S5 = {1, 2, 3, 5, 6, 7, 8, 27},
(f) S6 = {1, 2, 3, 4, 5, 7, 8, 9}.
2. In a vast remote land, there are four tiny villages a, b, c, d, with 15, 16,
18, and 20 inhabitants, respectively. These villages have a peculiar property
that the distance in miles between any two of them equals the product of
their numbers of inhabitants. Solve the Minimum Spanning Tree problem
for these four villages.
3. Draw all trees with vertex set {a, b, c, d}.
Searching
When working with a large graph, we usually do not have a convenient drawing
of the graph available; all we know is the set of its vertices and the set of its
edges, along with their endpoints. Equivalently, the graph can be represented
with adjacency lists, that is, a list of its vertices and, for each vertex v, a list of
edges having v as an endpoint along with the other endpoint of the correspond-
ing edge. When the graph is simple (it has no loops and no multiple edges),
this information for a vertex v can be represented simply with a list of vertices
adjacent to v.
Example 9.8. In Fig. 9.7 we show a simple graph with vertex set {a, b, c, . . . , r}
and an adjacency list representation of the graph. ♦
FIGURE 9.7 A simple graph and its adjacency list representation (in two parts).
It is often useful if we are able to systematically search the graph, that is,
examine all the vertices of a graph in such a way that, whenever possible, each
newly visited vertex is adjacent to at least one of the already visited vertices.
There are two basic ways in which this can be achieved efficiently, both us-
ing trees: the so-called breadth-first search (BFS) and depth-first search (DFS).
What these two graph searches have in common is that they both start at some
vertex s in a given graph G and compute a tree T with the following properties:
• The vertices of T are exactly the vertices v such that there exists a path from
s to v in G.
• Every edge in T is an edge in G.
However, as the names suggest, these two graph searches differ in one important
aspect:
• In BFS, the graph (or, more precisely, the connected component of the graph
containing the starting vertex s) is explored “in breadth”, meaning that upon
reaching some vertex v, we first visit all of its yet unvisited neighbors before
visiting the neighbors of the neighbors of v. This results in the vertices being
examined in order of their distance from the starting vertex s.
• In DFS, the connected component of the graph containing s is explored “in
depth”, meaning that upon reaching some vertex v, we first visit one of its
neighbors and then proceed recursively on that neighbor, before moving on
to another neighbor of v.
The resulting trees are called a BFS tree and a DFS tree of G, respectively.
Example 9.9 (continued). Let us run the two searches on the graph from Fig. 9.7
from the vertex a. The algorithms are not completely specified, in the sense that
we may have some freedom when choosing the next yet unvisited neighbor of
the currently visited vertex. So, in principle, even for the same starting vertex,
there may be many possible outcomes – many possible BFS and DFS trees. For
this particular example, let us agree that we will break any such ties by always
choosing the alphabetically smallest yet unvisited neighbor of the current vertex.
Using this rule, can you compute the corresponding BFS and DFS trees?
FIGURE 9.8 A BFS tree (left) and a DFS tree (right) of the same graph. The numbers in paren-
theses denote the ordering of the vertices in which they were visited by the search.
BFS and DFS graph traversals have many applications. Breadth-first search
is used for computing shortest paths, for computing the connected components
of a graph, and as a subroutine in various more complicated algorithms on
graphs, the discussion on which is beyond the scope of this textbook. Depth-first
search is useful for computing the connected components of a graph, testing if
a graph is planar (see Section 9.4), searching for cycles, determining if a graph
remains connected upon deleting at most any one vertex or any set of at most
two vertices, etc.
Sorting
As you know, any two integer numbers (and, more generally, any two real num-
bers) a and b are comparable with respect to the “less than or equal” relation: it
Example 9.10. Consider the following list of 13 integers: 3, 19, 6, 8, 12, 11,
10, 22, 4, 1, 7, 9, 18. The list is broken into smaller and smaller lists, until we
obtain lists of size 1, which are trivial to sort, see Fig. 9.9. ♦
Let us now explain how to combine two sorted lists into a single sorted list.
Suppose that we have two sorted lists of integers, b1 , . . . , bk and c1 , . . . , c . We
create a new list L which is initially empty but will eventually become a single
sorted list combining the two given sorted lists. We introduce a pair of indices i
and j , each responsible for traversing one of the two initial lists. We traverse the
two lists in parallel, always keeping track of the next element for each list that is
the candidate for extending the current partially built list L. We initialize i = 1
and j = 1. If we have not yet exhausted any of the two lists, that is, if i ≤ k and
j ≤ , then we compare the current elements bi and cj . If bi ≤ cj , we append bi
at the end of L and increase i by 1. Otherwise, we append cj at the end of L and
increase j by 1. Sooner or later one of the two original lists will be completely
traversed, at which point we add the remaining elements of the other list at the
end of L. More precisely, if i ≤ k and j > , we append bi at the end of L and
increase i by 1, and if i > k and j ≤ , we append cj at the end of L and increase
j by 1. The algorithm stops when i > k and j > , at which point L is a sorted
list of integers that appeared in the combined list b1 , . . . , bk , c1 , . . . , c . Since at
every step exactly one of the indices i and j is increased by one, we conclude
that the total number of comparisons performed is bounded by the sum k + of
the lengths of the two lists.
Example 9.11. Consider the following two lists: (b1 , . . . , b7 ) = (3, 6, 8, 10,
11, 12, 19) and (c1 , . . . , c6 ) = (1, 4, 7, 9, 18, 22). The steps of the merging al-
gorithm are as follows:
• Initialization: L = (), i = j = 1.
• c1 = 1 < b1 = 3, we append c1 at the end of L to obtain L = (c1 ) = (1); we
increase the value of j to 2.
• b1 = 3 ≤ c2 = 4, we append b1 at the end of L to obtain L = (1, 3); we
increase the value of i to 2.
• The next values appended at the end of L are, in order: c2 = 4, b2 = 6, c3 = 7,
b3 = 8, c4 = 9, b4 = 10, b5 = 11, b6 = 12, c5 = 18, and b7 = 19.
• At this point we have i = 8, meaning that we have used up all the elements
from the first list. We append the remaining elements from the other list (in
this case only one, c6 = 22) at the end of L, to obtain final the merged list
L = (1, 3, 4, 6, 7, 8, 9, 10, 11, 12, 18, 19, 22). ♦
Now that we have explained how to merge two sorted lists, the algorithm
is clear: we traverse the tree that we constructed in the first step, when break-
ing down the problem to simpler subproblems, in the opposite direction, from
smaller to larger problems. At each step, we merge two sorted lists using the
procedure we described above. Once the procedure is finished, we will have
sorted the initial list.
How many comparisons do we need in the worst case? If we denote by T (n)
the number of comparisons needed in the worst case by the merge sort procedure
when sorting a list of n integers, then the following holds: T (1) = 0 and for all
n > 1, we have T (n) ≤ T ( n/2 ) + T (n/2) + n. Using induction on k, it can
be shown that for all k ≥ 0, we have T (2k ) ≤ k · 2k (see Exercise 2 at the end
of the section). Thus, if we denote by k the smallest integer such that n ≤ 2k ,
then 2k−1 < n, or equivalently k < log n + 1 and 2k < 2n, and we infer that
T (n) ≤ T (2k ) ≤ k · 2k < 2n · (log n + 1). This implies the following:
Theorem 9.12. The merge sort algorithm sorts a list of n positive integers with
fewer than 2n · (log n + 1) comparisons.
This is much better than n(n − 1)/2 comparisons. For example, for n = 100,
we have at most 1528 comparisons instead of at most 4950, but the larger the
value of n, the more dramatic the difference; in fact 2n · (log n + 1) = o(n(n −
1)/2).
Let us also note that the above theorem holds in a much more general setting,
namely for sorting objects from any set S equipped with a partial order such
that any two objects a, b ∈ S are comparable (that is, at least one of a b or
b a holds).
In conclusion, we return to our working example, Example 9.10.
Example 9.13 (continued). We now traverse the tree from Fig. 9.9 bottom up
and at every step merge two sorted lists into a larger sorted list. See Fig. 9.10.
FIGURE 9.10 Merging the sorted lists iteratively from bottom to top.
As you have probably noticed, the last merging is the one from Exam-
ple 9.11. ♦
Exercises
1. Sort the following list of integers using merge sort:
12, 22, 53, 17, 4, 9, 17, 99, 0, 8, 11, 20, 7, 18, 33, 21, 24, 5, 28, 42 .
9.4 Planarity
In Section 9.2, we learned how to connect a given set of geographical locations
(for example, cities or villages) by roads in a cheapest possible way. In reality,
once the roads are built, the network typically contains many more roads than
predicted by a solution to the Minimum Spanning Tree problem. This is because
we want the network not only to be connected but to allow for overall fast travel
times between different cities. On a more local scale, a similar phenomenon
occurs also in networks of streets within a city.
Imagine a situation where we have five important cities that we would like to
pairwise connect withdirect
road connections. While we are prepared to build
all the corresponding 52 = 10 roads, we would like to do so without incurring
additional expenses and risks related to building bridges or tunnels. Can this be
achieved?
If you try to solve this puzzle with paper and pencil, you will quickly realize
that it is not possible to achieve the desired design of roads; at least one pair
of cities must remain unconnected if bridges and tunnels are to be avoided. See
Fig. 9.11 for an example, where, with the other roads in place, Zurich and Bled
cannot be connected by a direct road, even if the last road were not required to
be straight.
A similar situation can occur even without requiring all possible pairs of
cities to be connected. A classical mathematical puzzle known as the three util-
ities problem or sometimes water, gas, and electricity asks for non-crossing
connections to be drawn between three houses and three utility companies. (Try
it! You can place the house and companies wherever you like in the plane.)
The graph in Fig. 9.11 is planar, which means that it can be drawn in the
plane without edge crossings. The complete graph K5 and the complete bipartite
graph K3,3 are both non-planar, there is no way to draw them in the plane even
with curved edges!
When we draw a graph we represent the vertices by dots and the edges by
curves.
In Fig. 9.12 we see a planar graph and several drawings of it, the leftmost
drawing has crossing edges.
FIGURE 9.12 Drawings of the cube graph with crossing edges and without.
Cutting along the edges of a non-crossing drawing divides the plane into
different regions which we call faces. We can describe the face set F by closed
walks in the graph by imagining walking on a face close to the cuts. The triple
G = (V , E, F ) is called a plane graph.
In Fig. 9.13 we indicate the faces by shadings. The inside white face is
described by the walk A, (A, b), b, (b, D), D, (D, c), c, (c, A), A. The outside
white face is described by the walk d, (d, C), C, (C, a), a, (a, B), (B, d), d.
Note that all these walks are actually cycles.
FIGURE 9.13 A drawing of the cube graph dividing the plane into 6 faces.
It seems intuitive that a simple graph with many edges, such as a complete
graph on n ≥ 5 vertices, will be impossible to draw without edge crossings.
To obtain a bound on the maximal number of edges in terms of the number of
vertices of a simple planar graph, we might ask the following question. How
many edges does a connected plane graph G on n vertices have if all faces are
triangles (i.e., cycles of length 3)?
FIGURE 9.16 Two plane graphs G1 and G2 corresponding to the same planar graph.
To understand why these two drawings are not considered equivalent to each
other, look at the faces. The graph G1 has for example a face which is a 3-cycle,
while G2 does not. This example also shows that the dual of a simple plane
graph need not be simple.
If we have a connected plane graph and apply the dual operation twice, we
get back to the same graph.
Interestingly, as shown by the Swiss mathematician Leonhard Euler, while
a planar graph may have many non-equivalent planar drawings, the number of
faces in any such embedding is always the same; in fact, it depends only on the
number of vertices and edges of the graph.
Theorem 9.14 (Euler’s formula). Let G be a connected plane graph and denote
by n the number of vertices, by e the number of edges, and by f the number of
faces of G. Then n − e + f = 2.
Proof sketch. Consider a spanning tree T of G. If T = G, then Euler’s formula
holds as in this case e = n − 1 and f = 1. Consider the edges not in T in some
order {e1 , e2 , . . .}. Cutting along e1 cuts the face created by T into two pieces,
an interior piece, and an exterior one. Since we started with a plane graph G, e2
is completely contained in one of the faces we have created so far, hence cuts
one of the given faces into two pieces. We therefore create e − (n − 1) + 1 = f
faces.
Our proof of Euler’s formula is an induction proof, namely induction on e.
It also provides, using the two-out-of-three theorem, a remarkable property of
plane graphs: There are f − 1 edges not in T , they correspond to f − 1 edges
separating two faces – or connecting two vertices of the dual graph, so they
are the edges of a spanning tree (by count and connectivity) of the dual graph.
A pair of complementary trees for the plane graphs of Fig. 9.16 is highlighted
in Fig. 9.17.
Using Euler’s formula, we can now re-derive, as a check, our upper bound on
the number of edges in a simple planar graph with a given number of vertices.
The bound can be further improved if G is triangle-free, that is, it does not
contain any three pairwise adjacent vertices.
Theorem 9.15. Let G be a simple planar graph with exactly n ≥ 3 vertices and
e edges. Then e ≤ 3n − 6. Furthermore, if G is triangle-free, then e ≤ 2n − 4.
Proof. Assume first that G is connected. Fix an arbitrary planar embedding of
G and let us denote by f the number of faces. For a face F , the length of F is
the number of edges in the walk bounding the face (counted with multiplicities).
For example, the graph G1 in Fig. 9.16 has faces of four different lengths, 3, 4, 5,
and 6. Let us denote by S the sum of the lengths of the faces. Since n ≥ 3 and G
is simple, each face has length at least three. Thus S ≥ 3f . On the other hand,
since each edge appears on the boundary of exactly two faces (or it appears
twice on the boundary of a single face), each edge contributes exactly 2 to the
sum S, which implies that S = 2e. By Theorem 9.14, we have that e − n + 2 = f .
Multiplying by 3, we obtain 3e −3n+6 = 3f ≥ S = 2e, from which the claimed
inequality e ≤ 3n − 6 follows. If G is triangle-free, then S ≥ 4f and hence
4e − 4n + 8 = 4f ≤ S = 2e, implying e ≤ 2n − 4.
If G is not connected, then we can add edges to it to obtain a simple con-
nected planar graph G (which can be made triangle-free if G is triangle-free).
The two inequalities for G will imply the desired conclusion for G, too.
By Theorem 9.15, every simple planar graph with 5 vertices has at most
9 edges. Since the complete graph K5 has 10 edges, we conclude that it is
nonplanar. Similarly, the complete bipartite graph K3,3 is nonplanar since it is
triangle-free and has 9 edges, while every simple planar triangle-free graph with
6 vertices has at most 8 edges.
We close this section by explaining in which sense these two graphs, K5 and
K3,3 , are essentially the only reason for which a graph may fail to be planar. Let
us first describe an operation that preserves planarity. Given a graph G and an
edge e in G with endpoints u and v, the subdivision of e is the operation that
replaces the edge e in G with a path of length two; formally, it deletes the edge
e, adds a new vertex z, and adds two new edges, one with endpoints u and z, and
one with endpoints z and v. The subdivision of a graph G is any graph obtained
from G by repeatedly subdividing some (possibly none) of its edges. Given two
graphs G and G , we say that G contains G if G can be obtained from G by a,
possibly trivial, sequence of vertex and edge deletions.
Given two graphs G and G such that G is a subdivision of G, it is not
difficult to check that G is planar if and only if G is planar. In particular, all
subdivisions of K5 and K3,3 are nonplanar. Furthermore, when a vertex or an
edge is deleted from a plane graph, the resulting graph is still a plane graph.
This means that each graph contained in a planar graph is planar. We conclude
that whenever a graph contains a subdivision of K5 or K3,3 , we can be sure that
it is nonplanar. As shown by the Polish mathematician Kazimierz Kuratowski in
1930, the absence of subdivisions of K5 or K3,3 is not only a necessary condition
for planarity but also a sufficient one!
What this means is that there is always a good way to certify the planarity
or nonplanarity of a given graph. If the graph is planar, we can certify this by
drawing it in the plane without edge crossings. If the graph is nonplanar, we can
Exercises
1. Let G be the simple graph with vertex set {1, 2, 3, . . . , 9} in which two dis-
tinct vertices are adjacent if and only if they are coprime. The graph H is
defined similarly, except that two distinct vertices are adjacent if and only if
they are not coprime.
(a) Show that G is not planar by showing that it has too many edges / that it
contains a K3,3 / that it contains a K5 .
(b) Show that the graph H is planar by drawing a planar embedding of it.
2. Derive the bound for the maximal number of edges in a bipartite simple
planar graph.
3. Draw a plane embedding of K4 and its dual graph. Verify that for each span-
ning tree the complementary edges form the edges of a dual spanning tree.
v0 , e1 , v1 , e2 , v2 , . . . , vk−1 , ek , vk
without repeated edges. An Eulerian trail in G is a trail containing all the edges
of G. An Eulerian circuit is an Eulerian trail with v0 = vk . A graph is said to be
Eulerian if it admits an Eulerian circuit. ♠
For example, the graph depicted in the left part of Fig. 9.18 is Eulerian, as
evidenced by the traversal of the edges depicted in the right part of the figure.
Note that vertex repetitions are perfectly ok.
An isolated vertex in a graph is a vertex that is not the endpoint of any edge.
If a graph has an isolated vertex v, then deleting v does not affect the existence
of Eulerian trails or circuits. Therefore, when addressing this problem we may
without loss of generality restrict our attention to graphs without isolated ver-
tices. Another easy observation is that if a graph has an Eulerian trail, then any
two of its edges must be connected by a path; that is, all the edges of the graph
must belong to the same connected component. (Do you see why?)
It is not difficult to construct examples of connected graphs that admit an
Eulerian trail but not an Eulerian circuit, or connected graphs that do not admit
an Eulerian trail.
Example 9.18. In Fig. 9.19, two small connected graphs G1 and G2 are de-
picted.
The graph G1 admits an Eulerian trail but not an Eulerian circuit. Traversing
the only edge in either direction yields an Eulerian trail. Since we cannot return
to the starting vertex without traversing the same edge again, the graph does not
admit an Eulerian circuit.
The graph G2 does not admit an Eulerian trail. Do you see why?
Every time an Eulerian trail in a graph visits a vertex, it either has to stop
at that vertex or it has to leave the vertex on a yet unvisited edge. Therefore,
the edges around every vertex, except possibly for the starting and the ending
vertex, can be grouped into disjoint pairs, one for each visit of the vertex. Since
in an Eulerian trail all the edges are traversed, we can conclude that all vertices
of the graph, except possibly two, must have an even degree. Going back to
our example graph G2 , note that all the four vertices of the graph have an odd
degree. It follows that G2 does not have any Eulerian trails. ♦
Theorem 9.19. Let G be a graph without isolated vertices. Then G has an Eu-
lerian trail if and only if G is connected and the number of odd-degree vertices
is either 0 or 2. Furthermore, G has an Eulerian circuit if and only if G is
connected and all its vertices have an even degree.
case. Since the graph is connected, there exists a vertex z that is an endpoint of a
traversed edge as well as an endpoint of an edge that has not yet been traversed.
We now repeat the same procedure starting at the vertex z and using only the
edges not used so far. Using the same arguments as above, we obtain another
trail starting and ending at the vertex z. Combining the two trails by traversing
the first one until the vertex z, then traversing the second one, and finally contin-
uing along the first one until the end, results in an Eulerian circuit of the graph
formed by the edges traversed so far. Repeating the procedure, we eventually
obtain an Eulerian circuit in the entire graph G.
It remains to analyze the case when G is connected and has exactly two
vertices of odd degree, say u and v. Adding to G an edge e with end-
points u and v we obtain a connected graph G in which all vertices have
an even degree. Therefore, G has an Eulerian circuit. Fix an Eulerian circuit
v0 , e1 , v1 , e2 , v2 , . . . , vm−1 , em , vm in G . Since v0 = vm , we may assume, by a
circular shifting of the indices if necessary, that the edge e appears at the end of
the circuit, that is, em = e. But then v0 , e1 , v1 , e2 , v2 , . . . , vm−2 , em−1 , vm−1 is
an Eulerian trail in G.
Exercises
1. The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both
sides of the Pregel River. There were two large islands and two mainland por-
tions of the city, which were connected to each other by seven bridges. The
problem of the Seven Bridges of Königsberg was to devise a walk through
the city that would cross each of those bridges exactly once. Euler showed
that such a walk exists if and only if the graph depicted in Fig. 9.20 contains
an Eulerian trail. Assuming this, explain why the desired walk through the
city does not exist.
3. Fig. 9.21 shows three graphs. For each of them determine if the graph con-
tains an Eulerian trail and whether it contains an Eulerian circuit. If an
Eulerian trail exists, find one.
FIGURE 9.22 Three graphs that behave differently with respect to Hamiltonian paths and cycles.
Do you see why the graph G2 is not Hamiltonian and why the graph G3 is
not traceable?
Deleting any k ≥ 1 vertices from a cycle results in a graph with at most k
connected components. Consequently, if we delete any k vertices from a Hamil-
tonian graph, we obtain a graph with at most k connected components. Similarly,
deleting any k ≥ 0 vertices from a path results in a graph with at most k + 1 con-
nected components. Hence, if we delete any k vertices from a traceable graph,
the resulting graph has at most k + 1 connected components. Let us now apply
these considerations to the graphs G2 ad G3 . If we remove from the graph G2
the middle vertex, the top vertex, and the bottom vertex, we obtain a graph with
4 connected components. We conclude that G2 is not Hamiltonian. Similarly,
if we remove the middle, top, and the bottom vertices from the graph G3 , we
obtain a graph with 5 connected components, and we conclude that G3 is not
traceable. ♦
Note that if a graph G has a loop, then G is traceable if and only if the graph
obtained from G by deleting a loop is traceable, and a similar argument holds
if G contains a pair of edges with the same endpoints. Furthermore, except for
graphs with one or two vertices, similar simplifications on the graph can be done
when studying the property of being Hamiltonian. Therefore, when studying
Hamiltonian paths and cycles, it suffices to consider simple graphs.
Although perhaps surprising at first, you may have guessed from the above
examples that the problem of determining the existence of Hamiltonian paths
and cycles is much more difficult than for Eulerian trails. No simple necessary
and sufficient condition for a graph to be Hamiltonian or traceable is known,
and the problems of deciding if a given graph possesses a Hamiltonian path or
a Hamiltonian cycle are NP-complete – just like the problem we talked about in
Section 4.7, of determining if a given expression in conjunctive normal form ad-
mits a Boolean assignment to the variables which makes the expression TRUE.
This means that no fast solution methods for the Hamiltonicity and traceabil-
ity problems are known. These problems become difficult to solve already for
moderately sized graphs.
Some necessary conditions are known, as well as some sufficient ones. We
have already described in the above example the following necessary conditions.
Theorem 9.22. If G is a traceable graph, then for every set S ⊆ V (G) the
graph G − S has at most |S| + 1 connected components. Furthermore, if G is
Hamiltonian, then for every nonempty set S ⊆ V (G) the graph G − S has at
most |S| connected components.
We would expect a simple graph to have a better chance to be Hamiltonian
if all the vertices are connected by edges to many other vertices. This is indeed
the case, as shown by the following sufficient condition for Hamiltonicity due
to Dirac.
Theorem 9.23. Let G be a simple graph with n ≥ 3 vertices such that each
vertex has degree at least n/2. Then G is Hamiltonian.
Proof. The proof uses induction in a particularly clever way. Fix a positive in-
teger n ≥ 3 and let us denote by Xn the set of all n-vertex graphs in which each
vertex has a degree at least n/2. Associate to each
graph G ∈ Xn the number
e(G) of non-edges in G, that is, the value of n2 − |E(G)|. Then e(G) ≥ 0. To
show that each graph G ∈ Xn is Hamiltonian, we use induction on the value of
e(G).
Base case: e(G) = 0, that is, the graph G ∈ Xn contains all possible edges
between two distinct vertices. Since n ≥ 3, visiting all the vertices of G in some
order and returning back to the first vertex yields a Hamiltonian cycle.
Inductive step: Let k ≥ 0 be given and assume that every graph H ∈ Xn with
e(H ) = k is Hamiltonian. Consider a graph G ∈ Xn with e(G) = k + 1. We
need to show that G is Hamiltonian. Suppose for a contradiction that G is not
Hamiltonian. Since e(G) > 0, there exist two nonadjacent vertices in G, say u
and v. The graph H obtained from G by adding to it the edge {u, v} belongs to
Xn and satisfies e(H ) = e(G) − 1 = k. Therefore, by the induction hypothesis,
H is Hamiltonian. Fix a Hamiltonian cycle C in H . Since G is not Hamiltonian,
the cycle C must use the added edge {u, v}. We may assume that the cycle C
starts at u but not along the edge {u, v} and hence there is an ordering v1 , . . . , vn
of the vertices of G such that u = v1 , v = vn , and any two vertices that are
consecutive in the ordering are adjacent in G. (In particular, G is traceable.)
Let A denote the set of neighbors of u in G and let B = {vi+1 | 1 ≤ i ≤ n −
1 and vertices v and vi are adjacent in G}. Since each vertex in G has degree at
least n/2, we infer that |A| ≥ n/2 and, similarly, |B| ≥ n/2. Furthermore, since
u = v1 belongs to neither A nor B, we have A ∪ B ⊆ {v2 , . . . , vn } and thus
|A ∪ B| ≤ n − 1. It follows that the sets A and B cannot be disjoint, as that
would imply |A ∪ B| = |A| + |B| ≥ n. Using an arbitrary vertex vj ∈ A ∩ B,
we can now construct a Hamiltonian cycle in G, as follows. Starting at u, go to
vj (note that this is possible since vj ∈ A is adjacent to u), then continue via
vj +1 all the way up to vn = v, then go to vj −1 (note that this is possible since
vj ∈ B implies that vj −1 is adjacent in G to v), and go back all the way down to
v1 = u. We conclude that G is Hamiltonian, contradicting our assumption that
G is not Hamiltonian. This completes the inductive step and with it the proof of
the theorem.
Exercises
1. Describe all traceable trees. Are there any Hamiltonian trees?
2. For each of the graphs in Fig. 9.23, determine whether it is traceable and
whether it is Hamiltonian. Justify your answer.
3. Find an example of a connected graph with 6 vertices and 8 edges that is:
(a) Eulerian but not Hamiltonian,
(b) Hamiltonian but not Eulerian,
(c) Eulerian and Hamiltonian,
(d) neither Eulerian nor Hamiltonian.
Can you always find a simple graph with the stated properties?
Theorem 9.24. An edge maximal simple planar graph can be drawn in the
plane with non-crossing straight line segments as edges.
Proof. Consider an edge maximal simple planar graph G. We want to show by
induction on the number n of vertices that G can be drawn with straight line
segments. This is clear for n = 3. Note that in this base case, G = K3 , we have
three vertices, 3 edges, and two faces. The triangle cuts the plane into two pieces,
an interior and an exterior.
For n > 3 we want to first prove by strong induction that there always exists
a vertex v in the interior of the outside triangle and an edge e with endpoint v
such that e is contained in exactly two triangles. For n = 4, the graph is a K4
and the statement holds trivially, since any edge belongs to exactly two trian-
gles. Assume now that n > 4 and that the statement holds for all triangulations
with fewer than n vertices. Let G be a triangulation with n vertices and let v
be any vertex in the interior of the outside triangle. Take any edge e with end-
point v. If the edge e is contained in exactly two triangles, we are done. So we
may assume that the edge e is contained in two facial triangles and also in a
third triangle T . The triangle T contains exactly one of the two triangular faces
separated by e. So T contains a vertex in the interior. Let H be the subgraph of
G consisting of the triangle T and all the vertices and edges drawn in the interior
of T . Then H is an edge maximal simple planar graph with at least 4 vertices
with fewer vertices than G. By the induction hypothesis, there exists a vertex w
of H in the interior of the triangle T and an edge f ∈ E(H ) with endpoint w
such that f is contained in exactly two triangles in H . Due to the planarity of
the drawing, this vertex and edge satisfy the same properties also with respect
to the graph G.
Now let G be any edge maximal simple planar graph on n vertices, and
consider an edge e = {a, b} which separates the facial triangles (a, b, v1 ), and
(a, b, v2 ) and is contained in no other triangle. Identifying the two endpoints
a and b into a vertex v creates parallel edges {a, vi }, {b, vi }, i = 1, 2, but no
other parallel edges. Replacing each of these pairs of parallel edges by a single
edge {v, vi } we obtain a simple graph on n − 1 vertices that is a planar trian-
gulation and can, by induction hypothesis, be drawn with straight lines. In such
a straight line drawing consider the edges emanating from v. One of the two
angles formed by edges {v, v1 } and {v, v2 } contains all edges inherited from
G which had endpoint a in G, the other all the ones which had endpoint b
in G. So we can split v into two vertices a and b a short distance apart, draw
in the straight line segment from a to b, and split the line segments {v, vi } into
two line segments from a, resp. b, to vi . This yields a straight line drawing
of G.
Fig. 9.24 illustrates how the proof can be turned into an algorithm. The in-
duction step applied repeatedly reduces the triangulation to a triangle – and then
we may work backwards, reconstructing the graph step by step, but with straight
line edges.
Could we have started the process by identifying vertices 1 and 5? The an-
swer here is no, since the edge with endpoints 1 and 5 is contained in more
than two triangles, and identifying 1 and 5 would produce three sets of parallel
edges. However, you may want to convince yourself that e is not the only choice
for starting the procedure. Also, the straight line drawing produced is not nec-
essarily optically pleasing; you are encouraged to turn Fáry’s proof into a nice
drawing algorithm.
Note that the proof of Theorem 9.24 involves Euclidean geometry and is not
completely discrete.
We proved Fáry’s theorem for triangulations, but if we want a straight line
embedding of a plane graph that is not edge maximal, we can first triangulate
all faces that are larger than triangles, find a straight line embedding of that
triangulation and then erase the extra edges to obtain a straight line drawing
of our original graph. Triangles are always convex, but k-gons for k > 3 need
not be, so after deleting edges from a triangulation, the resulting faces need
not be convex. However, Sherman K. Stein, in 1951, proved that for a plane
graph whose faces are polygons without repeated vertices or edges, and the
intersection of two faces is connected, there always exists an embedding such
that all faces are convex. The key lemma used in the induction proof on the
number of faces is claiming the existence of two neighboring faces A and B
such that for all other faces C the set C ∩ (A ∪ B) is connected. The proof of
this lemma is essentially the same as our argument about the existence of an
edge e contained in exactly two triangles. From Stein’s result Fáry’s theorem
follows. Convexity is a geometric property and the faces here are considered
closed and simply connected (in the topological sense) subsets of the Euclidean
plane. We encourage you to work through Fáry’s and Stein’s original papers and
determine which of the two results is more discrete.
connected with the following edges: (10 · · · 0, 20 · · · 0), (01 · · · 1, 21 · · · 1), and
(02 · · · 2, 12 · · · 2).
So, recursively, we just take three copies of the n-disk graph and add three
edges between them, only joining some of the special, degree 2 vertices. What
do we start with? Just a triangle! I won’t draw it for you, in fact, in this section
you have to do all the drawing. Try. The four disk graph takes four minutes.
So now you have a beautiful picture of the Towers of Hanoi graph. It’s not
beautiful? Did you notice that the graph is planar? Before you try again, we’ll
prove that outrageous claim. We’ll do it by induction and as often happens, it is
easier to prove a somewhat stronger statement. The Towers of Hanoi graph for n
disks has a planar drawing in which all the degree 2 vertices are on the exterior
face. For the base case, the graph is a triangle, so the claim is true, every vertex
is on the exterior face. Now let n ≥ 0 be given and represent the graphs on a
piece of paper by three blobs and label the 9 special vertices wherever you like
on the three blob boundaries. Can you join them correctly by edges in just the
exterior? You might need squiggly edges, but, unlike the similar but impossible
water-gas-electric problem, this should only take you a few seconds. Now, are
all the remaining special vertices, the degree two ones, on the exterior face?
No? No problem. The blobs are only attached at two points, so they be redrawn
twisted upside down. Done. Now that you know that the graph is planar, try to
make a better picture.
Here is another fact you can prove by induction, just add it to the inductive hy-
pothesis above and it will mostly slide right through: There is a planar drawing
with the optimal path from all 0’s to all 2’s laying entirely along the exte-
rior face. Here is another, there a Hamiltonian path joining state 0000000 to
2222222. That corresponds to a sequence of moves starting with 0000000, pass-
ing exactly once through every possible state, and ending 2222222. Don’t you
wonder what it looks like?
Too bad that there isn’t a Hamiltonian cycle. But maybe there is. Why don’t you
recycle your simplified water-gas-electric blob diagram and see if that can help
you prove that there is one. All these results you can describe and prove without
the graph, or the pictures, but why would you? And while it may be true that
only a madman would actually draw a graph on two thousand vertices and three
thousand edges, a mathematician will certainly try to imagine it, and a computer
scientist will certainly try to program a computer to render it.
Let go. What is the result? The Anchurian custom says that if the 6 strings
form a ring, you may marry your partner.
Interpreting the 6 strings as edges and the knots as vertices, we see that the
result of the experiment is a graph G on 6 vertices and 6 edges. The graph is bi-
partite, since every edge goes from top to bottom. It is also 2-regular, i.e., every
vertex is of degree 2 (since the strings were tied two by two). How can we count
the number of 2-regular bipartite graphs on six vertices? Let us first assume
that we are counting graphs whose edges are labeled 1,
. . . , 6. For tying the top
knots, by the multiplication principle, there are 62 42 22 possibilities, and we
can divide this number by 6, since we are not interested in which order the knots
were tied, only in the resulting three knots. The same holds for the bottom three
knots, so there are 152 possibilities to tie the knots. After the bottom knots are
tied, there are 15 ways to tie the top knots, we list them in Fig. 9.26. You see
that 8 out of the 15 outcomes are connected, 6 are consisting of a 4-cycle and
a 2-cycle, and one consists of three 2-cycles. Let us call two graphs isomorphic
if there is a bijection between their vertex sets preserving adjacency. Graph iso-
morphism induces an equivalence relation on the set of graphs produced by the
experiment and we see that there are three isomorphism classes.
We could consider the experiment having three different outcomes: three
2-cycles, a 2-cycle and a 4-cycle, or a 6-cycle. We can put our counting tech-
niques to work to answer the question about likelihood. What is the probability
8
to obtain a 6-cycle? It is 15 > 12 .
Now we want to discretely generalize the experiment. Instead of 6 strings
we want to consider 2n strings (why do we want an even number of strings?). It
1 Anchuria is a fictional country invented by O. Henry. A. Engel, well known for his mathematical
problem collections and pedagogy, uses this setting to describe several interesting problems.
Chapter 1 – Discreteness
1.2 Of course this is subjective, but Morse code seems discrete in a way that
hula dancing is not.
1.3 I say frissbeeee . . . to h-o-p-s-c-o-t-c-h.
2.1 Hint: If the students all answer honestly, you cannot assume indepen-
dence. Why?
2.2 You can analyze the problem by considering the no-hood option sepa-
rately, or taking “no hood” to be another color “invisible”. So the answer
is 4 · 5 · 2 = 40 or 4 · 4 · 2 + 4 · 2 = 32 + 8 = 40.
2.3 Hint: I would say that if you don’t take the entrée, you are not ordering
the special. All other courses are optional, including taking the salad with
no dressing.
5 10 5 10 3 10 2 10 1 10 0
3.1 105 9 + 6 9 + 7 9 + 8 9 + 9 9 + 10 9 .
10
3.2 5 510 .
3.3 Billiard balls are numbered and colored. We say they are distinguishable.
So for each ball, we have to choose a compartment. These drawer com-
partments are also distinguishable. So for each ball, choose one of the
three compartments. Fifteen choices of 3 give 315 . (Not 153 .) What if
they were ping-pong balls?
4.1 The circled entries are placed symmetrically, or did you forget to count
from
zero?
100 100!49!51! 49!51! 49!50!(51) 51
4.2 100
50 / 49 = 100!50!50! = 50!50! = 49!(50)50! = 50 > 1.
4.3 Hint: You have 8 children, 4 boys
and 4 girls, and want to count the
number of groups of size 4, so 84 since sex is irrelevant to the question.
But what if you want to take it into account anyway?
5.1 The first two are easy. The third is a shift, notice the “binary point”. The
last should look familiar, and note that it is easier if you write the carries
also inbinary.
11 11 11
5.2 211 − 11 3 − 2 − 1 − 0 .
5.3 First is 1 followed by 16, second has 64 zeros.
213
6.1 2020 in binary is 1100101000000 using either method. If you are like
most people, you add commas to make it easier to read: 1,100,101,000,
000. The numbers in between the commas are 3 digit binary numbers,
so 0 to 7, – aha – the digits in base 8, that’s the trick! Base 8: 14500,
Base 16: 1,1001,0100,0000, or 1940.
6.2 22212102 and 201324.
6.3 1776 is ↑↓↑↑ 0 ↑↓↑ 0.
Chapter 5 – Induction
1.1 a) True: Richard Feynman was born after 1888.
False: Albert Einstein was born after 1888.
1.2 a) True: 36 is the sum of three distinct cubes.
False: 35 is the sum of three distinct cubes.
1.3 It is small diagonal red “eight” in a sea of blue.
2.1 You get to choose n: Let n = 1, then 12 + 5 = 6 · 1, as required. (Where
did the 1 come from? Work had to be done but that is not part of the
proof.)
2.2 Let n ∈ N. Consider two cases, n is even, . . . . (Now you are started.)
2.3 a) and b) are true by choosing m = 0. c) is false, since given n, you can
take m > n3 + 1.
3.1 The base case is 3 · 0! > 02 .
The induction step requires that you prove, for any given n ≥ 0, that
3 · n! > n2 implies 3 · (n + 1)! > (n + 1)2 .
The induction hypothesis, for the given n ≥ 0, is 3 · n! > n2 .
3.2 Hint: The fact that the statement is false has nothing to do what you
would do to prove it.
3.3 P5 must be true. P25 , P35 , and P45 must be false. P15 cannot be deter-
mined.
4.3 Since P15 is true, any predicate on an odd index greater than 15 is true
by induction, so P55555 is true.
Since P14 is false, any predicate on an even index less than 14 is false,
otherwise P14 would be true by induction, so P0 and P4 are both is false.
About P2100 we can make no conclusion.
6.1 {0, 1, 3} = {0, 1, 2, 3, 4} ∩ {0, 1, 3, 4, 5, 6, 7, 8, 9}.
6.2 Let the universe U = N. T = {2}. P is the set of primes. E = {n ∈ N; n =
2k; k ∈ N}. P ∩ E ⊆ T .
6.3 Define pn to be 1 is k − 1 is evenly divisible by 5 and 0 otherwise.
a0 a1 a2 a3 a4 a5 a6 a7
0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1
2 1 2 4 1 2 4 1 2
3 1 3 2 6 4 5 1 3
4 1 4 2 1 4 2 1 4
5 1 5 4 6 2 3 1 5
6 1 6 1 6 1 6 1 6
The 6th and 7th columns are just what are predicted by Fermat’s Little
Theorem.
2.3 b) 21710 = (21700 )(210 ) = (2100 )17 210 ≡ 1 · 1024 ≡ (10)(101) + 14 ≡
14 mod 101.
3.1 The multiplicative decoding key is the multiplicative inverse of 7 modulo
26 which is 15.
3.2 Hint: The encoding and decoding keys are established modulo 10 but the
encoding and decoding are done modulo 11.
3.3 For exponential, the numbers not coprime to 10 are {0, 2, 4, 5, 6, 8, 10}.
4.1 δ = 77.
4.2 (108, 141, 166).
4.3 Hint: You need the multiplicative inverse of 67 modulo (3 − 1)(101 −
1) = 200; which is 3.
5.1 52802 = 1,0100,1010,0000, a 13 digit binary number, so the Euclidean
algorithm should take at most 26 steps by our bound.
5.2 limn→∞ 500n +1000n
5 3
n6
= limn→∞ 500n + 1000n = 0 + 0 = 0.
3
2n +3n
5.3 limn→∞ 5n = limn→∞ (2/5)n + (3/5)n = 0.
9 7 4 3 1
6.1 1776(2 ) · 1776(2 ) · 1776(2 ) · 1776(2 ) · 1776(2 ) .
6.2 722 ≡ 49 mod 100.
A B
Action strings, 66 Backwards induction, 106
Acyclic, 208 Base
connected graph, 186 cases, 98, 104, 112
graph, 182, 184 conversion, 14
Adjacency Basic Boolean identities, 75
lists, 188 BFS, see Breadth-first search (BFS)
lists representation, 188
Billiard balls, 2, 10, 67
relation, 133
Binary
Albertson’s Magic Trick, 1, 2, 4, 5, 7, 13
bits, 68, 106
Algebra
Boolean, 75, 76, 81–83, 88, 91, 95 digits, 13, 14, 106
Boolean expressions, 81 expression, 15
real functions, 95 form, 56
Algebraic format, 14
approach, 82 logical operation, 77
assertion, 101 number, 12–14, 24, 52, 53, 61, 67, 106,
equations, 155 146
expositions, 159 number system, 145
expression, 85, 117, 175, 179 operations, 34, 35
structures, 115 relation, 115, 140
Algorithm, 15, 177 representation, 23, 24, 169, 174, 175
Alphabet, 29, 57, 60, 61, 66, 169, 177, strings, 68, 107
185 system, 13
element, 177 Binomial
letters, 169, 178
coefficient, 8–12
Roman, 29
theorem, 18, 19, 51, 112
set, 169
Bipartite, 183
Alphabetic order, 59
Alphabetical ordering, 53 Bit, 13
Anchuria, 210 assignment, 83
AND clause, 84, 85 binary, 29, 68, 106
Antecedent, 77, 78, 81, 92, 94 sequences, 13
false, 94 vector, 52, 53, 57, 66–68
Anti-reflexive, 208 order, 54, 71
Axiomatic set theory, 41 ordering, 53
221
Delisting, 61 Dual
permutations, 64 graph, 195, 196, 198
problem, 61 operation, 196
Depth-first search (DFS), 188, 189 spanning tree, 198
tree, 189
Derangement, 69, 70 E
Developer’s problem, 132, 137 Edge, 181
DFS, see Depth-first search (DFS) Edge set, 181
Digits, 29 Elements, 27
arithmetic, 62 domain, 119, 121
binary, 13, 14, 106 for finite sets, 124
decimal, 29, 63, 66, 163 general, 30, 38, 62
Gray code, 106 golden, 51, 52
length, 61 in
numbers, 24, 109 lexicographic order, 59
Diophantine, 155 related, 117
equation, 158 remaining, 65
problem, 156 string, 168
Direct road connection, 185 target, 121
Directed graph, 127, 130 Empty
Discrete mathematics, 115, 117, 125, 131 set, 28, 31
Discreteness, 2 string, 57
Disjoint pairs, 200 Encoding, 52, 66, 67, 134, 171, 179
algorithm, 177
Disjunctive normal form (DNF), 84, 85
keys, 168, 170–172, 179
Distinct
letters, 168
domain elements, 121
numbers, 145
vertices, 182
symmetric relations, 177
Distributive law, 19, 36, 79, 81, 85, 92,
Encryption, 169, 170
95, 97, 150
function, 168
basic, 58
key, 168–170, 173
general, 58
schemes, 179
Divisible numbers, 40, 149 Endpoints, 181, 182
Division, 60, 64, 143, 145, 147–149, 151, Equivalence, 130
165, 171, 173 class, 131, 132, 137, 138
with remainder, 143, 146 relation, 130–132, 137
DNF, see Disjunctive normal form (DNF) Eratosthenes’s sieve, 143, 144, 173
Domain elements, 119, 121 Euclidean algorithm, 145–147, 160
Domain set, 117 Euclid’s Coin Problem, 147, 148, 151,
Double implication, 79–82, 91, 98, 159, 159
165 Eulerian
method, 79 circuit, 198–202
proof, 82 graphs, 198
Double inclusion, 37, 79–81 trail, 198–203
method, 37–39, 48, 49, 58, 146, 159 Euler’s formulas, 196
proof, 40, 80 Even versus odd, 4
Members, 27 natural, 2, 15
Membership, 27–31, 33, 34, 52, 53, 123 prime, 28
Membership list, 33 rational, 3
Merge sort, 190, 192 real, 28
algorithm, 192 sequence, 103, 185
Merged list, 191 sets, 34, 150
Minimum Spanning Tree, 186, 205 Numerical algebra, 76
problem, 186, 187
Misordered pairs, 108 O
Modular arithmetic, 149, 150, 156, 160, Objects
168, 169, 174 list, 188
Modulus, 150 sequences, 65
Multiple Obstruction
Cartesian product, 56, 57, 59–62 function, 133, 137, 138
edges, 181, 182 relation, 133, 137
union, 58 Oddness, 107, 108, 149
Multiplicative Operation
cypher, 168, 169 binary, 34
inverse, 143, 151–154, 164–166, unary, 34
168–171, 175, 176 Operator notation, 117
orders, 165, 179 Optimal solution, 110, 111
unique, 110
principle, 5–8, 10, 18, 21, 22, 31, 32,
Or, inclusive, 33
35, 51, 52, 55, 57, 66, 69, 83,
OR clause, 85, 86, 88
85, 86, 109, 119, 136, 185
Ordered
pairs, 35
N selection, 9
Nantucket map
Ordering, 130
problem, 1 bit vector, 53
Natural permutations, 61
language, 9, 28, 33, 34, 73, 74, 77, 79, subsets, 52
91, 115
number, 15 P
numbers, 28, 29, 40, 58, 94, 95, 113, Pairwise intersection, 69
123, 125, 130, 143, 157, 158 Palindrome, 22
numbers list, 59 Parallel edges, 181, 184, 205, 207
Non-transitive dice, 135 Partial order, 130
Nonplanarity, 197 diagrams, 130
Normal form, 84 strict, 135–137
NP-complete, 203 Pascal’s Triangle, 10–12, 18
Numbers Path, 182, 208
bases, 14, 16 Permutations, 62–65, 69, 70, 107, 108,
binary, 12–14, 24, 52, 53, 61, 67, 106, 168
146 evenness, 107
decimal, 13, 14, 28, 61, 64 Planar, 209
digits, 24, 109 Planar graph, 193–196
divisible, 40, 149 Planarity, 193, 197, 206
encoding, 145 Plane graph, 194, 195
integer, 2, 189 Platonic solids, 42, 45
T V
Target Vertex
element, 119, 121 degree, 182
set, 117 set, 181, 210
Ternary numbers, 110
Three utilities problem, 193 W
Threven numbers, 149 Walk, 182
Throdd, 149, 150 bounding, 197
Topological structures, 115 closed, 182
Towers of Hanoi, 17, 208 length, 182
Traceable traversing, 202
graph, 202–204 Weakly independent, 8
trees, 205 Wolf-Goat-Cabbage, 66, 133
Transitive, 173 problem, 1, 3
relation, 127, 129, 176 relation diagram, 134