Course webpage for
Freshman Seminar 24i: Mathematical Problem Solving (Fall 2008)
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 15
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 Catalan numbers, Monty Hall, and Greek letters)

Expectations, and organizational / administrative details
September 22:

General considerations I: where do problems/puzzles come from
and why we care about them. Examples: folk problems,
realworld™ sources, instructional exercises,
contest problems, and open questions. In each case
the ground rules (sometimes implicit) are different.

General considerations II: how do we come up with problems?
E.g. applied sources; variations of known problems;
“reverse engineering” (a solution method/trick
in search of a problem). We can never be sure that a problem is hard.
Sometimes the poser inadvertently makes the problem
harder than intended, or indeed incorrect!
[Hopefully not in this Seminar.]

Which is larger:
5^{1/2} + 13^{1/2} or 34^{1/2}
 and why are they so close? Can solve by calculator, but
that doesn't feel quite right although it can be made
mathematically irreproachable...
[cf. floor(exp(58^{1/2}π)), or ask Google Calculator for
the 4th root exp(58^{1/2}π/4).]
Two other solutions; some presentation (expository) issues.
The general formula for
a^{1/2} + b^{1/2} vs. c^{1/2}
and its unexpected S_{3} symmetry leads to connections with
Heron's formula and the Minkowski and Cauchy(Schwarz/Bunyakovsky)
inequalities. What happens for
(a,b,c) = (F_{n},F_{n+2},F_{n+4})
[Fibonacci numbers]?

A sample application of CauchySchwarz: minimize
(1/x_{1}) + (1/x_{2}) + (1/x_{3})
subject to x_{1} + x_{2} + x_{3} = 30.
(And note again the symmetry of problem and solution.)
We'll treat inequalities and max/min problems more systematically
later in the semester.
September 29:

Go over last week's problem: for P inside triangle ABC, let
d_{A}, d_{B}, d_{C} be the distances from
P to the sides opposite A,B,C respectively. Given ABC,
what is the minimum of
1/d_{A} + 1/d_{B} + 1/d_{C}?
[Use area(ABC)=area(APB)+area(BPC)+area(CPA) to get a
linear relation on d_{A}, d_{B}, d_{C};
then use CauchySchwarz as we did last week. Be sure to show that
the resulting lower bound is attained, and thus equal to the minimum.]
Further expository issues: give the answer first (when the problem
asks for one and not just “prove that...”);
tabulate information when appropriate; avoid reusing variable names
(even lower and uppercase versions of the same letter unless
they are structurally linked, as in vertices A,B,C and sidelengths
a,b,c of a triangle); label complicated expressions and use the labels
instead of repeating formulas such as Heron's for the area of
a triangle; careful about expressions like “1/2 x”
(is that (1/2)x or 1/(2x)?); etc.
“Dimensional analysis”, and
other sanity checks such as the special case of an equilateral triangle.

Mathematical
induction, introduced via the
Frobenius congruence between (x+y)^{p} and
x^{p}+y^{p} mod p
and the formula for the sum of the angles of an ngon.
Base case (S_{n0}), inductive hypothesis
(S_{k}), inductive step (S_{k} implies S_{k+1}).
Variations: “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);
proof by contradiction via least counterexample
(equivaletly: proof by “infinite descent”);
double induction (as in the formula n!/(k!(nk)!)
for binomial coefficients) and beyond; etc.
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  recall also the discussion last week
about the OEIS =
Online
Encyclopedia of
Integer Sequences).
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.
Induction and its variants as a basic structural property of
the natural numbers.
Here are some more
induction problems
(and the LaTeX source).
October 6:
 Last week's problems (in reverse order), except 6 and 2(ii)
(no solutions yet, so deferred till next time) and 1 (little new there).
Descent argument for #5; telescoping Πroduct
(analogous to a telescoping Σum) for #4;
bijective and inductive solutions for #3;
the hockeystick identity for #2(i), and the case k=2 of #2(ii).
 1/998.999 = 0.001001002003005008013021034055089144233...
suggests the generating function for the
Fibonacci numbers appearing in the decimal expansion.
Basic examples (geometric and binomial series)
and operations (shifts, addition).
Multiplication of generating functions corresponds to
convolution of power series.
Example: sum of squares of nth row of Pascal's Triangle.
Generatingfunctionological solution of #3
 but what's “3 choose n”?
