Course webpage for
Freshman Seminar 24i: Mathematical Problem Solving (Fall 2009)
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 2
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
Zach on injective polynomials and me on sphere packings,
and more details on some of the other favorites)

Expectations, and organizational / administrative details

Some initial problems to think about: three 5x5 and three 7x7
Kenken puzzles; which of
5^{1/2} + 13^{1/2} and
34^{1/2} is larger?
September 14

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?

Solving two of the Kenken puzzles

General considerations I:
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 21

Progress report on small nonzero D(a,b,c) values:
D(1,1,1) = 3,
not directly of much use for our purpose (since
1^{1/2} + 1^{1/2} vs. 1^{1/2}
is even less impressive than
1^{1/2} + 1^{1/2} vs. 2^{1/2}),
but suggestive: using narrow triangles on a triangular grid instead of
a square one, we can get bigger examples such as
D(3,7,19) = 3. But can we make D as small as 1 or 2
(or for that matter solve D(a,b,c) = +3 ?)

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.

More on the triangle inequality: some further applications
(reflection, bug on a Rubik's cube  can we make this one trickier?),
and the surprising difficulty of the Euclidean proof. 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?], or use the trick
with the quadratic formula and the nonnegativity of
a_{1}v_{1} + a_{2}v_{2}^{2}
 as we did earlier for xx^{2}.

Sample applications:
 The formula for the angle between two nonzero
vectors v,v' (it's the angle whose cosine is
<v,v'>/vv', where
<v,v'> is the “dot product”
(a.k.a. “inner product”, “scalar product”)
of v and v'.
 Also, in three dimensions, the difference
(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};
is the squared length of the “cross product” of the two vectors.
 Using CauchySchwarz to find the distance from the origin to
a line or plane, and the minimum of 1/a + 1/b + 1/c over
positive numbers a, b, c subject to a + b + c = 30.
For most of this last group of examples, you could (but don't really
want to) alternatively find the minimum using standard tools of
differential calculus.
October 5
 Solution by CauchySchwarz of a geometric minimization problem:
given 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):
 minimize a weighted sum of distances?
[careful that the weights aren't too lopsided!]
 minimize the sum of the squared distances,
or of the distances' inverses?
[the latter might not have a very simple solution]
 drop the hypothesis that the triangle be acute,
or that the point be inside the triangle?
 instead of a triangle, how about four or more points?
Four actually turns out to be easier!
[But 5 or more is known to be intractable, though
special cases can be done, e.g. a regular ngon,
or a hexagon ABCDEF whose diagonals AD,BE,CF meet at a point]
 [while we're at it, imagine four points in space,
or five in hyperspace, etc.]
 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 soap pizza produced by
n straight cuts; the inductive proof of Fermat's little theorem
(and another misleading pattern:
341=11*31 is the first (counter)example where
2^{p}2 is a multiple of p
but p is not prime).
October 15
More about induction, mostly motivated by Pascal's triangle:
 Sometimes we want to prove some S_{n}, but must find
a more general statement T_{n} for which
T_{k} implies T_{k+1} (and not just S_{k+1}!)
to make the induction work (and that's also one trick for
making an induction problem harder);
 Various techniques for guessing the pattern
to prove inductively, ranging from special cases to solving for the
coefficients to searching for the sequence online on Google or,
better yet, the OEIS =
Online Encyclopedia of
Integer Sequences);
 Induction and its variants as a basic structural property of
the natural numbers;

Avoiding (or more honestly, hiding) induction:
having established inductively basic results such as
the distributive law for arbitrarily long sums,
or telescoping cancellation, use those results
rather than explicitly carry out a new induction proof.
October 19
 The equivalence of “infinite descent” with induction
(via “strong induction”); the grounding of both of these
techniques in the “wellordering” of the set
{0,1,2,3,...} of whole numbers (totally ordered [trichotomy],
and every nonempty subset has a minimum). Finite wellordered sets
determined up to isomorphism by their cardinality;
infinite sets, not so, even countably infinite ones, e.g.
{0,1,2,3,...,ω} and much more complicated examples
(anyone for ω^{ωω}?).
 Proof by infinite descent that if
b and c are positive integers such that
c^{2}  bc  b^{2} = 1
then b and c are consecutive Fibonacci numbers.
The converse was seen by induction last week. Any Fibonaccimutant
sequence with a different initial pair, e.g.\ the Lucas sequence
1, 3, 4, 7, 11, 18, ...,
has the analogous property that the value of
c^{2}  bc  b^{2}
at consecutive pairs (b,c) is constant; this can be shown
either by induction, or by writing (b,c) as a linear
combination of the initial pair whose coefficients are (nonmutant)
Fibonacci numbers [this too uses induction] and then doing some algebra.
Does the converse hold again?
 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}.
October 26
 Go over some of the generatingpolynomial problems from last week.
