1483 Problem Solving
1483 Problem Solving
1483 Problem Solving
USA
Phone: 1-800-832-2412
www.thegreatcourses.com
Cover Image: © SSPL/The Image Works.
Course No. 1483 © 2010 The Teaching Company. PB1483A
PUBLISHED BY:
P
aul Zeitz is Professor of Mathematics at the
University of San Francisco. He majored in
History at Harvard University and received
a Ph.D. in Mathematics from the University of
California, Berkeley, in 1992, specializing in
Ergodic Theory. Between college and graduate school, he taught high school
mathematics in San Francisco and Colorado Springs.
Professor Zeitz has also been active in events for high school students. He
founded the San Francisco Bay Area Math Meet in 1994; cofounded the Bay
Area Mathematical Olympiad in 1999; and currently is the director of the
San Francisco Math Circle, a program that targets middle and high school
students from underrepresented populations.
Professor Zeitz was honored in March 2002 with the Award for Distinguished
College or University Teaching of Mathematics from the Northern California
Section of the Mathematical Association of America (MAA), and in January
2003, he received the MAA’s national teaching award, the Deborah and
Franklin Tepper Haimo Award. Ŷ
i
Table of Contents
INTRODUCTION
LECTURE GUIDES
LECTURE 1
Problems versus Exercises ................................................................4
LECTURE 2
Strategies and Tactics ......................................................................10
LECTURE 3
The Problem Solver’s Mind-Set ........................................................16
LECTURE 4
Searching for Patterns ......................................................................20
LECTURE 5
Closing the Deal—Proofs and Tools .................................................24
LECTURE 6
Pictures, Recasting, and Points of View ...........................................30
LECTURE 7
The Great Simpli¿er—Parity .............................................................35
LECTURE 8
The Great Uni¿er—Symmetry ..........................................................41
LECTURE 9
Symmetry Wins Games! ...................................................................45
LECTURE 10
Contemplate Extreme Values ...........................................................51
ii
Table of Contents
LECTURE 11
The Culture of Problem Solving........................................................55
LECTURE 12
Recasting Integers Geometrically.....................................................58
LECTURE 13
Recasting Integers with Counting and Series...................................63
LECTURE 14
Things in Categories—The Pigeonhole Tactic..................................67
LECTURE 15
The Greatest Uni¿er of All—Invariants .............................................71
LECTURE 16
Squarer Is Better—Optimizing 3s and 2s .........................................76
LECTURE 17
Using Physical Intuition—and Imagination .......................................80
LECTURE 18
Geometry and the Transformation Tactic..........................................85
LECTURE 19
Building from Simple to Complex with Induction ..............................89
LECTURE 20
Induction on a Grand Scale ..............................................................94
LECTURE 21
Recasting Numbers as Polynomials—Weird Dice............................98
LECTURE 22
A Relentless Tactic Solves a Very Hard Problem ...........................103
LECTURE 23
Genius and Conway’s In¿nite Checkers Problem ..........................108
iii
Table of Contents
LECTURE 24
How versus Why—The Final Frontier............................................. 113
SUPPLEMENTAL MATERIAL
iv
The Art and Craft of Mathematical Problem Solving
Scope:
T
his is a course about mathematical problem solving. The phrase
“problem solving” has become quite popular lately, so before we
proceed, it is important that you understand how I de¿ne this term.
I contrast problems with exercises. The latter are mathematical questions that
one knows how to answer immediately: for example, “What is 3 + 8?” or
“What is 3874?” Both of these are simple arithmetic exercises, although the
second one is rather dif¿cult, and the chance of getting the correct answer is
nil. Nevertheless, there is no question about how to proceed.
In contrast, a problem is a question that one does not know, at the outset, how
to approach. This is what makes mathematical problem solving so important,
and not just for mathematicians. Arguably, all pure mathematical research
is just problem solving, at a rather high level. But the problem-solving
mind-set is important for all who take learning seriously, especially lifelong
learners. Much of the current craze in brain strengthening focuses merely on
exercises. These are not without merit—indeed, mental exercise is essential
for everyone—but they miss out on a crucial dimension of intellectual life.
Our brains are not just for doing crosswords or sudoku—they also can and
should help us with intensive contemplation, open-ended experimentation,
long wild goose chases, and moments of hard-earned triumph. That is what
problem solving is all about.
1
Becoming a good problem solver requires new skills (mathematical as well
as psychological) and patient effort. My pedagogical philosophy is both
experiential and analytic. In other words, you cannot learn problem solving
without working hard at lots of problems. But I also want you to understand
what you are doing at as high a level as possible. We will break down the
process of solving a problem into investigation, strategy, tactics, and ¿ner-
grained tools, and we will often step back to discuss not just how we solved
a problem but why our methods worked.
A small but important part of the course explores the culture of problem
solving. I will draw on my experience as a competitor, coach, and problem
writer for various regional, national, and international math contests, to make
Scope
the little-known world of math Olympiads come to life. And I will discuss
2
the recent educational reform movement (in which I am a key player) to
bring Eastern European–inspired mathematical circles to the United States.
3
Problems versus Exercises
Lecture 1
I
n this introductory lecture, we de¿ne the main entity that we will study
in this course: problems. Problems, by de¿nition, are dif¿cult, and our
investigation of them cannot proceed without organized strategies and
tactics. Indeed, our course focuses on 3 things: investigation, strategies, and
tactics. Problem solving is at the heart of mathematics. It is not just a way of
thinking about math but is an intellectual lifestyle with its own mathematical
folklore and culture. Most of our learning
will be by example. Almost every lecture
will revolve around one or more problems. Much of the current
You, the viewer, will need to use the Pause craze in brain
button and pencil and paper. This lecture strengthening focuses
will include several fun problems not
on exercises. This
requiring any special mathematical skills,
but in later lectures, the problems will be is not without merit,
more complex. but our brains should
Lecture 1: Problems versus Exercises
4
What do I mean by “problems versus exercises”? This course is devoted
to the study of problem-solving investigation and the strategies and tactics
that facilitate it. An exercise is a mathematical question that you know
immediately how to answer. You may not answer it correctly, and it may not
be easy, but there is no doubt about how to proceed. In contrast, a problem is a
mathematical question that you do not know how to answer, at least initially.
Problems require investigation, which employs strategies and tactics.
Why study problem solving? It helps you develop a problem solver’s mind-
set, which involves both heightened mental discipline and an explorer’s
attitude. Much of the current craze in brain strengthening focuses on
exercises. This is not without merit, but our brains should also work on
intensive contemplation and open-ended experimentation. A good problem
solver is intellectually playful and fearless.
5
and solution tell important stories that teach us about problem solving
and show us the beautiful interconnectedness of mathematics. From time
to time, we change our focus from problem solving itself to exploring the
problem-solving culture. We do this not just because it is interesting but
because it is essential.
Northbound Southbound
12:00 12:10
12:20 12:30
12:40 12:50
6
• But look at this schedule!
Northbound Southbound
12:00 12:05
12:20 12:25
12:40 12:45
• Now we have a balanced dose but one too big. Wishful thinking:
Imagine that you are a giant (twice as large as a normal
person). Then you would be done! This immediately suggests
the solution: Cut the double-sized dose in half (or grind up and
divide in half), producing 2 days of correct dosages to get us
back on track.
7
• What we did was use wishful thinking and symmetry. Why we
did it was to increase our ability to investigate and move our
solution toward a con¿guration with more balance and possibly
more information.
Suggested Reading
Questions to Consider
1. You are in the downstairs lobby of a house. There are 3 switches, all in
Lecture 1: Problems versus Exercises
the off position. Upstairs, there is a room with a light bulb that is turned
off. One and only one of the 3 switches controls the bulb. You want to
discover which switch controls the bulb, but you are only allowed to go
upstairs once. How do you do it? (No fancy strings, telescopes, and so
on are allowed. You cannot see the upstairs room from downstairs. The
light bulb is a standard 60-watt bulb.)
8
2. You are locked in a 50- × 50- × 50-foot room that sits on 100-foot stilts.
There is an open window at the corner of the room, near the Àoor, with
a strong hook cemented into the Àoor by the window. So if you had a
100-foot rope, you could tie one end to the hook and climb down the
rope to freedom. (The stilts are not accessible from the window.) There
are two 50-foot lengths of rope, each cemented into the ceiling, about
1 foot apart, near the center of the ceiling. You are a strong, agile rope
climber, good at tying knots, and you have a sharp knife. You have no
other tools (not even clothes). The rope is strong enough to hold your
weight, but not if it is cut lengthwise. You can survive a fall of no more
than 10 feet. How do you get out alive?
9
Strategies and Tactics
Lecture 2
So far we’ve seen the difference between problems and exercises, and
we’ve solved several problems using 2 very, very simple commonsense
strategies: wishful thinking and get your hands dirty. What we’ll do
in this lecture is develop a careful de¿nition of strategies and tactics,
which is what we need to proceed with problem-solving investigations,
and we’ll look at an analytic approach to problem solving. … Along the
way, of course, we’ll solve some classic problems using several different
approaches. We’ll do some where we concentrate on strategies and
others where we’re concentrating more on tactics.
T
he main goal of this lecture is an overview of the analytic approach
to problem solving, carefully de¿ning the notions of strategy and
tactics that were introduced in Lecture 1. All problems require
investigation, and to facilitate investigation, we need many resources.
These are collectively called strategies, and we will mention several but
only focus on a few during this
lecture. Tactics have a narrower
and more mathematical focus and Strategies are ideas, mostly
are used, generally, at a later stage nonmathematical, that
of investigation, often providing the
facilitate investigation of
key to solution. In this lecture, we
will look at 2 classic problems. An almost any problem. Tactics
Lecture 2: Strategies and Tactics
10
Omnicorp Story Problem
• The only catch is that the answer must make sense in terms
of units.
How does the analytic approach to problem solving work? Use strategies
to begin and facilitate the investigation. Next, deploy tactics to continue
the investigation and hopefully yield a solution. Use tools (a.k.a. tricks)
sparingly, at the narrowest focal level. Strategies are ideas, mostly
nonmathematical, that facilitate investigation of almost any problem. Tactics
are more narrowly focused, mostly mathematical, ideas that help one solve
many problems that have been “softened” by good strategy. Tools have very
narrow applications—and very impressive results when used correctly. Ŷ
11
The Census Taker Problem
• A classic example, one of my favorites, that uses the get hands
dirty strategy.
• The ¿rst clue says, “The product of the ages is 36.” There are
only a few possible ways you can multiply 3 whole numbers to
get 36; it makes sense to systematically list them.
• The second clue says that if she told him the sum, he would
Lecture 2: Strategies and Tactics
12
The Frog Problem
• The frog problem is a classic Russian math circle problem.
• Will a frog ever occupy the vertex of the square that was
originally unoccupied?
• Some of the coordinates that the red frog hits are (1, 1), (1, 3), (1,
í1), (í1, 1), (í1, í1), and (í1, í3). They are all odd numbers!
• Likewise, the blue frog only hits certain points on a 2-unit grid,
including (0, 1), (2, 1), (4, 1), and (0, í1); these are all of the
form (even, odd).
13
• Likewise, the green frog only hits (even, even) points.
• For example, suppose the red (1, 1) frog jumps over the green
frog at (0, 0). The horizontal and vertical displacements to the
leapee are both í1 (since it is moving left and down), so the ¿nal
change in coordinates will be í2. The horizontal coordinate
Lecture 2: Strategies and Tactics
• Suppose now that the red frog jumps over the blue frog,
which is (0, 1). The horizontal displacement is +1, and the
vertical displacement to the target is +2. So the new horizontal
coordinate will be í1 (the starting value) + 2 × 1 = +1, and the
new vertical coordinate will be í1 (the starting value) + 2 × 2
= 3. Thus the red frog jumps from (í1, í1) to (1, 3).
14
• In general, when a frog jumps, we will take its starting
x-coordinate and add twice the horizontal displacement to its
target. Likewise, we take its starting y-coordinate and add twice
the vertical displacement to the target. These displacements
may be positive, negative, or zero.
Suggested Reading
Questions to Consider
15
The Problem Solver’s Mind-Set
Lecture 3
I
n this lecture, we discuss some of the mental tools needed for successful
problem solving. A good problem solver needs concentration,
con¿dence, and creativity—but how can one acquire these, and how can
these attributes be enhanced? We explore some classic puzzlers and begin to
develop some number theory ideas and to investigate a problem about the
famous Fibonacci numbers.
addictive. As with any art or craft, you must set aside a quiet time and place
for your work and start building your concentration. Start building up a stock
of back-burner problems. Make good use of unstructured time.
When Gauss was only 10, as legend has it, he was faced with the sum
1 + 2 + 3 + … + 100. How was he to compute it, in 1787, when there were
no calculators? He simply paired the terms: (1 + 100) + (2 + 99) + … +
(50 + 51). Thus the sum is 50(101) = 5050.
16
The second tool is telescoping. We will apply it to a harder sum
involving fractions:
1 1 1 1
"
1u 2 2 u 3 3 u 4 99 u 100
Do not let such a problem make you panic: Panicking is bad for your
con¿dence and harms investigation. You must look for things that foster
investigation. The wishful thinking strategy works for this reason: Pretending
you have solved a problem—even an easier one—keeps you happy, and that
keeps you thinking about the problem!
1 1/ 2 1/ 1 u 2
1/ 2 1/ 3 3 2 / 2 u 3 1/ 2 u 3
1/ 3 1/ 4 4 3 / 3 u 4 1/ 3 u 4
• Thus all terms cancel (telescope) except the ¿rst and last, yielding
the answer 1 í 1/100 = 99/100.
17
How do you get more creative? The 3 c’s are inextricably linked:
Concentration leads to con¿dence, which frees you to explore, which
facilitates investigation and creativity. You need to set up a problem-solving
routine. And think about peripheral vision: Many problems cannot be solved
with direct focus. Many problems need to percolate in your unconscious.
You need to cultivate a good supply of back-burners and get in the habit
of not solving problems. The more you
can cultivate a state of investigation
and purposeful contemplation, the more People are endowed
powerful your mind will get. unequally with con¿dence,
creativity, and power of
We end with a fun open-ended problem
designed to facilitate uninhibited concentration, but all of
investigation. There are no wrong these are trainable skills.
answers. First, a little introduction
to modular arithmetic: We write
a { b mod m , read “a is congruent to b modulo m,” if a í b is divisible by
m. The nice thing about congruence is that it preserves addition, subtraction,
and multiplication. For example, if 17 { 2 (mod 5) and 8 { 3 (mod 5), then
17 × 8 { 2 × 3 (mod 5). You can think of congruence as a sort of myopia
in which we lump the in¿nitude of integers into just a few categories. In the
(mod 5) universe, there are only 5 types of numbers, those congruent to 0, 1,
2, 3, and 4 (mod 5). If we restrict ourselves to the (mod 2) universe, that is
Lecture 3: The Problem Solver’s Mind-Set
the same as only worrying about parity. The Fibonacci numbers are de¿ned
by f1 f 2 1 and f n f n 1 f n 2 for n greater than 2. The ¿rst few terms
are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and 144.
18
• Trying mod 3, we get 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, … , and we see that
every fourth one is a multiple of 3.
Suggested Reading
Gardner, Aha!
Honsberger, Ingenuity in Mathematics.
Zeitz, The Art and Craft of Problem Solving, sec. 2.1.
Questions to Consider
2. One day Martha said, “I have been alive during all or part of 5 decades.”
Rounded to the nearest year, what is the youngest she could have been?
19
Searching for Patterns
Lecture 4
The moral of the story that we’ve seen is that uninhibited experimentation
is lots of fun and it often leads to many fun conjectures, but mere
pattern hunting is not enough if we do not understand the why behind
what we see.
I
n this lecture, we step back a bit and examine the power of simple strategies
that allow us to simplify problems, make numerical experiments, and
develop conjectures. We also look at 2 cautionary examples that show
that experimentation and conjecture is not always enough. The core of this
lecture is the beginning of an investigation into
trapezoidal numbers and a search for patterns in
Perhaps the Pascal’s triangle. This lecture is devoted to the
most important search for patterns by getting one’s hands dirty.
mathematical We will look at several examples where this
strategy succeeds, as well as ones where it is
playground of all is clearly not enough.
Pascal’s triangle.
It is helpful to build up a stock of knowledge to
aid our receptiveness to discovery. You must be
at least passively aware of some of the most important subsets of the integers.
It is important to develop an obsession with numbers and sequences.
Lecture 4: Searching for Patterns
20
• Factorials:
1! = 1,
2! = 1 × 2 = 2,
3! = 1 × 2 × 3 = 6,
4! = 1 × 2 × 3 × 4 = 24,
5! = 4! × 5 = 120,
6! = 720,
7! = 5040.
1,
1 + 2 = 3,
1 + 2 + 3 = 6,
1 + 2 + 3 + 4 = 10.
• 6 = 1 + 2 + 3.
• 36 = 11 + 12 + 13.
Our goal for now is to ¿nd at least 5 interesting patterns in Pascal’s triangle.
Carefully write out rows 0 to 10, at least. The sums of the elements in each
row are powers of 2. The alternating sums, however, are always 0. The
hockey-stick pattern: For example, 1 + 4 + 10 = 15. Triangular numbers
(1, 3, 6, 10, … ). Fibonacci numbers even appear; it is easier to see this if we
draw Pascal’s triangle this way:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1.
There are limits to inductive reasoning. Here are 2 examples of why seeing a
pattern is not suf¿cient if you do not understand why the pattern is there.
22
• The 5 circles problem: If n points are placed on a circle and all
pairs of points are joined by line segments, into how many regions
is the circle divided? Assume that the points are in general position
(i.e., no 3 lines intersect in a single point). Investigation quickly
yields the sequence 1, 2, 4, 8, 16. The obvious conjecture is that the
number of regions is 2n1 , where n is the number of points. But a
careful count of the 6-point circle yields only 31 regions!
The moral of the story is clear: You must understand what you are
looking at. Ŷ
Suggested Reading
Questions to Consider
1. For each positive integer n, ¿nd distinct positive integers x and y such
that 1/x + 1/y = 1/n.
2. Draw triangles with lattice point vertices. Count the number of lattice
points in the interior (I) and boundary (B). Is there a formula relating
these 2 numbers to the area (A)?
23
Closing the Deal—Proofs and Tools
Lecture 5
T
his lecture focuses on closing the deal: turning your investigative
ideas into rigorous arguments. We ¿rst develop the ideas of
deductive proof and proof by contradiction. Many problems also
require ¿nely focused ideas known
as tricks, or tools. We brieÀy discuss
some of the most important of these, In¿nite processes such
while strenuously arguing against their as sums and fractions
overuse (a common beginner’s error). are de¿ned by looking
at the ¿nite version and
It is critical to become comfortable
Lecture 5: Closing the Deal—Proofs and Tools
24
• Now count the 2s in the prime factorizations and use the fundamental
theorem of arithmetic.
• The left-hand side has an odd number of 2s, while the right-hand
side has an even number—a contradiction!
Now we can prove the conjecture about trapezoidal numbers from the
last lecture.
• For the ¿rst goal, since powers of 2 are totally even, it makes
sense to think about parity.
25
• In the other direction (showing that all non–powers of 2 work), let T
be such a number. Then we have to ¿nd a and n, both positive, with
n > 1, such that T = n(2a + n í 1)/2.
• Thus, for any value of T that has at least one odd factor (besides
1), compute 2T and factor it into a product of an odd and an
even. The smaller factor will be n, and the larger will be 2a +
n í 1, and we will be able to solve for a.
• Assume, to the contrary, that there are ¿nitely many primes, ending
with the prime number L.
Lecture 5: Closing the Deal—Proofs and Tools
Now let’s apply these methods to the Fibonacci divisors problem. First
we need a little tiny lemma. Lemma: If p is prime and ab is congruent to
0 (mod p), then a = 0 or b = 0. This lemma is not true for composites [2 ×
26
3 is congruent to 0 (mod 6)]. We will use this to prove our conjecture about
Fibonacci divisors. For example, F4 3 , so we conjecture that every fourth
Fibonacci is a multiple of 3. Modulo 3, the ¿rst 4 Fibonacci numbers are 1,
1, 2, and 0. But the ¿fth and sixth Fibonacci numbers are 2 and 2. The rest
of the sequence behaves like the ¿rst terms, only now they are multiplied by
2! So the second 4 terms are equal to the ¿rst 4 terms, but multiplied by 2.
Since 3 is a prime, the only way we will get a zero is when we multiply by
zero. This argument will work for prime divisors only. But we have proven
that if a prime p divides Fn , then p divides F2 n , F3n , and so on.
Now let’s focus on useful tools involving algebraic sums. The mother of all
tools is telescoping. Sometimes we can take a sum and perturb it so that
most of the new terms cancel with the old terms. Here is an example of a
geometric series.
S a ar ar 2 ar 3 ar 4
rS ar ar 2 ar 3 ar 4 ar 5
S rS a ar 5
S (1 r ) a ar 5
In other words, S(1 í r) turned the sum into a telescoping series. We can
extend this to in¿nite geometric series, as long as r is less than 1 in absolute
value. As n grows, the limiting value will be S a / (1 r ) .
The massage tool is less common than telescoping but quite powerful. It
says, feel free to mess around with an expression to make it simpler for your
particular context; do not worry if you have altered its value a little. Let’s
work an example: The harmonic series is the in¿nite sum 1 + 1/2 + 1/3 +
1/4 + 1/5 + … . Does it converge or diverge? We will prove divergence by
showing that we can make the sum arbitrarily large if we go out far enough.
• Thus, 1/3 + 1/4 1/4 + 1/4 (which equals 2/4, which simpli¿es
to 1/2).
27
• Likewise, 1/5 + 1/6 + 1/7 + 1/8 1/8 + 1/8 + 1/8 + 1/8 (which
equals 4/8 and simpli¿es to 1/2).
• Hence if we look at the terms from 1/9 to 1/16, there are 8 terms,
each at least as large as 1/16, so their sum is at least 8/16 = 1/2.
• Likewise, the sum of the 16 terms from 1/17 to 1/32 is at least 1/2.
1
1 .
1
1
1
1
1 %
Lecture 5: Closing the Deal—Proofs and Tools
In general, in¿nite processes such as sums and fractions are de¿ned by looking
at the ¿nite version and considering what happens when they converge. Get
your hands dirty: Compute successive fractions. We get 1, 2, 3/2, 5/3, 8/5,
and so on. Conjecture: These are quotients of successive Fibonacci numbers.
We compute the limiting value using the creative substitution tool. Let x
equal the whole limiting value. Then x = 1 + 1/x. The quadratic formula
1 5
yields , which is approximately 1.6803. This number is known as the
2
golden ratio, and it is ubiquitous in mathematics. Ŷ
28
Suggested Reading
Questions to Consider
29
Pictures, Recasting, and Points of View
Lecture 6
I
n this lecture, we explore 3 strategies: draw a picture, change your point
of view, and recast your problem. We begin with proofs without words;
then explore the amazing utility of the simple distance-time graph; and
next move on to harder problems, where the crux idea is the discovery of
the natural point of view. We will look at an example where the problem is
geometric, at least on the surface, but cannot be solved until we turn it into a
logic puzzler.
Let’s begin with an example that makes strong use, as many pictorial
problems do, of symmetry: Prove that if T is a triangular number then 8T + 1
will be a perfect square.
Lecture 6: Pictures, Recasting, and Points of View
• But why is it true? It is not too hard to prove using algebra, but it is
more fun to use pictures.
Let’s switch gears to a pure word problem, one with no obvious picture. Pat
works in the city and lives in the suburbs with Sal. Every afternoon, Pat gets
on a train that arrives at the suburban station at exactly 5 pm. Sal leaves the
30
house before 5 and drives at a constant speed so as to arrive at the train station
at exactly 5 pm to pick up Pat. The route that Sal drives never changes. One
day, this routine is interrupted, because there is a power failure at work. Pat
gets to leave early and catches a train that arrives at the suburban station at
4 pm. Instead of phoning Sal to ask for an earlier pickup, Pat decides to get
a little exercise and begins walking home along the route that Sal drives,
knowing that eventually Sal will intercept Pat and make a U-turn, and they
will head home together in the car. This is indeed what happens, and Pat
ends up arriving at home 10 minutes earlier than on a normal day. Assuming
that Pat’s walking speed is constant, that the U-turn takes no time, and that
Sal’s driving speed is constant, for how many minutes did Pat walk?
Every problem has a natural point of view; you need to ¿nd it. If a problem
is hard, perhaps you need a new point of view. What is the ¿rst time after
noon at which the hour and minute hands meet? This is an amusing and
moderately hard algebra exercise. However, this problem can be solved in
a few seconds in your head if you avoid messy algebra and just consider
the natural point of view. Don’t use a ¿xed frame
of reference. Instead, look at it from the point of
view of the hour hand. At noon, it coincides with The most common
the minute hand. Then, after somewhat more form of recasting
than an hour, the minute hand visits it again!
is between algebra
How long until the next visit? The same amount and geometry.
of time, of course! From the point of view of
the hour hand, nothing has changed from the
situation at noon! Clearly there will be 11 meetings between noon and
midnight, so the time between meetings is exactly 12/11 of an hour. The ¿rst
meeting after noon is at 1:05:27.18.
31
rate of speed. As the swimmer passes under the bridge, a bystander tells her
that her hat fell into the river as she originally dived. The swimmer continues
downstream at the same rate of speed, catching up with the hat at another
bridge exactly 1 mile downstream from the ¿rst one. What is the speed of the
current in miles per hour?
Look at things from the hat’s point of view. The hat thinks that it is sitting
still in the water. From its point of view, the swimmer abandoned it and then
swam away for an hour at a certain speed (namely, the speed of the swimmer
in still water). Then the swimmer turned around and headed back, going at
exactly the same speed, since the current is always acting equally on both hat
and swimmer. Therefore, the swimmer retrieves the hat exactly 1 hour after
turning around. The whole thing took 2 hours, during which the hat traveled
1 mile downstream. So the speed of the current is 1/2 mile per hour.
• But for n > 3, it gets ugly. The planets may no longer lie on a
plane, so we are forced to contemplate spherical geometry.
32
• But perhaps it is not really a geometry problem! Crux move:
Construct a universal north. Imagine that the planets lie in a
room, and thus the point on each planet that is closest to the
ceiling of the room is that planet’s north pole.
33
How did we solve the planet problem? The universal frame of reference
facilitated investigation of the relationships between private and public on
different planets. We then realized that private/public is not just a geometric
relationship but a binary logical relationship. We recast a hard geometry
problem into a relatively simple logic problem! Ŷ
Suggested Reading
Questions to Consider
1. Find a “proof without words” that the sum of the ¿rst n positive odd
integers is equal to n 2 .
2. Sonia walks up an escalator that is going up. When she walks at 1 step
per second, it takes her 20 steps to get to the top. If she walks at 2 steps
per second, it takes her 32 steps to get to the top. She never skips over
Lecture 6: Pictures, Recasting, and Points of View
34
The Great Simpli¿er—Parity
Lecture 7
Any time you have a situation of mutuality, where you might have 2
players, in some sense, connected by some relationship, there should be
a nice systematic way of analyzing it. ... There’s a branch of mathematics
designed for handling these situations, called graph theory.
P
arity is such an important tactical idea that we devote most of this
lecture to it. Parity analysis helps to solve problems because it
allows us to reduce the possibly in¿nite complexity of a situation to
just 2 states. We apply parity to a number of diverse problems involving
information Àow, changing con¿gurations, and maps of countries. We also
introduce a topic that will recur several times in this course: graph theory,
the study of networks.
35
The prisoners are allowed to chat for a few minutes before their
ordeal begins. What is the largest number of prisoners that can be
guaranteed to survive?
36
• If a number is rational, then it can be expressed as a fraction in
simplest form, in which case the numerator and denominator cannot
both be even.
• So a 2 / b 2 2 , or a 2 2b 2 .
The next problem, the locker problem, we will not solve completely in
this lecture.
37
• A simple investigation quickly leads to the conjecture that
squares remain closed.
The next problem comes from the Bay Area Mathematical Olympiad. A
lock has 16 keys arranged in a 4 × 4 array, and each key is oriented either
horizontally or vertically. In order to open it, all the keys must be vertically
oriented. When a key is switched to another position, all the other keys in the
same row and column automatically switch their positions too. Show that no
matter what the starting positions are, it is always possible to open this lock.
(Only one key at a time can be switched.)
Parity can be used whenever there are just 2 states in a problem, and here
Lecture 7: The Great Simpli¿er—Parity
vertical and horizontal certainly ¿t the bill. We need to be able to change any
key, but the problem is that when we turn a single key, it changes 7 keys,
including itself. We would like to only change one key. However, if a key
is changed twice, it is as if it was never changed (odd + odd is even). We
need to ¿nd a move or sequence of moves that changes lots of keys an even
number of times but changes only one key an odd number of times. There
are not too many things to try, and a number of them work. You can check
that if you pick any speci¿c key and turn all 7 keys in its cross, this will do
the trick.
38
Here is another problem from a regional Olympiad (Colorado): If 127 people
play in a singles tennis tournament, prove that at the end of the tournament,
the number of people who have played an odd number of games is even.
Note that the tournament can have any
structure; the only restriction is that each
game requires 2 people. Parity analysis helps to
solve problems because
Suppose each person pays a dollar to the it allows us to reduce
tournament each time they play a game.
the possibly in¿nite
Each game played makes the tournament
owner $2 richer. If we add up the amount complexity of a situation
of money each person pays, it will be to just 2 states.
equal to 2 times the number of games
played, and will be even. And it is the
same as adding up the number of games each person plays. So, if there are
127 people, and we add up the number of games each person played, we
are adding 127 numbers and getting an even sum. So the number of people
who played an odd number of games is even. This problem involves mutual
relationships (playing in a game). This is a ubiquitous situation and can be
modeled in many other contexts. This leads to the abstract idea of a graph: an
entity of vertices and edges.
Suggested Reading
39
Questions to Consider
40
The Great Uni¿er—Symmetry
Lecture 8
L
ike parity, the symmetry tactic is so important that we need to spend an
entire lecture on it. Symmetry is one of the most important underlying
principles in mathematics. Symmetrical structures (geometric or
otherwise) are simpler than asymmetric structures and hence easier to
investigate. Thus, searching for symmetry—or if need be, imposing it where
it was not at ¿rst—is a powerful tactic for
investigating problems. In this lecture, we
explore symmetry not just visually but There are hundreds
also algebraically.
of proofs of the
What is symmetry? An object (which may Pythagorean theorem.
or may not be geometric) is symmetrical
if a transformation leaves it invariant. This
can take many forms. Geometric symmetry is the simplest to understand.
Objects can have rotational, reÀectional, and other symmetries. Metaphorical
symmetry is more subtle. Examples of metaphorical symmetry are the pills
problem (once the pills were balanced, the problem was almost solved); the
private planets problem (private/public duality); and the handshake lemma
(handshake is a symmetrical relation). Thus parity is, in a sense, an example
of metaphorical symmetry in action.
41
• The sum 1 + 2 + 3 + 4 + … + 100 is not symmetrical.
1 + 2 + 3 + … + 100
100 + 99 + 98 + … + 1
Symmetry is related to the search for natural points of view. Often this
point (or line, etc.) is one of symmetry. The classic 4 bugs problem is an
excellent example.
42
There are hundreds of proofs of the Pythagorean theorem. Here is a simple
one that uses the imposition of symmetry. First we reformulate a 2 b 2 c 2
into an equality of areas of squares. The sum of the areas of the 2 smaller
squares must be equal to the area of the large square.
• Start with the large square ( c 2 ) and add copies of the original
triangle, symmetrically.
• Thus, c 2 equals the area of 4 of the original triangles plus the area
of the square in the center.
• The length of this square is the equal to (a í b), and the area of one
triangle is ab/2.
Symmetry can be applied to number theory. Recall the locker problem in the
last lecture? We did not quite solve it; we need to show that an integer has
an odd number of divisors if and only if it is a perfect square (a square of an
integer). Remember, divisors include 1 and the number itself. For example,
for N = 12, pair each factor with its mate. Since 12 is not a perfect square,
each divisor has a distinct mate, different from itself.
1 × 12
2×6
3×4
1 × 36
2 × 18
3 × 12
4×9
6×6
43
These ideas also apply to algebra. Let’s use symmetry to solve the
fourth-degree equation x 4 x3 x 2 x 1 0 . This equation is nearly
“symmetrical”; we can make it more so by dividing by x 2 , getting
x2 + x + 1 + 1/x + 1/x2 = 0. We have imposed an interesting algebraic
symmetry. There is a correspondence between terms of the form x k and
terms of the form 1/ x k .This suggests a natural symmetrical substitution:
y = x + 1/x. Notice that (x + 1/x)2 = x2 + 2 + 1/x2. So our equation now
becomes y 2 2 y 1 0 , a quadratic equation that can be solved by
the quadratic formula. Then we can solve for x, again using the quadratic
formula! Once again, imposing symmetry was the key. Ŷ
Suggested Reading
Questions to Consider
2. The set {1, 2, 3, 4, 5, 6} has 64 subsets, including the empty set and
the set itself. For how many of these subsets is the sum of the elements
greater than 10?
44
Symmetry Wins Games!
Lecture 9
T
his is our ¿rst applied lecture, where we focus more on using
problem-solving ideas than on developing new ones. We study
combinatorial games, which apply literal and metaphorical symmetry.
Our cornerstone is Wythoff’s Nim, which is an absurdly easy game that is
amazingly hard to play well, until you use symmetry and a few other ideas.
It is also one of the many mathematical phenomena in which the Fibonacci
numbers and the related golden ratio play an important role.
All combinatorial games have the same basic structure: Two players, A and
B, alternate taking turns. A goes ¿rst. The game ends when no legal moves
can be made. The last person to make a legal move wins. Our goal: Given a
game, discover the winning strategy.
• The get your hands dirty and make it simpler strategies compel
us to change the 17 to smaller values, such as 1, 2, 3, and
so on.
45
• Looking at these simpler games shows us that if you are left with
5, no matter what you do, your opponent will win on the next
move. So if you can present your opponent with 5, you win.
• The pattern clearly continues. Let us call the values 0, 5, 10, 15,
… the oases and the other values the desert. If you move to an
oasis value, your opponent must move to a desert value. If your
opponent moves to a desert value, you can always move to an
oasis. Thus, if a player moves to an oasis, he or she can control
the game, always moving to oases and forcing the opponent to
stay in the desert—until the end, when the lucky oasis traveler
moves to the ¿nal oasis value, 0, and wins the game.
• Start with the value 0. Assume that you have gotten there
(wishful thinking), so you have won. Color this value green.
• The next value, 5, has not been colored yet; it is colored green.
• Notice that from this green value, one can only move to
red values, and from there, one can always move to another
green value.
46
• Continuing, we color red the next values that in one move can
get to green. We continue this recursive process inde¿nitely.
• One possible game: Start with 100. Player A’s moves are
bolded: 98, 97, 96, 48, 24, 21, 14, 7, 6, 4, 2, 1. Hence B wins.
47
• So the winning strategy is this: A subtracts an odd from 100
and thereafter keeps presenting odd numbers to B. In general, A
can always win if the starting number is even, and B can always
win if the starting number is odd.
The next game, which I call cat and mouse, also relies on parity and
symmetry. A very polite cat chases an equally polite mouse. They take turns
moving on a grid. Initially, the cat is at the point labeled C; the mouse is at
M. The cat goes ¿rst and can move to any neighboring point connected to it
by a single edge. Thus the cat can go to points 1, 2, or 3, but no others, on its
¿rst turn. The cat wins if it can reach the mouse in 15 or fewer moves. Can
the cat win?
At ¿rst, it seems impossible; the mouse can always be one step away from
the cat. If you look carefully at the grid, you will discover that it contains
only rectangles glued together, with one triangle at the top left. Temporarily
pretend that the triangle is not there (make it easier). Then we can color
the vertices with alternating colors, like a chessboard. Let the cat’s starting
position be blue. Notice that the mouse’s starting color is also blue. So if
we ignore the triangle, the cat moves from blue to red. Then the mouse
moves from blue to red. Then the cat moves from red to blue, and the mouse
follows suit. The cat and mouse are always on same-colored vertices, so it is
impossible for the cat to make a single move
Lecture 9: Symmetry Wins Games!
48
for if it did, you would have a chain of dance partners: B G B G B, and then
B is connected to B.
Our ¿nal game is called Wythoff’s Nim, a.k.a. “puppies and kittens.” Start
with a pet shelter with, say, 10 puppies and 7 kittens. A and B alternate turns
adopting animals. On each turn, you must adopt at least one animal, and you
must only adopt one kind of animal, unless you adopt equal numbers of both
kinds. As always, the winner is the one who makes the last legal move—in
this case, the one who clears out the pet shelter. We can use the oasis/desert
analysis method to quickly build up a repertoire of oasis positions that will
make us unbeatable.
• Here is a list of oases (leaving out symmetrical pairs): (1, 2), (3, 5),
(4, 7), (6, 10), (8, 13).
• This eliminates all other ordered pairs with difference of 1 and with
either p or k equal to 1 or 2.
• The next one after that must be (4, 7), and so on. Ŷ
49
Suggested Reading
Berlekamp, Conway, and Guy, Winning Ways for Your Mathematical Plays.
Gardner, Penrose Tiles to Trapdoor Ciphers, chap. 8.
Questions to Consider
1. Modify the takeaway game so that the last penny is “poison,” and the
person who takes this penny away loses.
50
Contemplate Extreme Values
Lecture 10
We’ll look at several interesting examples, and in each case, the problem
is generally rather dif¿cult until we use the extreme principle. When we
use the extreme principle, the problem becomes nearly trivial.
T
his lecture focuses on an incredibly productive but little known (by
laypeople) tactic that simply advises one to contemplate the extremal
values in a problem. For example, look at the triangle of least area, the
largest variable, or the ¿rst time something occurs. This tactic has the nearly
magical ability to solve hard problems in a line or 2. I have often compared
expert use of the extreme principle to watching a martial artist break a board,
something that looks impossible yet effortless to the uninitiated.
How do you apply the extreme principle? Put your things in order,
contemplate the largest and/or smallest of these things, and be creative about
just what a thing is and how to measure it.
Here is a warm-up example: There are ¿nitely many points in the plane,
colored red or blue. Between any 2 red points, there is a blue point on the line
segment connecting them. Between any 2 blue points, there is a red point on
the line segment connecting them. What
kinds of con¿gurations are possible?
Sometimes the hardest
thing about an extreme Investigation yields the conjecture that
the only con¿gurations are linear, with
principle problem is points alternating colors. But how do
¿guring out which entity we prove this rigorously? Assume to the
should be contemplated. contrary that there is a 2-dimensional
con¿guration. Consider the triangle of
smallest positive area. Two vertices of
this triangle must be the same color, forcing a point to lie between them; this
creates a smaller triangle, which contradicts the minimality of the triangle.
So a 2-dimensional con¿guration is impossible!
51
Here is a problem from the Canadian Mathematical Olympiad: On a large,
Àat ¿eld, n people (n > 1) are positioned so that for each person, the distances
to each of the other people are different. Each person holds a water pistol and
at a given signal ¿res and hits the person who is closest. When n is odd, show
that there is at least 1 person left dry. Is this always true when n is even?
• If n is odd, there must be at least some people whose victims are not
shooting them.
• Consider the person among these who shoots the furthest distance.
52
• But how do we prove it?
• Continue until only 2 people are left, me and the person who
shook hands with 10 people.
How do you quantify network diversity? Look at the edges. The crux idea is
to maximize balanced edges! Given any ¿xed network, there are only ¿nitely
many ways to color the vertices. For each coloration, count the number of
balanced edges. Find the coloration with the greatest number of balanced
edges. This will be a diverse network!
How do we know this? Assume, to the contrary, that this network is not
diverse. Then there is a “bad” vertex. Change its color! This produces a
new coloration, with more balanced edges. But this is impossible! We have
created our contradiction. Ŷ
53
Suggested Reading
Questions to Consider
2. Suppose you are given a ¿nite set of coins in the plane, all with
different diameters. Show that one of the coins is tangent to at most 5 of
the others.
Lecture 10: Contemplate Extreme Values
54
The Culture of Problem Solving
Lecture 11
W
e take a brief detour from solving mathematics problems to
look at problem solving as a cultural force. In Eastern Europe,
mathematics has long been respected, even among children, and
math contests play a role not unlike sports in the United States. We look at
the history of the Mathematical Olympiad culture and assess whether this
culture has a chance of taking root in the United States. I will draw upon my
experiences as a member of the ¿rst U.S. team to compete in the International
Mathematical Olympiad; my later career as a coach, problem writer, and
editor for these and other contests; and my current efforts to make the
San Francisco Bay Area become more like Bulgaria—at least with respect
to mathematics.
The culture of math circles, math contests, and math nerds (“nerd” is not a
pejorative) is a world where excellence in math is a social bene¿t and where
math contests are as popular as sports contests are in the United States. This
culture exists, but it is rare, both in space and time. Its roots are primarily
Eastern European. My ¿rst introduction to this culture was as a student at
Stuyvesant High School in New York, one of several specialized schools for
math and science. Unique features of this school included social acceptance
of intellectual achievement and opportunities for independent study with
teachers with doctorates.
Why did this culture Àourish in Eastern Europe? Mathematics and physics
were ways to escape totalitarianism. More intellectuals were drawn to math
and physics than in Western democracies. And the state rewarded scientists
with of¿cial status.
55
What is a math circle? The word “circle” is a direct translation of the
Russian word kruzhok. Math circles are like math clubs on steroids. They
are highly intensive and feature interaction with college and graduate
students, professors, and world-famous research mathematicians. The
curriculum is based on problem solving, and there is a deliberate effort to
transmit the folklore of problem solving. Most math circles are linked with
math competitions.
Here is a brief and incomplete history of these contests. The ¿rst modern one
was the Hungarian Problems, which began in 1906. The Moscow Olympiads
began in the 1930s. The International
Mathematical Olympiad began in 1959. At
¿rst, its participants were only Iron Curtain The important thing
countries, but gradually it has become more
about this culture
inclusive. The United States ¿rst participated
in 1974, and today nearly 100 nations is that it celebrates
participate. The style of these math contests is intellectual inquiry
unusual. In the United States, many exams are and intensity and
still multiple choice, but the Olympiad style is encourages passion
always essay-proof.
for investigating
How did this culture migrate to the United mathematics.
Lecture 11: The Culture of Problem Solving
Let’s look at the “math nerd culture.” There are now quite a few specialized
schools. There are also several summer camps devoted to mathematical
folklore transmission. There are online communities and an international
nerd culture that features T-shirts, frisbees, silly word games, and fetishistic
memorization of numbers such as ʌ. Famous mathematicians visit math
camps and clubs, and such luminaries become worshipped. The important
thing about this culture is that it celebrates intellectual inquiry and intensity
and encourages passion for investigating mathematics. Ŷ
56
Suggested Reading
57
Recasting Integers Geometrically
Lecture 12
This and the next lecture focus on number theory, the study of the
integers. We’ve seen a little number theory so far in earlier lectures, but
now that we understand basic strategies and tactics, we can go deeper.
T
his lecture focuses on the chicken nuggets problem, a classic folklore
puzzle that originated in England over a century ago and is now a
mainstay of math clubs around the world. This rich problem can be
analyzed with induction, pictures, symmetry, careful counting principles, and
other approaches. We focus here on a visual approach, recasting the problem
into one of counting lattice points, with symmetry playing a key role.
The fundamental objects that we will be exploring are lattice points: the
points (x, y) on the coordinate plane, where both x and y are integers. By
contemplating lattice points as natural objects, we can convert algebraic
questions involving natural numbers into geometric questions, and
vice versa.
Lecture 12: Recasting Integers Geometrically
Bay Area Rapid Foods sells chicken nuggets in boxes of 7 and boxes
of 10. A number n is feasible if it is possible to buy n nuggets. For
example, 7 is the smallest feasible number, and the next ones after
that are 10, 14, 17, 20, 21, and 24. There are 2 natural questions.
58
The values 7 and 10 are probably not critical; we should look at
smaller, simpler values and try to get a general picture. In other
words, given positive integers a and b, if nuggets come in boxes of
size a and size b, what is the largest nonfeasible number, and how
many nonfeasible numbers are there?
• Feasible: 5, 7, 10, 12, 14, 15, 17, 19, 20, 21, 22, 24, 25, 26, 27,
28. It is clear that all values starting with 24 are feasible (since
5 in a row are).
59
Can we ¿nd a visual interpretation?
• If a and b are relatively prime, then a line with slope a/b either
has no lattice points on it or hits lattice points in a systematic
way, with each lattice point separated from the next by the
same vector.
• One solution is (5, í2). All solutions are separated by the vector
(í7, 5). Remember that there are no lattice points on the dotted
line between the 2 lattice points.
60
Breakthrough idea: Let’s change our point of view and count lattice
points, not feasible or nonfeasible numbers!
61
Suggested Reading
Questions to Consider
2. Suppose you accept on faith that Pick’s theorem is true for triangles.
How can you use this to prove that it is true for all polygons?
Lecture 12: Recasting Integers Geometrically
62
Recasting Integers with Counting and Series
Lecture 13
Like the last lecture, what we’re presenting here is pretty dif¿cult
mathematics. We’ll prove Fermat’s little theorem, which is one of
the most important theorems of elementary number theory, but
we’re going to prove it in a way that was not found in most number
theory textbooks.
T
his lecture employs the powerful strategies of recasting and rule
breaking to 2 classical theorems in number theory: Euler’s proof
of the in¿nitude of primes and Fermat’s little theorem. We use the
knowledge of modular arithmetic and in¿nite series that we developed
earlier. We begin by using simple counting ideas to explore number theory,
using the basic principle that if something can be counted, it is an integer.
Let’s go back, for a moment, to the earlier lecture about chicken nuggets. If
you were really, really observant, you may have noticed a gap in our argument.
We associated each lattice point with either a feasible or nonfeasible number.
But we blithely assumed for each number n that the equation ax + by = n
must pass through lattice points. How
do we know if it does? In other words,
We begin by using given relatively prime numbers a and b
simple counting ideas to and an integer n, can we be guaranteed
explore number theory, that there are integers x and y such that
ax + by = n?
using the basic principle
that if something can be We only need to consider n = 1. If we
counted, it is an integer. can ¿nd a solution for that, we can easily
get one for n = 2 and so on. A concrete
example: Show that 5x + 7y = 1 has
integer solutions. We will ¿nd a result that can easily be generalized to any
values of a and b. We count lattice points. For each integer n, the equation
5x + 7y = n determines a line with slope í5/7. As n ranges from 0 to 35, we
get a family of 36 parallel lines. Notice that if a line intersects one of the
63
lattice points, it will not intersect another. So each lattice point corresponds
to a different line. Thus, we just need to count the lattice points. They are
arranged in a parallelogram, but we can move the bottom points up. By
symmetry, we get a rectangle, and clearly there are 7 × 5 lattice points. Each
of the 35 lines for n = 0 to n = 34 hits a lattice point. So the n = 1 line hits a
lattice point, and we are done.
We can exploit the idea of counting in many other ways. Combinatorics has
its own logic and rules, which are pretty simple, at the start. Let’s look at
Fermat’s little theorem. We begin with an example: Find the remainder when
21000 is divided by 13. We can use modular arithmetic to solve this.
• This is the crux move, since now we can raise this to any
power we want with ease. Since 1000 = 12(83) + 4, we have
(212 )83 183 1 (mod 13).
The crux was ¿nding the exponent of 2 that equals 1 (mod 13). On the other
hand, if we try a nonprime mod, like (mod 10), we discover that the powers
of some numbers are never equal to 1 (mod 10), and for others we get 1, but
never when we raise to the ninth power. The sensible conjecture to try is that
if p is prime, then a p 1 = 1 (mod p) for any number that is not a multiple of p
itself. This is Fermat’s little theorem. We will prove this, but ¿rst we modify
the statement by multiplying both sides by a: a p a (mod p).
64
Let’s replace number theory with combinatorics. We will prove Fermat’s
little theorem for the concrete values p = 7 and a = 4 and demonstrate
that 47 4 is a multiple of 7 using simple counting principles. Imagine a
necklace with 7 identical beads. We wish to color them using any of 4 colors.
How many different necklaces are possible? Let’s make it easier. If it were
not a necklace but just a line of beads, then the number of different necklaces
would be 4 × 4 × 4 × 4 × 4 × 4 × 4 = 47 . That is promising, since it is a
number we are interested in. But since we have a necklace, we can slide
beads around. In fact, there will be 7 different linear sequences of colors that
are all really the same necklace.
Indeed, almost any linear color sequence is 1 of 7 “sisters” that form the same
necklace. In other words, each linear sequence is in a 7-member sorority.
The only exceptions are the 4 monochromatic sequences. These 4 sequences
belong to exclusive sororities: Each sorority has just 1 member. Notice that
we are using the fact that 7 is prime. If we had a 6-bead necklace, then the
pattern black-red-black-red-black-red would only give rise to 2 sisters. We
started with 47 linear color sequences. Of these, just 4 were monochromatic.
The remaining 47 4 sequences can be grouped into 7-member sororities
where each sorority member is actually the same necklace. So the total
number of different necklaces is ( 47 4 )/7 + 4. So 47 4 had to be a
multiple of 7, which was what we wanted to prove!
For our ¿nal example, we will give a second proof of the in¿nitude of primes,
due to Euler, that is notable for its surprise use of in¿nite series. We start
with the harmonic series, which is in¿nite.
1 1
• De¿ne Sk 1 " , and consider the in¿nite product
k k2
S2 S3 S5 S7 " , where the subscripts run through the prime numbers.
1 1 1 1
• The in¿nite product begins with (1 ")(1 2 " )
2 22 3 3
1 1
(1 2 ") … .
5 5
65
• When we expand this in¿nite product, it will give us each term of
the harmonic series; hence it is in¿nite.
• Now, assume to the contrary that there are only ¿nitely many
primes. Then there are only ¿nitely many Sk terms in our product.
That would make the harmonic series ¿nite. But it is in¿nite!
So there must be in¿nitely many Sk terms and hence in¿nitely
many primes! Ŷ
Suggested Reading
Questions to Consider
Lecture 13: Recasting Integers with Counting and Series
1. Use Fermat’s little theorem to ¿nd the remainder when 32009 is divided
by 19.
2. How many different necklaces can be made using 6 beads, if each bead
is a different color?
66
Things in Categories—The Pigeonhole Tactic
Lecture 14
L
ike the extreme principle, this tactic seems almost vacuous: If you try
to put n + 1 pigeons into n pigeonholes, at least 1 hole will contain
at least 2 pigeons. Yet the pigeonhole principle allows us to solve an
amazing variety of problems. Among the applications we will explore is a
graph theory subject known as Ramsey theory, which provides a systematic
way of ¿nding patterns in seemingly random structures.
• Let the vertices be pigeons, and the colors be holes. Since 3 > 2,
there is a hole with at least 2 pigeons.
67
• People are the pigeons, but what are the holes?
• So at least 2 of them are the same distance from their correct dish.
A third example: Prove that among any group of people, 2 of them have the
same number of friends in the group.
Lecture 14: Things in Categories—The Pigeonhole Tactic
• Wishful thinking and the extreme principle tell us that there must be
a way to get rid of at least 1 degree value.
68
• Conversely, if a vertex has degree 5, it is connected to all other
vertices, so no vertex can have degree 0.
• Thus the possible degree values are between 0 and 5, inclusive, but
cannot include both 0 and 5. So there are only 5 possible values,
and with 6 vertices, we can conclude that 2 vertices must have the
same degree!
Here is a classic example: Show that among any 6 people, either 3 of them
are mutual friends, or 3 are mutual strangers. Graph theory recasting: If you
2-color the edges of a complete graph with 6 vertices, then there must be
a monochromatic triangle! Use green and red. We want to see lots of one
color, since that would make it more likely to get a monochrome triangle.
The extreme principle suggests that we search for the vertex that has, say, the
maximum number of red edges emanating from it. The pigeonhole principle
gives us that maximum: Each vertex has 5 edges emanating from it. At least
ǻ5 / 2 ȼ 3 edges are the same color (say, red). Focus on the vertex we started
with plus the 3 others that are joined to it with a red edge. If any of these 3
vertices are joined with a red edge, we are done. But if none of them are red,
we have created a green monochromatic triangle.
69
Let’s generalize this problem. We just showed that if the edges of a K 6 are
2-colored, then there must be a monochromatic triangle. The Ramsey number
formulation of this is R(3, 3) = 6. The Ramsey number R(a, b) is de¿ned to
be the smallest number N such that if the edges of a K N are colored blue
and red, then there must be a red K a or a blue K b . Ramsey numbers can
use more than 2 colors. For example, R(3, 3, 3) is equal to the smallest N
such that if you 3-color the edges of a K N , you must have a monochromatic
triangle. Ramsey’s theorem states that the numbers R(a, b, c, … ) exist and
are ¿nite. Example: R(3, 3, 3), the only nontrivial Ramsey number known
involving more than 2 colors, is equal to 17. Ŷ
Suggested Reading
Questions to Consider
1. Given a unit square, show that if 5 points are placed anywhere inside or
2
on this square, then 2 of them must be at most units apart.
2
2. People have at most 150,000 hairs on their head. How many people must
live in a city in order to guarantee that at least 10 people have exactly
the same number of hairs on their head?
70
The Greatest Uni¿er of All—Invariants
Lecture 15
I
nvariants are central to mathematics, yet most laypeople have never
heard of them. In this lecture, we show how the concept of invariants
contains both symmetry and parity. We tweak it to look at monovariants
and use these to study some interesting games. We also continue our study of
modular arithmetic, which we now see is merely a special case of the grand
unifying principle of invariants.
These 2 theorems seem like related results about intersecting lines and
circles, but in fact they are actually manifestations of a single fact. For any
¿xed point P and any ¿xed circle, draw any line through P that intersects
the circle in points X and Y. De¿ne the power of P to be the quantity (PX)
(PY). The power of a point theorem says that for any ¿xed circle and any
¿xed point, this quantity is invariant, no matter which line we choose. This
invariant formulation is true no matter where the point is located.
71
The Hotel Room Paradox
• The question is not what happened to the dollar, but how do the
variables relate to one another? What is invariant?
• The money the guests paid is equal to the amount that the
hotel received (“hotel” means the porter and the desk). In other
words, if g, p, and d are respectively equal to what the guests
pay, what the porter pockets, and what the desk receives, then
Lecture 15: The Greatest Uni¿er of All—Invariants
72
Here is another classic puzzler: Bottle A contains a quart of milk, and bottle
B contains a quart of black coffee. Pour a half-pint of coffee from B into A,
mix well, and then pour a half-pint of this mixture back into bottle B. What
is the relationship between the fraction of coffee in A and the fraction of milk
in B? It is possible to do this with algebra, and when we do so, we discover
the surprising fact that the fraction of coffee in A is equal to the fraction
of milk in B. But this can made obvious once we think about invariants.
The coffee and milk both satisfy conservation of mass (really, volume). So if
bottle A has x ounces of coffee “pollution,” then
bottle B is missing x ounces of coffee and thus
A monovariant
has x ounces of milk pollution. Both bottles are
is a quantity that equally polluted.
changes, but only
in one direction. Here is an example using a parity invariant:
Let a1 , a2 , } , an represent an arbitrary
arrangement of the numbers 1, 2, 3, … , n. Prove
that if n is odd, the product (a1 1)(a2 2)" (an n) is even. First, we give
a solution that uses a pigeonhole argument. An alternative solution uses
invariants. Given any permutation a1 , a2 , } , an , observe that the quantity
(a1 1) (a2 2) " (an n) is invariant; namely, equal to zero! Thus the
terms in the product we are interested in add up to zero, and there are an
odd number of them. Clearly, they cannot all be odd, since a sum of an odd
number of odd numbers is always odd, and zero is even. So one term must
be even.
73
A monovariant is a quantity that changes, but only in one direction.
Monovariants are useful for studying evolving systems. Here is a simple
example (due to John Conway), called Belgian wafÀes. Two people take
turns cutting up a wafÀe that is 6 squares × 8 squares. They are allowed to
cut the wafÀe only along a division between the squares, and cuts can be only
straight lines. The last player who can cut the wafÀe wins. Is there a winning
strategy for the ¿rst or second player? This is actually a fake game. There
is no strategy because of this simple monovariant: Each move increases the
number of pieces by 1! You start with 1 piece (the whole wafÀe), so the
game ends in 47 moves no matter what the players do!
The next problem illustrates the power of monovariants to cut through the
complexity of evolving systems. At time t = 0 minutes, a virus is placed into
a colony of 2009 bacteria. Every minute, each virus destroys 1 bacterium,
after which all the bacteria and viruses divide in 2. For example, at t = 1,
there will be 2008 × 2 = 4016 bacteria and 2 viruses. Will the bacteria be
driven to extinction? If so, when will this happen? There are complicated
algebraic formulas that will do the trick, but monovariants are a better way.
Let b and v be the respective populations at a certain time, and let bƍ and
vƍ be the populations 1 minute later. It is easy to see that bƍ = 2(b í v) =
Lecture 15: The Greatest Uni¿er of All—Invariants
bc 2b 2v b
1 .
vc 2v v
Suggested Reading
74
Questions to Consider
1. A graph that can be drawn so that edges do not cross is called a planar
graph. For example, a typical picture of a K 4 has the 2 diagonal edges
crossing, but it is possible to draw this graph where one diagonal is
“inside” and the other is “outside,” so that K 4 is planar. Given any
planar graph, it is easy to count the number of vertices (v), edges (e),
and regions bounded by edges (r). Discover an invariant involving
these variables.
2. Can you ¿nd distinct integers a, b, and c such that a í b evenly divides
b í c, b í c evenly divides c í a, and c í a evenly divides a í b?
75
Squarer Is Better—Optimizing 3s and 2s
Lecture 16
O
ur anchor problem is an International Mathematical Olympiad
problem about a maximal product: Determine, with proof, the
largest number that is the product of positive integers whose sum is
1976. Intuition may tell us to try a square: 988 × 988 = 976,144. But we can
do better. For example, 987 × 987 × 2 = 1,948,338. Clearly we need more
investigation! First, let’s consider simpler, more constrained questions.
76
A reformulation of this is the 2-dimensional arithmetic-geometric mean
inequality (AM-GM): If x and y are nonnegative, then (x + y)/2 t xy , with
equality attained when x = y. The AM-GM is also true in higher dimensions.
For example, in 3 dimensions, the statement is
(x + y + z)/3 t 3 xyz , which is very hard to
But a better way prove using algebra alone. The 2-dimensional
to prove this AM-GM is not too hard to prove with algebra. It
squarer-is-better is equivalent to ( x y ) 2 t 0 , which is certainly
always true. But it is hopeless to prove the general
principle is with
n-dimensional AM-GM with algebraic methods.
a picture.
However, we can use the 2-dimensional
squarer-is-better principle to prove AM-GM in
any dimension if we leave algebra behind and instead view the problem in
terms of physics. The original formulation for n variables is as follows:
77
• There are 2 dif¿culties: We are not told how many numbers are in
the product. And even if we were, we could not guarantee that the
values would be integers if we made them all equal.
• Next, notice that if you have three 2s, you can replace them
with two 3s.
• So that gives us the optimal breakdown: all 3s, unless you have
Lecture 16: Squarer Is Better—Optimizing 3s and 2s
to have some 2s, but never more than two 2s. For example, 12
breaks into 3 × 3 × 3 × 3, but 13 gives us 3 × 3 × 3 × 2 × 2.
Suggested Reading
78
Questions to Consider
1. If you have a ¿xed length of wire and you are to make a rectangle of
maximum area, you know that a square is optimal. But what if one side
of your rectangle is already provided? For example, suppose you are
building a rectangular fence, one of whose sides is a river? What will
the optimal dimensions be? (Hint: symmetry.)
79
Using Physical Intuition—and Imagination
Lecture 17
This lecture, like the earlier one about games, does not attempt to
teach you new problem-solving strategies or tactics. Instead, we will
look at a few problems in depth and use methods that we’ve already
seen. Our goal is to continue to reinforce the all-important ideas of
symmetry, but now we’ll add its “mother,” invariance, now that we’ve
learned something about that. In particular, we will channel our
intuition about the so-called “real world” to use physical invariants to
solve a problem.
T
his lecture is inspired by a problem that I proposed for the USA
Mathematical Olympiad only to ¿nd out that a variant of it had been
used for years as a job interview question for a hedge fund. This
challenging problem about marbles on a track combines much of what we
have studied: invariants, symmetry, drawing pictures, and getting your hands
Lecture 17: Using Physical Intuition—and Imagination
dirty. Notably, we use physical intuition to get to the heart of the problem.
80
This is a challenging problem, and we need a good venue for investigation.
The geometry of the circle is irrelevant; only the fact that there is no beginning
or end is important. Hence the following warm-up, Martin Gardner’s classic
airplane problem. Several planes are based on
a small island. The tank of each plane holds
just enough fuel to take it halfway around the We use physical
world. Fuel can be transferred from the tank intuition to get to the
of 1 plane to the tank of another while the heart of the problem.
planes are in Àight. The only source of fuel is
on the island, and we assume that there is no
time lost in refueling either in the air or on the ground. What is the smallest
number of planes that will ensure the Àight of 1 plane around the world on a
great circle, assuming that the planes have the same constant speed and rate
of fuel consumption and that all planes return safely to the base?
81
• A now has enough fuel to get to within 2 units of the
destination. As soon as B returns to base (when A has
reached the halfway point, with 2 units of fuel left), B
refuels and heads for A’s location (traveling backward
this time).
• Notice how the second half of the story is symmetrical with respect
to the ¿rst.
beam will bounce off the 2 line segments (including the ¿rst bounce,
at C).
• Instead of the actual laser path, look at the straight line. We merely
need to count the number of times it intersects the boundary of one
of the reÀected mirrors. Answer: 6 bounces. Ŷ
82
The Marbles on a Track Problem, Solved
This explains why the ¿nal positions of the marbles must coincide
with the original positions, up to a permutation. Which permutations
are possible? Remember that marbles cannot actually pass through
one another, so the order of the marbles cannot change. All that can
happen is a cyclic permutation. How do we predict the permutation?
If we started with 6 balls, there are 6 possible permutations.
However, there are 2 × 2 × 2 × 2 × 2 × 2, which equals 64, different
choices of initial orientation for the balls. How do these orientations
inÀuence the ¿nal result?
83
Suggested Reading
Questions to Consider
2. Imagine a laser beam that starts at the southwest corner of a square and
moves northeast with a slope of 7/11. How many times will it bounce
before it returns to its starting point?
84
Geometry and the Transformation Tactic
Lecture 18
T
his is the only lecture in the course wholly devoted to geometry. We
look at geometric transformation, a great example of the problem-
solving strategy of reversing one’s point of view. We apply this idea
to a number of problems that initially appear completely intractable but
become almost trivial once we are comfortable with dynamic entities like
rotations, vectors, and reÀections.
85
In our exploration of the algebra of transformations, we restrict our attention
to the plane and look at just 3 types of transformations: reÀections, rotations,
and translations. Let’s look at the composition of reÀections: Let Fh denote
a reÀection across line h. Note that Fh leaves all the points of h invariant.
In general, the ¿xed points of a reÀection are a line. When composing 2
reÀections, there are 3 cases: The lines are the same, parallel, or meet in a
single point.
• Now consider this rotation, but let line A 3 go along for the ride!
By using parts of the ¿gure and the knowledge that the rotation moved one
point of the unknown triangle to another unknown point, we were able to
construct the location of both points! Now we are ready to understand the
composition of 2 rotations. No matter where the centers are, the composition
is just another rotation about this center, where the angle is just the sum
of the 2 angles. But if the angles for 2 rotations add up to 360°, then the
composition of the 2 rotations is a translation. This is an unexpected but
helpful fact that is the tool we need for the pentagon problem. Let’s call it the
reÀection-translation tool.
86
Now let’s use this tool to solve the pentagon problem that we began our
lecture with.
• So it is a translation!
• The line segment joining P1 and P6 has the same length as the
mystery side AB of our pentagon. Draw a line parallel to this
segment that goes through X, and mark off equal segments on either
side of X whose length is half of AB. We have just reconstructed
segment AB!
87
Why did it work? The higher-level reason for this is that we did not use
the transformations randomly, but instead searched for transformations that
leave parts of our problem invariant. Ŷ
Suggested Reading
Questions to Consider
88
Building from Simple to Complex with Induction
Lecture 19
Induction has its own context. Inductive proofs usually involve problems
that involve evolving structures that build upon simpler structures or
problems that have recurrence, for example, the recurrence relation
de¿ning the Fibonacci numbers.
M
athematical induction is the natural way to prove assertions that are
recursive, that is, where simpler cases evolve into more complex
cases that depend on the earlier cases. Our cornerstone problem is
a folkloric tiling of a punctured chessboard, and we also apply induction to
combinatorial geometry and a probability problem from the Putnam exam.
We know that 2009 is a red herring, so we focus on whether it will work for
any chessboard of size 2n u 2n . It certainly works when n = 1 or n = 2. Can
we bootstrap from n = 2 to n = 3 to n = 4 and so on? Mathematical induction
allows us to prove an empirical pattern and show how it extends inde¿nitely.
In general, mathematical induction proof involves a sequence of propositions,
Pn , indexed by natural numbers. We wish to prove that P1 , P2 , } are all
true. To do this, we ¿rst show that P1 (the base case) is true. Then we need
to establish the principle that if each case is true, the next one will be as well:
In other words, for all positive integers n, if Pn is true, then Pn 1 will also be
true. The assumption that Pn is true is called the inductive hypothesis. We do
not know if it is true, but we use its truth to prove that Pn 1 is true.
89
adjacent regions are never the same color. Let’s call colorings such as the
above “nice.” De¿ne Pn to be “If the plane is divided into regions by n
straight lines, then it is possible to color nicely.” This is clearly true for n
= 1 (we have proven the base case). But what about, say, n = 10? We need
an algorithm for moving from the nth case to the (n + 1)th case. Keep things
concrete: Suppose I can nicely color any 5-line con¿guration. How can I
use this to nicely color an arbitrary 6-line con¿guration? Here is the formal
solution for the inductive step.
• Now you have an n-line con¿guration, which you know you can
color nicely.
90
Here is a probability example from the 2002 Putnam exam: Shanille O’Keal
shoots free throws on a basketball court. She hits the ¿rst and misses the
second; thereafter, the probability that she hits the next shot is equal to the
proportion of shots she has hit so far. What is the probability she hits exactly
50 of her ¿rst 100 shots?
91
• Now suppose we do get a basket on the ¿nal toss. Then we
accumulated b í 1 baskets in the ¿rst t tosses. By the inductive
hypothesis, this also has probability 1/(t í 1). The probability
we will get a new basket is equal to the current proportion,
(b í 1)/t. So the probability that we end up with b baskets by
missing the last toss is [1/(t í 1)](b í 1)/t = (b í 1)/t(t í 1).
The induction proof is formally correct but not fully illuminating. This is a
feature of some induction proofs. You can verify how to get from t to t + 1,
but you sometimes do not know why it works.
• Place a tromino in the center so that it takes a single bite out of each
of the other quadrants.
Suggested Reading
92
Questions to Consider
1. Conjecture a formula for the sum of the ¿rst n Fibonacci numbers. Then
prove your formula by induction.
93
Induction on a Grand Scale
Lecture 20
Imagine that you had a lot of time and you wrote out many, many rows
of Pascal’s triangle, like a couple quadrillion rows. Then you took all of
those numbers, and you put them on little pieces of paper, and you put
it in a hat. Then you shook the hat really, really well, and you picked out
a number at random, and you check to see if it’s odd or even. What’s
the probability that that number will be even? That’s the question
we’re going to ask, but since Pascal’s triangle is in¿nite, we have to
think about an in¿nite process.
W
hat is the probability that a randomly chosen number in Pascal’s
triangle is even? This problem is surprisingly easy to investigate
but requires sophistication to resolve. By this stage, you have a
good grasp of investigative methods, summation, mathematical induction,
and modular arithmetic, so you are ready for this investigation, the ¿rst of
the advanced lectures as we approach the end of the course.
94
coef¿cients of (1 x) n are the elements of row n. The base case is obvious,
since row 0 is just 1, and row 1 is 1, 1. We want to prove the inductive
step now, but let’s keep it concrete and informal. We will just show that P5
implies P6 ; our argument will generalize easily.
Now let’s look at the parity of the numbers of Pascal’s triangle. We will work
(mod 2). Look at the ¿rst 9 rows. At ¿rst, there are not many evens at all. But
row 4 and row 8 are all even, except for the ubiquitous 1s that start and end
every row. And notice that rows 3 and 7 are all 1s. We conjecture that row
2n 1 will be all 1s and that row 2n will be all 0s, except for the ¿rst and
last terms. Clearly, the second statement follows from the ¿rst, but how do
we prove the ¿rst statement?
Now look at rows 0–32. We see a fractal structure, with inverted triangles
of 0s. What causes them? The seed of the 0 triangles is the row of all 1s,
since this forces the next row to be all 0s (except the ¿rst and last terms).
The natural way to look at the parity of Pascal’s triangle is by successive
doublings of it. Let Tn be the nth-order triangle that ends with a row of 1s.
T1 is the triangle consisting of rows 0 and 1 (i.e., it contains three 1s), and
T2 is the triangle that is built out of 3 copies of T1, with a 0 in the middle.
In general, Tn is the triangle that ends with row 2n 1 , which is all 1s. This
starts 2 seeds at opposite ends, with 0s in between, which then grow 2 more
copies of Tn, producing a new structure, Tn+1.
95
in Tn, we get the simple formula Un = 3n. Our ¿nal step is to compute the
relative fraction of 1s in Tn and then let n get large.
How many elements are in Tn? It is a triangle starting with one element and
ending with 2n elements. So the number of elements in Tn is the 2n triangular
number! This is equal to 1 + 2 + … + 2n = 2n(2n + 1)/2. Thus, the probability
that an element in the ¿rst 2n rows is odd is equal to 2(3n)/2n(2n + 1). Despite
the factor of 2 in the numerator, the 4n in the denominator will eventually
overpower it, so the limit is 0. A more rigorous way to see this is by dividing
numerator and denominator by 4n. As n grows larger, the entire fraction
approaches 0. So the probability that an
element is odd approaches 0. That means that
the probability an element is even approaches By this stage, you
100%, which is truly surprising. In other have a good grasp
words, essentially all binomial coef¿cients of investigative
are even! methods, summation,
mathematical
We just proved an absolutely amazing fact
about long-term convergence of parity, an induction, and
asymptotic property of Pascal’s triangle. modular arithmetic.
But it would be nice to analyze the parity in
a more exact way. In Lecture 4, we counted
the number of evens and odds in each row, and the number of odd terms
was a power of 2. Which power of 2? What is the appropriate point of view
Lecture 20: Induction on a Grand Scale
But why? Remember that the elements of Pascal’s triangle are the coef¿cients
of (1 x) n . When n = 2, we have (1 x) 2 1 2 x x 2 , but (mod 2), the
middle term disappears. So (1 x) 2 1 x 2 (mod 2). If we square this again,
we get n(1 x) 4 n (1 x 2 ) 2 1 x 4 (mod 2). In general, we see that for any n,
(1 x) 2 1 x 2 (mod 2). This immediately explains why row 2n has just
two 1s!
96
But what about an arbitrary row, say, row 11?
Here is a slicker way to see it: When (1 x)11 is multiplied out and simpli¿ed
modulo 2, it will be a sum of powers of x n , where the coef¿cients will either
be 0 or 1. Ŷ
Suggested Reading
Questions to Consider
2. Investigate the same question that we did in the lecture, but modulo 3. In
other words, look at the patterns of when elements of Pascal’s triangle
are multiples of 3. It is a little more subtle than before, because now
there are 3 possible values (mod 3): 0, 1, and 2.
97
Recasting Numbers as Polynomials—Weird Dice
Lecture 21
T
his is an advanced lecture that uses algebra more than most, including
in¿nite geometric series. Can we renumber 2 dice with positive whole
numbers that are not the standard 1, 2, 3, 4, 5, and 6 in such a way that
the various sums still range from 2 to 12 inclusive, with the same probabilities
as standard dice? Amazingly, the answer is yes. We use generating functions,
which glue most of mathematics to polynomial algebra.
Lecture 21: Recasting Numbers as Polynomials—Weird Dice
98
The Dice Problem
• Suppose such dice exist. We will call them weird dice. If you
roll 2 weird dice (and they may not be 2 identical dice), the
probability of getting a sum of 10 will still be 3/36.
• Note that a weird die can have multiple faces with the same
label—for example, three 1s, two 2s, and one 5.
99
Here are some examples of sequences transforming into generating functions
or vice versa.
• 1, 2, 3 ļ 1 2 x 3 x 2 .
• 1, 1, 1, 1, … ļ 1 x x 2 x3 x 4 " 1/ (1 x) .
Many operations are possible with generating functions, but we will stick
to multiplication. Let’s look at some examples. Compute (2 + x)(1 + 3x) =
2 6 x x 3 x 2 , using the FOIL method. There are 4 raw terms. What is
the coef¿cient of x 6 in ( x3 2 x 2 x)(3 x 4 2 x3 x) ? We want to look at
the ways we can multiply terms and get the
exponent of 6. The x3 and 2x3 and the 2x 2
and 3x 4 combine to give an answer of 1 × 2 + Generating functions
Lecture 21: Recasting Numbers as Polynomials—Weird Dice
2 × 3, which equals 8.
can shed light on
Generating functions can shed light on combinatorics.
combinatorics. Consider the simplest type of
die (i.e., a coin). Put 0 on one side and 1 on the
other. Then the generating function will be 1 + x. Suppose 7 people are each
Àipping a coin to decide if they will get a prize (0 = no, 1 = yes). The number
of prizes possible ranges from 0 to 7. There are 27 different outcomes. Each
is encoded by the expansion (1 + x)7 = (1 + x)(1 + x)(1 + x)(1 + x)(1 + x)(1 +
x)(1 + x) = 1 + 7x + 21x2 + 35x3 + 35x4 + 21x5 + 7x6 + x7. How many outcomes
had 3 prizes? 35. In other words, there are 35 ways to choose 3 prize winners
§7·
out of 7 contestants. Thus 35 ¨ ¸ .
© 3¹
Now we are ready to recast the original dice problem into polynomial
form. The generating function for a single die is D(x) = x x 2 x3
x 4 x5 x 6 . The generating function for the sums of 2 ordinary
dice is just D(x)D(x) = ( x x 2 x3 x 4 x5 x 6 ) 2 . This expands to
x 2 2 x3 3 x 4 4 x5 " 2 x11 x12 . If weird dice exist, we must have A(x)
B(x) = (x x 2 x3 x 4 x5 x 6 ) 2 . Now we have converted a tricky question
into a relatively simple one: Can we factor ( x x 2 x3 x 4 x5 x 6 ) 2 in a
different way?
100
We can do this with algebraic tools. Use the geometric series tool to simplify
x + x2 + … + x6 = x(x6 í 1)/(x í 1). We have to factor (x + x2 + … + x6)2 =
x2(x6 í 1)2/(x í 1)2. We need to get rid of the denominator. The full
factorization thus is x2(1 + x)2(1 í x + x2)2(1 + x + x2)2, and now it is a
matter of rearranging them in a nonsymmetrical way. In other words, if we
write each distinct prime as P(x) = x, Q(x) = (1 + x), R(x) = 1 í x + x2, and
S(x) = 1 + x + x2, then D(x) = PQRS.
• P(1) = 1.
• Q(1) = 2.
• R(1) = 1.
• S(1) = 3.
So for each die, we need exactly 1 Q and 1 S, since that is the only way to
get the proper coef¿cient sum. We can do whatever we want with the other
factors, as long as each die also has 1 P. We conclude that our weird dice are
1, 2, 2, 3, 3, 4 and 1, 3, 4, 5, 6, 8.
101
Suggested Reading
Questions to Consider
2. Consider the in¿nite series 1 D( x) > D( x)@ > D( x)@ " , where
2 3
102
A Relentless Tactic Solves a Very Hard Problem
Lecture 22
T
his advanced lecture is a continuation of the ideas begun in Lecture
14. We use the pigeonhole principle relentlessly to study Gallai’s
theorem, a Ramsey-style assertion. Our investigation takes us into the
realm of the nearly in¿nite, where we contemplate numbers far larger than
the number of atoms in the universe. The strategic principle we highlight is
more earthbound: Don’t give up.
Let’s do a warm-up problem: Color the lattice points of the plane in 2 colors.
Prove that there must be a rectangle (with sides parallel to the axes) each
of whose vertices are the same color. The pigeonhole principle applied to
3 consecutive lattice points in a horizontal line forces there to be at least 2
points of the same color (points are pigeons, colors are holes). We would be
done if we had 2 identical patterns, one on top of the other. But how do we
guarantee this can happen?
Here’s the crux idea: Look at 9 rows of 3 points, and we are guaranteed that 2
of the rows will be identical! After all, there are only 8 different 2-colorings
of 3 points! And since each row contains 2 points of the same color
(at least), we will have a monochrome rectangle. Thus every 3 × 9 grid of
points contains a monochrome rectangle. This is a worst-case scenario, of
course; we could have gotten lucky with just a 2 × 2 grid, but 3 × 9 guarantees
103
it. This can be easily generalized. If we 5-colored the lattice points of the
plane, there would still be a monochromatic rectangle, but we would need to
look at rows of 6 points (to guarantee that each row contains at least 2 points
of the same color) and then consider 56 + 1 (or 15,626) rows.
104
How do we create a monochrome square? Certainly the monochrome right
angle is a start. What if we could make a monochrome right angle out of
monochrome right angles? The worst-case scenario is that the lower right
corner is not red. In this case, we can guarantee a structure where 3 of the
4 vertices are red but the fourth vertex is blue. Then we can again make a
right angle with these structures. Then we are done; no matter what color the
lower right-hand point is, we have created a monochrome square. However,
in order to do this, we needed a right-angle construction with identical right
angles. We can only get monochrome right-angles so far using 2 colors. But
what if we could get right angles using any number of colors? That is what
we need to complete our proof.
• There are about 1080 particles in the universe. If every one of those
particles could count at a speed of a billion billion billion billion
billion numbers per second, it would take the universe 10712870
seconds, or 10712863 years, just to count this number.
105
Now view the entire 2-colored lattice, but in 1539 × 1539 chunks. You can
think of this as a B-colored lattice. If R(B) is the ¿nite value G, then there is a
grid of G × G chunks that is guaranteed to contain a monochrome right angle
of chunks!
Thus, if we can show that R(B) is ¿nite, we are done. It was already pretty
hard to compute R(2), but we will con¿dently compute R(3), and do it in a
way that can clearly be generalized to higher numbers of colors. Our guiding
principles are to stick to worst-case scenarios and build structures with focal
points. We start by considering a row of 4 points. This guarantees 2 identical
colors somewhere in this row. There are 316 different ways to 3-color this 4 ×
4 grid, so just string 316 + 1 of them together in a row, and we are guaranteed
to see 2 identically colored grids. Let M = 316 + 1.
Next, focus on a grid that would contain the third vertex of our right angle.
Since it is a worst-case scenario, it is possible that this focal point is colored
Lecture 22: A Relentless Tactic Solves a Very Hard Problem
106
Suggested Reading
Questions to Consider
1. Color the plane in 2 colors. Prove that 1 of these colors contains pairs
of points at every mutual distance. In other words, 1 of the 2 colors,
say, red, has the property that for each distance x, there are 2 red points
exactly x units apart. (Hint: Use proof by contradiction.) What is the
negation of the assertion?
2. Color the plane in 2 colors. Prove that there will always exist an
equilateral triangle with all its vertices of the same color.
107
Genius and Conway’s In¿nite Checkers Problem
Lecture 23
I
n our penultimate lecture, we sketch John Conway’s brilliant solution
to a classic puzzle. Our focus is not just on the mathematics, which is
a wonderful mix of the ubiquitous golden ratio and monovariants, but
we also engage in a discussion of mathematical culture, particularly the
cult of genius that surrounds Conway and other mathematical “rock stars,”
including Paul Erdös and Évariste Galois.
Lecture 23: Genius and Conway’s In¿nite Checkers Problem
108
• This quantity should be a monovariant.
• For example, the entire ¿rst row (y = 0) has the Conway sum
z 5 2( z 6 z 7 ") .
2z6
• This simpli¿es to z 5 .
1 z
2z 6
• Since z2 + z = 1, we simplify this further to z 5
z2
z5 2z 4 z3 ( z 2 z) z 4 z3 z 4 z2 (z z2 ) z2 .
109
• Likewise, the Conway sum for the row y = í1 will be z3,
and so on, so the starting Conway sum of our problem is
z2 z2
z 2 z3 z 4 " 1.
1 z z2
• Why is this a monovariant? Consider any con¿guration of
checkers, and look at what happens to the Conway sum when
a jump occurs.
• For example, suppose there are checkers at (4, 1) and (4, 2),
and (4, 3) is unoccupied, so the ¿rst checker can jump over
the second.
110
• There is one other case to check: that where your jump does
not change the distance to C. For example, if you jump from
(í1, 2) to (1, 2).
It takes a certain type of intellect to solve problems at this level. The key
ingredient is a passion to investigate without any worry about consequence.
Conway is one of a triumvirate of such
heroes that also includes Paul Erdös and
The key ingredient is a
Évariste Galois. All 3 are iconoclastic
rebels, belying the myth of the boring nerd, passion to investigate
who supply romantic inspiration for the without any worry
next generation. John Conway has led an about consequence.
unconventional life and made incredible
contributions to math. He is like an eternal
child in his ability to play, break rules, work on whatever pleases him, and
continually ask questions, with a willingness to get his hands dirty. Paul Erdös
111
led a life of deliberate homelessness and celibacy. He wrote more papers and
collaborated with more people than any mathematician in history. Évariste
Galois died in a duel at age 20. His 60 pages of mathematics are considered
by some to be the most important 60 pages ever written in mathematics. His
greatest achievement, now called Galois theory, is a point of view Àip.
Suggested Reading
Berlekamp, Conway, and Guy, “The Solitaire Army,” in Winning Ways for
Your Mathematical Plays.
Hardy, A Mathematician’s Apology.
Lecture 23: Genius and Conway’s In¿nite Checkers Problem
Questions to Consider
1. The solution to the checkers problem was pretty subtle. Test your
understanding: Why not just assign a large value—say, 100—to the
point C? Then if a checker occupied C, the Conway sum would be at
least equal to 100. But since the Conway sum starts at the value of 1 and
never increases, it can never reach a value this large and hence never
occupy C. What is wrong with this argument?
112
How versus Why—The Final Frontier
Lecture 24
I
n this ¿nal lecture, we look back on what we have learned, talk about
what we should study next, and reÀect on what we do not know. We
begin to ponder the ultimate purpose of an investigation: the quest
for why something is true, not just how. I will share some of my favorite
examples of this elusive intellectual quest.
First, some reminders about how to approach problems tactically, with the
assumption that by now you have internalized key strategies.
• Proof by contradiction should be used when the thing you are trying
to prove is easier to contemplate when negated.
• The extreme principle is useful when your problem has entities that
become simpler at the boundary.
• The pigeonhole principle works well when the penultimate step can
be formulated with 2 things belonging to the same category.
• The most important thing is to ask what type of problem you are
trying to solve. This is half the battle.
What should you study next? Complex numbers! They are another
playground with incredible potential for connecting many branches of
math. Complex numbers are 4 things simultaneously: numbers, locations
in the plane, vectors, and transformations! Complex numbers allow you to
recast to and from physics, with dynamic interpretations of hitherto static
113
objects. They also have connections to every branch of math, including
number theory.
• “How” arguments are rigorous and have clear details, but the global
picture is murky.
114
• Problems fall all along the spectrum from completely opaque to
completely understood in the “why” sense.
So what’s next? Keep learning facts, but do not forget the need to build up
Àexibility, visualization, recasting, physical intuition, and the ability to see a
natural point of view. Learn about complex numbers, which incorporate all of
these ideas. Remember that problem solving is not just a textbook subject—
it is a lifestyle, with a culture. The true underpinnings of this culture are
passion and persistence. Ŷ
115
Suggested Reading
116
Solutions
Lecture 1
1. The problem is that there are 3 switches, but a light bulb only has 2
states: on and off. Use wishful thinking: What if you had a light bulb
with 3 states? You do, since a bulb can be on, off and cold, or off and
warm. So turn one switch on, leave one switch off, and turn the third
one on brieÀy and then off. Go upstairs and check to see which state the
bulb is in!
2. Once again, use wishful thinking: If you had a hook in the ceiling, you
would be done, since you could tie the ends together at the bottom,
climb up, hang onto the hook, cut both ropes at the top, slide one end
through, climb down the doubled rope, and then pull it loose from the
hook. Indeed, you can create a hook: Just cut off a small chunk at the top
of one rope and make a loop right near the ceiling!
Lecture 2
1. It is not possible. The numbers 1, 3, 5, 7, and 9 are odd; the others are
even. Adding or subtracting an even number does not change parity, but
adding or subtracting an odd number does. We start with zero (nothing
written yet) and then proceed to add or subtract 5 odd numbers and 5
even numbers. Parity changes 5 times, so the ¿nal result will always be
odd. But zero is even!
2. The ¿rst professor writes a random number and shows it to the next
professor, who then writes the sum of her salary and the ¿rst number on
her piece of paper. This process of writing the running sum is continued
until the last professor shows her sum to the ¿rst, who then subtracts her
random number and adds her real salary. Now the sum (and hence the
average) is known.
117
Lecture 3
2. She could be just a few moments older than 30, if she was born at
11:59 pm on December 31, 1959, and she uttered her words early on
January 1, 1990.
Lecture 4
Lecture 5
Lecture 6
2. The second trip takes 4 fewer seconds, but 12 more steps are stepped
on. So the escalator is traveling 3 steps per second. Therefore, on the
¿rst trip, her net speed is 4 steps per second, and in 20 seconds she goes
80 steps, the “true” distance.
Lecture 7
Solutions
1. Assume, to the contrary, that all 3 are odd. Then the sum of the squares
of 2 of them would be the sum of 2 odds, which is even. Yet the square
of the third one is odd. Contradiction!
118
2. No. Assume, to the contrary, that there is such a line. Move your diagram
so that this line is horizontal. Then, without loss of generality, A lies
above the line. Thus B is below, C is above, D is below, E is above, and
we have a contradiction, since the segment EA should be intersected by
this horizontal line!
Lecture 8
1. Let A = (4, 3), and let B and C be the points on the x-axis and the line
y = x, respectively. If we reÀect the picture across the x-axis, we see that
line segment AB will have the same length as the line segment from
(4, í3) to B. If we reÀect now across the line y = x, we see that AC has
the same length as the line segment from C to (3, 4). So the perimeter of
the triangle is equal to the sum of the lengths of the line segments from
(4, í3) to B, from B to C, and from C to (3, 4). This is clearly minimized
by the straight segment joining (4, í3) to (3, 4). By the Pythagorean
theorem, this minimal length is 12 7 2 , which is 50 .
Lecture 9
119
2. Consider the magic square below.
2 7 6
9 5 1
4 3 8
Each row, column, and diagonal adds up to 15. Hence our game is
equivalent to tic-tac-toe, which we all know will be a draw if players
play optimally. But you can win this game if you have the magic square
picture in mind and your opponent does not.
Lecture 10
1. Suppose that they are not all equal. Then there is a value m that is the
least value on the board, and at least somewhere on the board, since the
values are not all equal, this value m must be adjacent to a value M that is
greater than m. But then m is the average of 4 values, including M, which
forces one of the values to be strictly less than m, a contradiction.
Lecture 11
Not applicable.
Lecture 12
1. Not applicable.
Solutions
120
2. Let’s show that it is true for a quadrilateral ABCD. Divide it into
triangles ABC and ACD. The area of the quadrilateral will be the sum of
the areas of the triangles. For each triangle, the area is equal to half the
boundary lattice points, plus the interior lattice points, minus 1. When
we apply this to both triangles and add, the boundary count includes
the lattice points on segment AC twice. Suppose AC contains exactly x
lattice points (including A and C). Then half the boundary count for the
2 triangles will be equal to half the boundary count for the quadrilateral,
plus x í 1. (The minus 1 is because A and C are counted twice.) However,
the interior count of the 2 triangles does not include any of the x í 2
lattice points that are on AC (not including A and C). So the interior
counts of the 2 triangles added will be equal to the interior count of the
quadrilateral, minus x í 2. The ¿nal bit of accounting is to note that the
triangle count includes two í1s, and for the rectangle, just one í1, so it
balances out. This can be extended to larger polygons.
Lecture 13
Lecture 14
1. Partition the unit square into four 1/2 × 1/2 squares. By pigeonhole,
one of these smaller squares must contain at least 2 points. Since the
diagonal of each small square is 2 / 2 , that is the maximum distance
between the 2 points.
121
2. There are 150,001 categories (include bald people!). We need to ¿nd the
minimum population p such that the ceiling of p divided by 150,001 is
equal to 10. Thus p = 9 × 150,001 + 1 = 1,350,010.
Lecture 15
2. You cannot. If you could, then the quotients (b í c)/(a í b), (c í a)/
(b í c), and (a í b)/(c í a) would all be integers. However, the product
of these 3 quotients is invariant; it is 1. The only way that 3 integers can
multiply to 1 is if all of them are equal to 1. But that would mean that
2b = a + c, 2c = a + b, and 2a = b + c. In other words, a, b, and c are
each the average of the other 2. Using the extreme principle, let, say,
a be the smallest of the 3 numbers (remember, the numbers are distinct).
Then we have a contradiction. How can a be the average of 2 numbers
that are both larger than a? The other possibility is if one of the quotients
is 1 and the other 2 are í1. But if a quotient equaled í1, for example, the
¿rst quotient, we would get b í c = b – a, which makes c = a, another
contradiction.
Lecture 16
1. ReÀect across the stream. Then when you build your optimal rectangle
with perimeter S, the mirror rectangle also has perimeter S, and
collectively, you are building a rectangle with 4 sides that is to have
maximal area, with a ¿xed perimeter of 2S. You know that this optimal
shape is a square. So the answer to the original question is a half square:
a rectangle whose sides are in the ratio 1:2, with the longer side on
the stream.
122
Lecture 17
1. Imagine, on the second day, a clone of the ¿rst monk who starts at the
bottom at 8 am and exactly imitates what the ¿rst monk did the day
before. Clearly the 2 monks will meet on the trail, and this time and
place are the solution.
2. Draw a lattice of squares. Start at (0, 0), and begin drawing a line with
slope 7/11. As it goes northeast, it will ¿rst hit another lattice point at
(11, 7). To count bounces, just count the number of times this line hits a
horizontal or vertical lattice line. It will hit x = 1, 2, 3, …, 10 and y = 1,
2, 3, …, 6, for a total of 16 bounces.
Lecture 18
1. Just rotate the diagram 60° clockwise about the center K. Then J moves
to M, and N moves to I. Hence JN = IM. Likewise, a rotation about I will
show that LK = JN.
2. Start with the point (0, 0). The ¿rst rotation leaves it ¿xed; the second
one, about (1, 0), brings it to (1, í1); the third brings it to (3, í1); and
the ¿nal one brings it to (4, 0). So the translation (of any starting point)
will be “move 4 units to the east.” You might conjecture that if you
360 °
have n rotations, about (0, 0), (1, 0), … , (n í 1, 0), each by
n
counterclockwise, the net result would be a translation by n units to the
right, and this is correct. The easiest way to see it is to imagine a regular
n-gon with side length 1 unit whose “top” side is the line segment joining
(0, í1) and (0, 0). Then the rotations are equivalent to rolling this n-gon
along the x-axis, ending up n units to the right. Try this for n = 3, n = 4,
or n = 5 to see for sure.
123
Lecture 19
2. Once again, the base case is obvious, since the ¿rst Fibonacci number
is less than 2. Thereafter, it is simple as well: Since each successive
Fibonacci is equal to the sum of the 2 preceding it, and since the
sequence is an increasing one, each Fibonacci number is strictly less
than twice the one before it.
Lecture 20
2. The analysis is similar to what we did in the lecture, but this time,
recursive structures are successive powers of 3, and each new triangle
consists of 6 triangles of the previous kind, with an inverted 0 in
the middle. You can search the Web for “Pascal’s triangle modulo 3”
to ¿nd good illustrations and interactive applets; one example is
at http://faculty.salisbury.edu/~kmshannon/pascal/article/twist.htm. The
reason for the number 6 is that it is equal to 1 + 2 + 3. The limit of the
Solutions
124
Lecture 21
dice are rolled. You may enjoy looking up this sequence in The Online
Encyclopedia of Integer Sequences; they are called the “hexanacci”
numbers. Can you see why? Because they satisfy the recurrence
formula that each number in the sequence is equal to the sum of the 6
previous numbers!
125
Lecture 22
2. Start by ¿nding 2 points that are the same color, say, red, at locations
A and B. Now consider the con¿guration below made of equilateral
triangles. Besides the small equilateral triangles, note that there are
larger equilateral triangles, such as CDE and AEH. The existence of
these alternatives is key for a miniature Gallai-style argument: Either C
or D are red; then we would be done. Otherwise, both C and D are blue.
Then if E is blue, we are done again (triangle CDE). But if E is red, then
we will be done if either F or G is red. If not, they are both blue. But now
we have a focal point at H. If it is red, we have a large red equilateral
triangle (AEH). If it is blue, we have the small equilateral triangle HCF.
No matter what, a monochrome equilateral triangle is guaranteed.
Solutions
126
Lecture 23
Lecture 24
Not applicable.
127
Timeline
the U.S.
128
1959................................................. The ¿rst International Mathematical
Olympiad is held in Romania, with
teams from 7 countries.
1961................................................. John Conway analyzes the
checker problem.
1970................................................. John Conway invents the
cellular automaton Game of Life,
popularized by Martin Gardner in
Scienti¿c American.
1972................................................. The ¿rst USA Mathematical Olympiad
is held.
1974................................................. The U.S. participates for the ¿rst time
in the International Mathematical
Olympiad (in East Germany), placing
second after the USSR.
1977................................................. Wythoff’s Nim is popularized by Martin
Gardner in Scienti¿c American.
1981................................................. The International Mathematical
Olympiad is held in the U.S. for the ¿rst
time, with 27 countries participating.
1985................................................. The Colorado Mathematical Olympiad
begins, founded by Soviet émigré
Alexander Soifer. This was the ¿rst
regional Olympiad-style contest in
the U.S.
1994................................................. The U.S. team comes in ¿rst place at
the 35th International Mathematical
Olympiad (held in Hong Kong), with
all 6 team members receiving perfect
scores. This was the ¿rst and only time
a team has received a perfect score at
that competition.
129
1996................................................. Hungarian-born Paul Erdös, the most
proli¿c mathematician and problem
solver of modern times, dies.
2001................................................. The U.S. hosts the International
Mathematical Olympiad for the second
time, with 83 countries attending.
Timeline
130
Glossary
bipartite graph: A graph whose vertices can be colored red and blue in such
a way that no edge connects vertices of the same color.
degree: A graph theory term; the degree of a vertex is the number of edges
emanating from it.
131
generating function: Given a sequence a0 , a1 , a2 , } , its generating function
is the polynomial a0 a1 x a2 x 2 " . The generating function encodes
information about the entire sequence; algebraic manipulations of generating
functions can thus shed light on questions about the sequence.
graph theory: The branch of math that studies abstract networks, also
known as graphs, which are entities of vertices joined by edges. It is easy to
learn and therefore a very accessible laboratory for exploring a number of
problem-solving themes.
handshake lemma: An important graph theory result stating that the sum of
the degree of each of the vertices of a graph is equal to twice the number of
edges in the graph.
harmonic series: The sum of the reciprocals of the positive integers, which
is a divergent series (meaning the sum is in¿nite).
132
invariant: A very high-level tactic for looking at many problems where a
quantity or quality stays unchanged. A monovariant is a quantity that changes
in only one direction; monovariants are very useful for studying evolving
systems and proving that they terminate or that certain states are impossible.
number theory: The branch of math dealing with integers. Because integers
are familiar to us beginning in grade school, number theory, like graph
theory, is an excellent venue for mathematical investigation for beginners.
prime number: A positive integer that has no positive integer divisors other
than 1 and itself. The ¿rst few primes are 2, 3, 5, 7, 11, and 13.
133
problem: A mathematical question that one does not know, at least
initially, how to approach and that therefore requires investigation, often
using organized strategies and tactics. We contrast this with an exercise: a
question that may be dif¿cult but is immediately approachable with little
or no investigation.
Pythagorean theorem: The sum of the squares of the legs of a right triangle
is equal to the square of its hypotenuse. There are hundreds of known proofs
of this theorem, the earliest thousands of years old.
of Lecture 19 is another.
134
strategies: Mostly commonsense organizational ideas that help overcome
creative blocks to begin and facilitate a problem-solving investigation.
Strategies in this course include wishful thinking, make it easier, get hands
dirty, chainsaw the giraffe, draw a picture, change your point of view, and
recast your problem.
tactics: Narrower than strategies, tactics are broad ideas within mathematics
generally used at a later stage of investigation, often providing the key to
a solution. Examples in this course include symmetry, parity, the extreme
principle (contemplate extreme values), the pigeonhole principle, and squarer
is better.
tromino: A shape made out of 3 contiguous square units. There are only 2
types of tromino, the L and the I (a straight line of 3 squares). Trominos and
more complex shapes (e.g., the 12 different pentominos, made of 5 squares)
are popular objects of study in recreational mathematics.
135
Wythoff’s Nim: One of the many names of a simple combinatorial game
whose solution involves Fibonacci numbers and the golden ratio. Nim is an
ancient game in which 2 players typically take turns removing objects from
piles until none are left.
Glossary
136
Biographical Notes
137
Klein, Felix (1849–1925): A German mathematician and inÀuential
expositor. He proposed the important point of view change that geometry is
best understood by looking at transformations rather than objects.
Biographical Notes
138
Bibliography
The list of books and resources below is pretty large, even though it just
scratches the surface of the literature out there. If you are just getting started
and really want to become a better problem solver, you must get practice
by working on problems, and it is best for the problems to be fairly gentle
and nontechnical.
The best place to start is by perusing any book by Martin Gardner. The CD
collection of his books is an economical way to go (and its searchable). If
you feel overwhelmed by the sheer quantity of Gardner’s work, there are
4 great single-volume choices. George Polya’s classic How to Solve It is
short and very useful. My book, The Art and Craft of Problem Solving, has
a larger collection of problems and a more explicit treatment of strategy
and tactic. The Mathematical Circles (Russian Experience) book lead-
authored by Dmitri Fomen has a wealth of “easy” problems (i.e., intended
for Russian middle school–aged kids) along with good pedagogical ideas.
And perhaps the most enjoyable single-volume book to look at is Ravi
Vakil’s Mathematical Mosaic. It is not comprehensive, but the mathematical
topics are chosen with great taste. Its style may seem a little juvenile—it was
written for a young audience—but the mathematics is actually quite deep.
Aigner, M., and G. Ziegler. Proofs from THE BOOK. Berlin: Springer,
2000. A collection of proofs that satisfy Paul Erdös’s criteria of elegance,
simplicity, and beauty.
139
Beck, M., and S. Robbins. Computing the Continuous Discretely. New York:
Springer, 2007. This is an elegant (albeit advanced) book that explores the
relationship between combinatorics and geometry, mostly via counting
lattice points.
Conway, John H., Heidi Burgiel, and Chaim Goodman-Strauss. The Symmetry
of Things. Wellesley, MA: A. K. Peters, 2008. The latest of Conway’s many
books, this one is bound to be a classic.
for beginners.
140
Gardner, Martin. Aha! A Two Volume Collection. Washington, DC:
Mathematical Association of America, 2006. Originally published separately
and now reissued as a single volume, this is a collection of some of the short
puzzles of Martin Gardner. The theme of the aha puzzles is the unexpected,
creative solution.
141
Graham, Ronald, Bruce Rothschild, and Joel Spencer. Ramsey Theory. 2nd ed.
Hoboken, NJ: Wiley, 1990. A fascinating (albeit quite advanced) discussion
of many Ramsey theory topics, by one of Erdös’s favorite collaborators,
Ronald Graham.
Hoffman, Paul. The Man Who Loved Only Numbers. New York: Hyperion,
1999. A beautifully written book about an unbelievable character, Paul Erdös,
the most proli¿c researcher in the history of mathematics.
142
Kendig, Keith. Sink or Float? Thought Problems in Math and Physics.
Washington, DC: Mathematical Association of America, 2008. An elementary
book to help develop your physical intuition in a mathematical context.
Lansing, Alfred. Endurance. New York: Carroll and Graf, 1999. First
published in 1959, this is a riveting account of an epic tale of survival: the
ill-fated Antarctic voyage of Ernest Shackleton. It is relevant to us because
of the important story of mental toughness.
Lehoczky, Sandor, and Richard Rusczyk. The Art of Problem Solving. 7th ed.
Vols 1–2. Alpine, CA: Art of Problem Solving, 2008. An excellent guide for
beginners (as young as middle school), with complete solutions to problems
from a very wide variety of topics.
Liu, Andy, ed. and trans. Hungarian Problem Book III. Washington, DC:
Mathematical Association of America, 2001. There are several volumes in
English of the famous Hungarian Problems, the earliest modern Olympiad-
style contest. All 3 volumes of this series have excellent commentary about
problem solving in general, but this is the best of them.
143
Olson, Steve. Count Down: Six Kids Vie for Glory at the World’s Toughest
Math Competition. Boston: Houghton MifÀin Harcourt, 2004. A fascinating
account of the 2001 International Mathematical Olympiad, which was held
in the United States.
Polya, G. How to Solve It. 2nd ed. Princeton, NJ: Princeton University Press,
1957. This is the classic book about problem solving. All later books, mine
included, owe a tremendous debt to Polya’s pioneering work and writing.
Solow, Daniel. How to Read and Do Proofs. 5th ed. Hoboken, NJ: Wiley,
2009. One of the standard college texts on this dif¿cult topic.
Tanton, James. Solve This: Math Activities for Students and Clubs.
Washington, DC: Mathematical Association of America, 2001. This is a one-
Bibliography
of-a-kind collection of deep puzzles that have a hands-on quality. Perfect for
truly doing mathematics and developing physical intuition.
144
Vakil, Ravi. A Mathematical Mosaic. Ontario: Brendan Kelly, 1996. One
of my favorite books for beginners, this is an absolutely joyous excursion
through many topics. Vakil is one of the best contest problem solvers in
history, but only modesty and generosity come across in this remarkable
little book.
Velleman, Daniel. How to Prove It. New York: Cambridge University Press,
2006. This excellent book is a standard college-level text.
Zeitz, Paul. The Art and Craft of Problem Solving. 2nd ed. Hoboken, NJ:
Wiley, 2007. My book parallels many of the topics in this course and has a
wide variety of problems of many levels of dif¿culty.
145
Csicery, George Paul. Hard Problems. 2008. DVD. A thought-provoking
documentary about the formation of the 2006 U.S. International Mathematical
Olympiad team and its adventures at the competition, which was held in
Slovenia. This ¿lm initially aired on PBS stations around the United States
in 2009.
146