The generating function for Catalan numbers, which requires us
to unwind “1/2 choose n”.
So far, only ordinary generating functions;
a hint of exponential generating functions: the power series for
e^{ax}e^{bx}.
Here are some more
generating function problems
(and the LaTeX source).
October 13:
[A University holiday, so no official class meeting.
Instead Zach and I hold in effect an extended section,
going over generating functions and the pending problems.
Also, a more combinatorial proof of the formula for the sum
of the squares of the entries of the nth row of
Pascal's triangle: once we know it's Binomial(2n,n),
interpret Binomial(2n,n) as the number of NE paths from
(0,0) to (n,n), and group them by which point at which
the path crosses the diagonal (k,nk).]
October 20:
 Go over a couple of last week's problems
(leaving #10 for next time), and a few generalizations
(Euler's #8, and some variants of the Knightpath problem #4 
speaking of which, did anybody look it up in the
OEIS?...).
 Geometry using Cartesian coordinates, vectors,
barycentric coordinates, and complex numbers:
centroid (A+B+C)/3 of triangle ABC trisects its medians
(also proved via equalarea locus); the Euler line of a triangle;
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&theta}
and some of its uses; start on product of distances in a regular
ngon.
October 27:
Solutions of problems postponed from previous weeks:
Induction 2(ii) and 6; the last generatingfunction problem;
the easy part of the Fermat point construction via complex numbers.
Some simplifications: 2(ii) by telescoping; 6 is only barely an
induction problem (need only the formula for 1+2+...+n);
first part of 10(ii) is a special case of exponential convolution;
for Fermat, write AA'=A+rB+r^{2}C where
r=“cis(120)” is a complex cube root of unity,
and likewise BB' and CC'.
Also: introduction to the 2dimensional cross product,
see
these further problems
(and the LaTeX source).
[corrected Nov.5]
November 3:
 The basic cyclotomic identity: if ω is a primitive
nth root of unity such as exp(2πi/n)
(a.k.a. “cis(360/n)”) then
(x1)
(xω)
(xω^{2})
(1ω^{3})
...
(xω^{n1})
= x^{n}  1
(guessed by trying n=1,2,3,4,5, and proved using invariance under
multiplication of x by ω). Application:
(1ω)
(1ω^{2})
(1ω^{3})
...
(1ω^{n1})
= n,
which completes the solution of the problem on product of distances
in a regular ngon. Further cyclotomy: evaluation of
sin(18) and sin(54); how to generalize it?

