Course webpage for
Freshman Seminar 24i: Mathematical Problem Solving (Fall 2010)
If you find a mistake, omission, etc., please
let me know
by email.
Your favorite problems or solutions
Here's a clearer picture of the
background pattern...
September 1
Initial meeting:

Introductions, à la Pál Erdös:
“What's your name and what's your problem?”
(from our email 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
5^{1/2} + 13^{1/2} and
34^{1/2} is larger?
September 13

Various approaches to
5^{1/2} + 13^{1/2} vs. 34^{1/2}.
How were these numbers 5, 13, 34 chosen?
Generalizations and connections: factoring
x^{2}+1 or x^{2}1;
Fibonacci numbers; the general formula
for a^{1/2} + b^{1/2} vs. c^{1/2}
via the sign of D(a,b,c) :=
a^{2} + b^{2} + c^{2}  2 (ab + ac + bc),
with unexpected extra symmetry, in turn leading us to
Heron's formula for the area of a triangle of sides
a^{1/2}, b^{1/2}, c^{1/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
September 20

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
u^{1/2} + (u+1)^{1/2}.]
Likewise D(a,b,c) = 3, starting from the
sillylooking (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
a^{2} + b^{2} + c^{2} = 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
D(
x_{1}^{2} + y_{1}^{2},
x_{2}^{2} + y_{2}^{2},
(x_{1}+x_{2})^{2}
+ (y_{1}+y_{2})^{2}
) = 4 (x_{1}y_{2}x_{2}y_{1})^{2}
[sorry, HTML doesn't handle expressions like x_{1}^{2}
as well as TeX...]. Along the way we find that
(x_{1}x_{2}+y_{1}y_{2})^{2}
≤
(x_{1}^{2}+y_{1}^{2})
(x_{2}^{2}+y_{2}^{2}),
which is one way to state the 2dimensional case of the
CauchySchwarz inequality,
whose importance and ubiquity in mathematics are hard to overstate.
Equality holds if and only if
x_{1}y_{2}=x_{2}y_{1},
which is to say if and only if the vectors
(x_{1}, y_{1}) and
(x_{2}, y_{2})
are proportional. In 3 dimensions, we find with a little more work that
D(
x_{1}^{2}
+ y_{1}^{2}
+ z_{1}^{2},
x_{2}^{2}
+ y_{2}^{2}
+ z_{2}^{2},
(x_{1}+x_{2})^{2}
+ (y_{1}+y_{2})^{2}
+ (z_{1}+z_{2})^{2}
)
equals 4 times
(x_{1}y_{2}x_{2}y_{1})^{2}
+ (y_{1}z_{2}y_{2}z_{1})^{2}
+ (z_{1}x_{2}z_{2}x_{1})^{2};
so we get the triangle inequality for vectors
(x_{1}, y_{1}, z_{1}) and
(x_{2}, y_{2}, z_{2}),
with equality if and only if one is a nonnegative multiple of the other,
and also threedimensional CauchySchwarz:
(x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{2})^{2}
≤
(x_{1}^{2}+y_{1}^{2}+z_{1}^{2})
(x_{2}^{2}+y_{2}^{2}+z_{2}^{2})
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 (n^{2}n)/2 squares
[where did I get this count of (n^{2}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
xx^{2} (a.k.a. xy if x+y=1,
which reveals a symmetry between x and 1x);
when solving an inequality problem, always try to determine
the equality condition. Introduction to the AMGM 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
without calculus.
September 27
 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
4k^{2}+4k+1 = 4(k^{2}+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
√145/144,
which comes out to 1.003466…
 Max/min problems continued: the biggest volume of a
half or fullyopen box of given surface area; more uses of
CauchySchwarz; 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
October 4
 CauchySchwarz, 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)
The “quadrilateral inequality” encountered during the
geometrical solution suggest a segue to the important technique of
induction.
Base case (S_{n0}),
inductive hypothesis (S_{k}),
inductive step (S_{k} implies S_{k+1}).
Variation: “strong induction”
(equivalently: apply induction to the statement
S_{n}:
“S_{k} is true for each k between n_{0} and n”
rather than to S_{n} 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 problemsolving technique in general,
but beware of false trails such as
3^{2}+4^{2}=5^{2},
3^{3}+4^{3}+5^{3}=6^{3}, but
3^{4}+4^{4}+5^{4}+6^{4}≠7^{4});
maximal number of slices of a pizza produced by
n straight cuts.
Here are some more
induction problems
[October 11: no meeting — University holiday (Columbus Day)]
October 18 (abbreviated)

Reviewing some of the induction problems; inductive construction of
formula for
1^{k} +
2^{k} +
3^{k} +
… +
n^{k}
(each k = 0, 1, 2, 3, …);
the role of tools like the
OEIS =
Online Encyclopedia of
Integer Sequences)
in guessing the pattern (and getting more information)

further example: the formula n! / (k! (nk)!)
for the k th entry of the n th row of
Pascal's triangle,
and some other interpretations
 Introduction to generatingfunctionology (yes, the singleword
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 reexplain the fact that the sum of
all the entries in that row is 2^{n}
and to find the sum of their squares via the
x^{n} coefficient of
(1+x)^{n} (1+x)^{n} = (1+x)^{2n}.