Course webpage for
Freshman Seminar 24i: Mathematical Problem Solving (Fall 2010)
If you find a mistake, omission, etc., please
let me know
Your favorite problems or solutions
Here's a clearer picture of the
Introductions, à la Pál Erdös:
“What's your name and what's your problem?”
(from our e-mail correspondence; see the list above, plus
Iurie on an alternating sum of interval lengths when
[0,mn] is divided both
into m and into n equal parts, me on sphere packings,
and some more details on some of your favorites)
Expectations, and organizational / administrative details
Some initial problems to think about: one 5x5 and two 7x7
Kenken puzzles; which of
51/2 + 131/2 and
341/2 is larger?
Various approaches to
51/2 + 131/2 vs. 341/2.
How were these numbers 5, 13, 34 chosen?
Generalizations and connections: factoring
x2+1 or x2-1;
Fibonacci numbers; the general formula
for a1/2 + b1/2 vs. c1/2
via the sign of D(a,b,c) :=
a2 + b2 + c2 - 2 (ab + ac + bc),
with unexpected extra symmetry, in turn leading us to
Heron's formula for the area of a triangle of sides
a1/2, b1/2, c1/2
(if it exists); we know how to make D(a,b,c)=4 or
-4, but can we make |D(a,b,c)|
even smaller (but not zero) for some natural numbers a,b,c?
This turns out to be related with our CA
Iurie Boreico's HCMR article on what was then his favorite problem
— which as it happens refers to the
“favorite problem” article of Zach Abel
(who CA'd the '09 and '08 editions of this seminar) in earlier
HCMR issues. Iurie's article gets rather technical, but at least
some of the formulas in the “Preliminary Analysis” section
should look familiar…
Some more Kenken: last week's solution; parity tricks
General considerations I:
Where do problems come from, and (how and) why are they created?
The uses of problems, to proposers and solvers, ranging from external
applications to the satisfaction of solving a stumper; who is playing
the “game” (proposer? other solvers? audience for solution?), and how
this and other aspects of the context of the problem might influence
one's strategy for solving (and presenting) the solution
Progress report on small nonzero |D(a,b,c)| values:
D(a,b,c) = 1 can happen! Almost trivially at first,
with (a,b,c) = (0,u,u+1); but from one solution
we can get another by keep two of the variables the same
solving the resulting quadratic equation for the third.
This gets from (0,u,u+1) to (u,u+1,4u+2),
and beyond. [In a few weeks we'll see another way to explain why
(4u+2)1/2 is a bit larger than
u1/2 + (u+1)1/2.]
Likewise D(a,b,c) = -3, starting from the
silly-looking (1,1,1) [an equilateral triangle,
of area sqrt(3)/4] to (1,1,3)
[an isoceles triangle with angles of 30, 30, and 120 degrees],
(1,3,7), (3,7,19), and beyond,
giving increasingly sharp triangles, all with the same area
sqrt(3)/4, that can be plotted on the triangular lattice,
as the original (5,13,34) triangle can on the
square lattice (see the next item).
This technique can be used for other problems, finding for instance
infinitely many solutions of
a2 + b2 + c2 = abc
starting from the symmetrical (3,3,3).
For equations of arbitrary degree (rather than just quadratic)
this is related with
Viète's formulas for the
coefficients of a polynomial with known roots and leading coefficient.
More on the triangle inequality.
Proving it algebraically, in effect via
x12 + y12,
x22 + y22,
) = -4 (x1y2-x2y1)2
[sorry, HTML doesn't handle expressions like x12
as well as TeX...]. Along the way we find that
which is one way to state the 2-dimensional case of the
whose importance and ubiquity in mathematics are hard to overstate.
Equality holds if and only if
which is to say if and only if the vectors
(x1, y1) and
are proportional. In 3 dimensions, we find with a little more work that
equals -4 times
so we get the triangle inequality for vectors
(x1, y1, z1) and
(x2, y2, z2),
with equality if and only if one is a nonnegative multiple of the other,
and also three-dimensional Cauchy-Schwarz:
with equality if and only if the vectors are proportional.
To do it in general, either proceed in the same way, ending up with
a sum of (n2-n)/2 squares
[where did I get this count of (n2-n)/2?];
we'll soon see a less mystifying proof.
Some applications of the triangle inequality: reflection tricks
(and the physics explanation of why this is called
“reflection” to begin with);
distances on the surface of a cube.
Inequalities in general; different approaches to the maximum of
x-x2 (a.k.a. xy if x+y=1,
which reveals a symmetry between x and 1-x);
when solving an inequality problem, always try to determine
the equality condition. Introduction to the AM-GM inequality:
the arithmetic mean (AM, a.k.a. average) of any list of positive
numbers is at least as large as their geometric mean (GM), with
equality if and only if all the numbers being averaged are the same.
So, for example, can maximize xyz given xy+xz+yz
- End of the |D(a,b,c)| story: because
D(a,b,c) = (a+b+c)2 - 4 (ab + ac + bc),
D is either a multiple of 4 or exceeds by 1 a multiple of 4
(in other words, D is “congruent to 0 or 1 mod 4”).
Indeed if a+b+c is even then its square is clearly
a multiple of 4, while if it's odd, say a+b+c=2k+1,
then its square is
4k2+4k+1 = 4(k2+k) + 1
(indeed an odd square is always a mod 8, but that gives us
nothing more here). Conversely, using our work thus far
it is not hard to show that if d is 0 or 1 mod 4
then D(a,b,c) = d is possible,
so at last we're basically done with this problem.
(The condition on d was originally reached by solving
D(a,b,c) = d as a quadratic equation in c.)
- The problem of finding the
farthest point on the surface of a cube from
an edge midpoint, or from almost any other point on the surface,
is surprisingly delicate, and some problems that look very close
to this are still unsolved. It turns out that the point farthest from
an edge midpoint is neither the opposite midpoint, nor a far corner,
nor halfway between the opposite midpoint and far corner
(as one might first calculate), but a third of the way.
This is farther than the midpoint by a factor of only
which comes out to 1.003466…
- Max/min problems continued: the biggest volume of a
half- or fully-open box of given surface area; more uses of
Cauchy-Schwarz; geometrical minimization problems, e.g.
minimizing distance from point to plane, or sum of reciprocals
of distances from a point inside a given triangle to its sides
The “quadrilateral inequality” encountered during the
geometrical solution suggest a segue to the important technique of
Base case (Sn0),
inductive hypothesis (Sk),
inductive step (Sk implies Sk+1).
Variation: “strong induction”
(equivalently: apply induction to the statement
“Sk is true for each k between n0 and n”
rather than to Sn itself).
Standard examples of induction problems:
sums and and other recursions, once we've guessed the answer from
the pattern of the first few examples
(an important problem-solving technique in general,
but beware of false trails such as
maximal number of slices of a pizza produced by
n straight cuts.
- Cauchy-Schwarz, cont'd; e.g. a geometric minimization problem:
giving a triangle, find point in the interior minimizing the sum of
inverse distances to the three sides.
- Geometric solution of the problem of minimizing the sum of
distances from a point to the three vertices of an acute triangle,
leading to the Fermat point and some of the remarkable properties
of an associated configuration of three equilateral triangles.
Physical (vector field) interpretation.
Students' suggested variations and generalizations
(and some comments, e.g. the importance of homogeneity
[a.k.a. “dimensional analysis”] — which is
yet another example of exploiting the symmetry of a problem)
Here are some more
[October 11: no meeting — University holiday (Columbus Day)]
October 18 (abbreviated)
Reviewing some of the induction problems; inductive construction of
(each k = 0, 1, 2, 3, …);
the role of tools like the
Online Encyclopedia of
in guessing the pattern (and getting more information)
further example: the formula n! / (k! (n-k)!)
for the k th entry of the n th row of
and some other interpretations
- Introduction to generatingfunctionology (yes, the single-word
typesetting is a joke, but blame
Wilf for it, not me), via Pascal's
triangle again: (1+x)n
as a generating polynomial for the nth row,
proved by induction and used to re-explain the fact that the sum of
all the entries in that row is 2n
and to find the sum of their squares via the
xn coefficient of
(1+x)n (1+x)n = (1+x)2n.