Cevian challenge, completed (via
Menelaus' theorem, as it turns out):
Eucliean constructions for dividing a line segment into
n equal parts (any n) without constructing parallel lines,
indeed without using the compass except as an unmarked caliper.

The twodimensional crossproduct, and some connections
(multiplicativity of 2x2 determinants,
crossproduct formula for polygon areas).
Can you use its properties to give an alternative proof of Menelaus?
November 10:
 Finish crossproduct problems (except 810 due to illness),
including Menelaus.
 Formula for the Fermat length of the triangle
(but not yet in fully symmetric form).
 The cubic equations satisfied by cos(2π/7) and cos(2π/9),
using the rootofunity formulas for these cosines; interlude:
the formula for cos(3θ) and the trigonometric solution of
the cubic equation.
 Introduction to convexity: Jensen's inequality;
applications to biggest ngon inscribed in a circle,
and to AMGM inequality
(arithmetic mean ≥ geometric mean);
special cases: Jensen for x^{2} and 1/x
are familiar consequences of CauchySchwarz
Some problems on
convexity and Jensen's inequality
(and the LaTeX source).
[corrected Nov.17]
November 17:
 Go over problems on convexity and variations (log convexity,
midpoint convexity, and optimization in the direction opposite to
Jensen), with a couple of alternative proofs of the convexity of
sin(x) on 0 ≤ x ≤ π.
 Interlude on reflection tricks in this context:
maximal area between straight wall and a given fence that's
 rectangular (1:2 rectangle),
 triangular (454590 triangle),
 triangular with a right triangle at the wall (306090 triangle),
 quadrangular (half a regular hexagon),
 arbitrary (semicircle, à la
mathematical model of the Dido legend).
 A simple proof that π^{2}
[more honestly, that 6ζ(2)] is less than 10,
and indeed less than 9.9, by comparing a tail of the sum
for ζ(2) with a telescoping series.
 Maxima/minima with vs. without calculus
November 24:
 Your variations on reflection tricks:
 A and B are points on the same side of line l; find X on l
that minimizes AX+XB.
 Fence problem variants: maximize the area of:
 triangle with one angle against the wall specified
(mysterious angle trisection);
 replace straight wall by right angle, require fence to be in
k segments for some k=1,2,3,...,∞
 Same for any angle 2π/n  at least for n=2,4,6,...;
 replace wall by 270degree angle, require 2segment fence
meeting the wall in points equidistant from its corner.
 Tent problem: enclose maximal volume with tent of given
surface area in the shape of a triangular prism with one
(triangular) side missing;
 Given P, find maximal volume of tetrahedron between
rightangled corner and a triangle of permieter P
[easier to solve as AMGM problem: maximize abc/6 given
(a^{2}+b^{2})^{1/2}
+ (a^{2}+c^{2})^{1/2}
+ (a^{2}+c^{2})^{1/2}]
 Progress towards isoperimetric inequality for ngons:
a maximal ngon must be convex with all sides equal
 Intro. to compactness: the supremum of a subset of R;
a bounded continuous function on [0,1] must attain its supremum
(to come: boundedness is automatic; HeineBorel: compact subsets of
R^{n})
December 1:
Some considerations of the artificial problemsolving environment
that is the coming Putnam exam; recent Putnam examples
(full statement of problems and solutions
here):
 2006A4 (additivity of expected values,
a.k.a. interchange of summations);
 2005B2 (yet another appearance of some of our standard inequalities);
 2004A3 (pattern detection and induction);
 2004B2 (an offbeat use of binomial coefficients);
 2003B5 (using our beloved(?) Fermat point and complexnumber geometry);
 2003B2 (a less offbeat use of Pascal's triangle etc.);
 Plus Stanley's problems 3 and 11
(starred, so used in some past Putnam exam(s)  probably
around 1984 when I remember solving his problem 8).
December 8:

Solution of problem A5 on the past weekend's Putnam
(which happens to use some ideas we developed on
roots of unity and Pascal's triangle)

Some applications of the Dirichlet Box (a.k.a. Pigeonhole) Principle:
 If gcd(m,n)=1 then the fractions a/m, b/n
interleave perfectly with the fractions c/(m+n)
(a finite version of
Beatty's Theorem  to see the connection,
multiply by m+n and let
r=(m+n)/m, s=(m+n)/n)
 If gcd(m,n)=1 then mx≡b mod n has a unique solution
x mod n for every integer b
(cf. also Problem B4 of Saturday's Putnam)
 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
 More about compactness (basically the HeineBorel theorem,
which describes compact subsets of R^{n})
and application to the isoperimetric theorem for ngons.
December 15:

Your final problems (with italicized further commentary,
and [bracketed] additional problems that we didn't have time for):
 Generatingfunction problems:
 Sanjay: How many ways to repay a $0.33 debt
(incurred during a background playground story
with parodistically Too Much Information) using
at most 8 pennies, 8 nickels, 4 dimes, and 2 quarters?
 Michael: the closed form for the Lucas numbers
2, 1, 3, 4, 7, 11, ... :
the nth Lucas number L_{n}
(starting with L_{0}=2) is
φ^{n} + (φ')^{n}
where
φ = (1 + sqrt(5)) / 2 is the Golden Ratio and
φ' = (1  sqrt(5)) / 2 is its algebraic conjugate.
Some remarkable consequences: powers of φ get ever closer
to integers, alternating between being just over and just under
an integer, e.g.
φ^{19} ~ 9349.000107
and
φ^{20} ~ 15126.999934
approximate L_{19}=9349 and
L_{20}=15127 from above and below
respectively; the formula
L_{n} = F_{2n} / F_{n}.
 [Peter: In how many ways can 10 items be selected from
4 categories, choosing no more than 4 from each category?]
 Pigeonhole principle problems:
 John: 51 babies in 5mby5m playpen; nurse (named "Lionel"
after Sanjay's story) can pick up the babies in any
1mby1m square; show that at any moment
at least 3 babies can be picked up. But if the playpen
is a barely larger square, and the babies are small enough,
then we can place 72 of them so Lionel can pick up no more than
two at once as long as his squares must be parallel to the
playpen sides.
 [John again (slightly edited): A final 101problem marathon
is parceled out among 14 students (including Zach), each being
assigned at least one; show that some two students get
the same number of problems. Darn, next time I'll have
to assign four more problems.]
 Philip: Let E be the integer lattice
Z^{3} in 3dimenionsal space
R^{3}. What is the smallest N
such that any Nelement set in E must contain
two distinct points, say P and Q, such that the trisection points
of the segment PQ are again in E?
 Philip again: 10 [originally 6] balls are placed
in N boxes so that each box contains at least one ball
and no two boxes contain the same number of balls.
How large can N be? No, the answer is not 4;
think outside the box! (Or perhaps inside it.)
 Inequality / optimization problems:
 Peter again: find the maximal value of
(16 x^{6} sin^{2} x + 9) / (x^{3} sin x)
for 0<x<π.
 Alexander: find the maximal absolute value of
x + y (sin x  cos x) + z (sin x + cos x)
on the radiusr sphere
x^{2} + y^{2} + z^{2}
= r^{2}.
 Induction / summation problems:
 Duncan: Find a formula for the partial sums of the
alternating series 1  2 + 3  4 +  ...
and 1  4 + 9  16 +  ...;
more generally, evaluate
1  2^{n} + 3^{n}  4^{n} +  ...
+ (1)^{x+1} x^{n}.
 Rachel: The sum of the first n cubes equals the square
of the sum of the first n numbers (e.g.
1+8+27+64=(1+2+3+4)^{2}).
Prove this by induction; if possible, find a more enlightening proof.
There's a neat dissection proof showing that that a square
of side 1+2+3+...+n has the same area as a
1x1 square plus two
2x2 squares plus three
3x3 squares plus ... plus n squares of sidelength n,
but the nth step requires a kludge for even n.
 Miscellaneous topics:
 Nick: 12 students (with Nick gone to Arizona) must split into
four groups of three. How many possibilities? (More generally,
how many bridge or Hearts deals [52 cards into four hands of 13],
etc.? As often happens with such problems, there's a formula
involving a quotient of factorials, and it is not at all obvious
that it always yields an integer.)
 Colin: if x is a complex number such that
x = x+1 = 1, what is x^{3}?
A nice example of using plane geometry to solve a question
about complex numbers, rather than the other way around
which has been our usual procedure.
 [Aaron: What's the largest circle that will fit into a unit cube?
A tough question, suggested by the recent Putnam problem
that asked the same question in a hypercube. It turns out that
there's a nice answer even for the general question of the
largest kdimensional ball that will fit
into an ndimensional hypercube of unit side
 in each case the maximal diameter is the square root of
n/k  but the proof is beyond our scope.]
 Tyler: Various divisibility problems:
 How many zeros at the end of the decimal expansion of 100!
(more generally, of n! for any n)?
Also, what's the last nonzero digit?
These are perennial math competition problems.
The resulting formula also has a more serious use in
Čebyšev's proof of an approximate
prime number theorem
by comparing Stirling's approximate formula for
n! with its prime factorization.
 Why the classic divisibility test mod 3 works.
Likewise mod 9, which once "everybody" knew as
"casting out nines". This lets us find the missing
central digit of 30! in the background pattern.
Likewise the variant mod 11, which for instance lets us
recover the central digit of 38!
which is still ambiguous after the mod9 test.
 [Divisibility tests mod arbitrary powers of 2 (or 5).]
 [Tyler again: the
derangement problem. Can you find
the exponential generating function for the sequence
{d_{n}}
of derangement numbers, i.e. the sum over
n=0,1,2,... of
d_{n} x^{n}/n! ?]
 Aaron: How many valid Nurikabe patterns in an mbyn rectangle?
Even the enumeration subject to only one of the two conditions
 connectivity and absence of 2x2 "pools"  seems extremely hard,
to the point that just finding good approximate formulas is a
researchlevel problem. It is not too hard to get upper and
lower bounds proportional to C^{mn}
for some C>1
(for lower bounds, exclude the cases m=1 and n=1), but the
best value of C for large m,n is probably not known.
Never mind even the problem of estimating the number of
uniquely solvable Nurikabe puzzles!
 A final fun example of a nonmathematical (or at least not blatantly
mathematical) puzzle that will yield to some of our techniques:
White to move with King h1 and Rook f1 vs. King h8, and force
checkmate  without moving the Rook except to deliver
checkmate on the move.
(From my previous freshman seminar...)