Is there a more intuitive explanation for the formula for the sum over
j=0,1,2,...,n of
Binomial(n, j)^{2}?
An unexpected solution to the Kingpath enumeration problem using
powers of a 32x32 “transfer matrix” 
a useful technique (which was a mainstay of my Math and Chess seminar
some years ago), and an example of what's called “dynamical
programming”, though here needlessly complicated, being equivalent
to a more familiar approach (a Pascallike triangle with three choices
at each point instead of Pascal's two) and also to a 7x7
transfer matrix that keeps track only of columns. Any of these methods
will also handle the variant of counting 7move paths
to f8 or g8, though the discrepancy between the answer and the
enumeration on an unbounded board still takes some other ideas
to explain.
 A further matrixpower digression: a simple 2x2 matrix whose
powers give Fibonacci numbers and explain (via determinants) why
F_{n1}F_{n+1}  F_{n}^{2} = (1)^{n}.
It even works for negative n once we've figured out what
F_{n} should be for n<0.
 Basic examples of generating functions (other than polynomials)
and operations on them, including multiplication which corresponds to
convolution of the coefficient sequences. [BTW this is useful
even for generating polynomials, e.g. for the distribution of the
sum of independently thrown dice with known probabilities.] Also
basic changes of variable, and going from
Σ_{n}a_{n}x^{n} to
Σ_{n}na_{n}x^{n}
by differentiating with respect to x
followed by multiplication by x
(so sometimes a generatingfunction solution requires solving
a differential equation!).
The generating function for (1+x)^{α}
for arbitrary exponent α, via Taylor's formula: if
A(x)=Σ_{n}a_{n}x^{n}
then a_{n} is 1/n! times the value at
x=0 of the nth derivative of A.
For A(x)=(1+x)^{α},
we find that again a_{n} is
Binomial(α, n) 
but we need to be careful interpreting this when α is not
a natural number. This actually arises in practice: using
generating functions we find that the nth Catalan number is
(1)^{n} 2^{2n+1} Binomial(1/2, n+1),
but that still takes a bit of work to identify with the more familiar
Binomial(2n, n) / (n+1)...
[from 2008] Here are some more
generating function problems
(and the LaTeX source).
November 2
 Presentations of solutions to problems from last week:
 Fibonaccilike sequences with
a(n+1) = a(n1) + k a(n)
for some constant k:
(1)^{n} [a(n)^{2}  a(n1)a(n+1)]
is still constant. The bracketed expression is also
a(n)^{2}  k a(n1) a(n)  a(n1)^{2};
does the sequence with a(0)=0 and a(1)=1
account for all solutions of
y^{2}kxyx^{2}
as was the case for the Fibonacci sequence (k=1)?
What other Fibonacci properties (such as the formula for
F_{n}) generalize? What happens for
a more general recursion like
a(n+1) = k a(n1) + k' a(n), or socalled
Tribonacci sequences each of whose terms is the sum of the
previous three?
 Proof that our formula
(1)^{n} 2^{2n+1} Binomial(1/2, n+1),
for the nth Catalan number agrees with the canonical
Binomial(2n, n) / (n+1)  unexpectedly by induction,
so also show the more standard approach via
1 · 3 · 5 · · · (2n1) =
(1 · 2 · 3 · 4 · 5 · 6 · · · (2n1) · (2n)) / (2 · 4 · 6 · · · 2n)
= (2n)! / (2^{n} n!)
[and be careful to distinguish "(2n)!" from "2n!" = 2·n!].
 Problem 5: the generating function for partial sums, a.k.a.
convolution with (1,1,1,...); and application to the "hockey stick"
identity, again with an unexpected concluding induction, using
the Pascal recursion for binomial coefficients rather than
the binomial expansion of (1x)^{(k+1)}.
 Problem 6: Partial fraction decomposition of
1/(1xx^{2}), and the closed form for Fibonacci
(though the solvers used not the generating function but
the fact that any Fibonacci recursion yields
a(n)=F_{n1}a(0)+F_{n}a(1),
together with the fact that a(n)=r^{n}
works if r is the Golden Ratio or its conjugate, to find F(n)
by solving simultaneous linear equations!)
 Introduction to convexity, via problems of maximizing perimeter
or area of ngon inscribed in a given circle, or
volume of box or open box with given surface area.
Jensen's inequality; further applications: AMGM inequality
(arithmetic mean ≥ geometric mean) via convexity of logarithm;
special cases: Jensen for x^{2} and
1/x are familiar consequences of CauchySchwarz;
answer of openbox problem suggests reflection trick to reduce to
closedbox problem; a hint of the importance for compactness:
what's the maximal volume enclosed by a "fence" (box without
both the top and the bottom faces) of given area?...
November 9
 Presentations of solutions to problems from last week:
9; 8 (except for equality condition, via convexity of the
square root rather than the expected CauchySchwarz); and most of 4.

Some applications of the Dirichlet Box (a.k.a. Pigeonhole) Principle:
 If gcd(p,q)=1 then the fractions a/p, b/q
interleave perfectly with the fractions c/(p+q)
(a finite version of
Beatty's Theorem  to see the connection,
multiply by p+q and let
r=(p+q)/p, s=(p+q)/q)
 There exists x such that bmx1 iff gcd(m,b)=1
(the "if" direction is the harder one, proved by showing that
in fact bmxc has a unique solution with
0≤x<b for each c);
 Existence of a “Garden of Eden” in Conway's
Game of Life (WAY bigger than the small examples shown
here, which were themselves
improved only a few years ago)
 Introduction to Ramsey theory, which is a canonical application
of the Principle
Here are some pigeonhole problems from the 2009
PCMI.
[Yes, the concluding (nonpigeonhole) problem A7
should end with a period, not a question mark.]
November 16

Report on the weekend's progress on the Erdös problem concerning
sumdistinct sets, and comparisons with the previous literature.
 Geometry using Cartesian coordinates, vectors,
barycentric coordinates, and complex numbers:
centroid (A+B+C)/3 of triangle ABC trisects its medians
;
van Aubel's theorem (cf.
“Napoleon's theorem”  can you formulate
the proof outlined in the Wikipage in terms of complex numbers?);
cis(θ) = cos(θ)+i sin(θ) =
e^{iθ}, and a bit about complex roots of unity