Course webpage for
Freshman Seminar 24i: Mathematical Problem Solving (Fall 2008)
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
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
General considerations I: where do problems/puzzles come from
and why we care about them. Examples: folk problems,
real-world™ 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:
51/2 + 131/2 or 341/2
-- and why are they so close? Can solve by calculator, but
that doesn't feel quite right although it can be made
[cf. floor(exp(581/2π)), or ask Google Calculator for
the 4th root exp(581/2π/4).]
Two other solutions; some presentation (expository) issues.
The general formula for
a1/2 + b1/2 vs. c1/2
and its unexpected S3 symmetry leads to connections with
Heron's formula and the Minkowski and Cauchy(-Schwarz/Bunyakovsky)
inequalities. What happens for
(a,b,c) = (Fn,Fn+2,Fn+4)
A sample application of Cauchy-Schwarz: minimize
(1/x1) + (1/x2) + (1/x3)
subject to x1 + x2 + x3 = 30.
(And note again the symmetry of problem and solution.)
We'll treat inequalities and max/min problems more systematically
later in the semester.
Here are some more
(and the LaTeX source).
Go over last week's problem: for P inside triangle ABC, let
dA, dB, dC be the distances from
P to the sides opposite A,B,C respectively. Given ABC,
what is the minimum of
1/dA + 1/dB + 1/dC?
[Use area(ABC)=area(APB)+area(BPC)+area(CPA) to get a
linear relation on dA, dB, dC;
then use Cauchy-Schwarz 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 re-using variable names
(even lower- and upper-case versions of the same letter unless
they are structurally linked, as in vertices A,B,C and side-lengths
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.
induction, introduced via the
Frobenius congruence between (x+y)p and
xp+yp mod p
and the formula for the sum of the angles of an n-gon.
Base case (Sn0), inductive hypothesis
(Sk), inductive step (Sk implies Sk+1).
Variations: “strong induction”
(equivalently: apply induction to the statement
“Sk is true for each k between n0 and n”
rather than to Sn itself);
proof by contradiction via least counterexample
(equivaletly: proof by “infinite descent”);
double induction (as in the formula n!/(k!(n-k)!)
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 problem-solving
technique in general -- recall also the discussion last week
about the OEIS =
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
generating function problems
(and the LaTeX source).
- 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 hockey-stick 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 n-th 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
[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 n-th 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,n-k).]
- 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 Knight-path problem #4 ---
speaking of which, did anybody look it up in the
- Geometry using Cartesian coordinates, vectors,
barycentric coordinates, and complex numbers:
centroid (A+B+C)/3 of triangle ABC trisects its medians
(also proved via equal-area 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(θ) = ei&theta
and some of its uses; start on product of distances in a regular
Solutions of problems postponed from previous weeks:
Induction 2(ii) and 6; the last generating-function 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 A-A'=A+rB+r2C where
r=“cis(120)” is a complex cube root of unity,
and likewise B-B' and C-C'.
Also: introduction to the 2-dimensional cross product,
these further problems
(and the LaTeX source).
- The basic cyclotomic identity: if ω is a primitive
n-th root of unity such as exp(2πi/n)
(a.k.a. “cis(360/n)”) then
= xn - 1
(guessed by trying n=1,2,3,4,5, and proved using invariance under
multiplication of x by ω). Application:
which completes the solution of the problem on product of distances
in a regular n-gon. 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 two-dimensional cross-product, and some connections
(multiplicativity of 2x2 determinants,
cross-product formula for polygon areas).
Can you use its properties to give an alternative proof of Menelaus?
Some problems on
convexity and Jensen's inequality
(and the LaTeX source).
- Finish cross-product problems (except 8-10 due to illness),
- 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 root-of-unity 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 n-gon inscribed in a circle,
and to AM-GM inequality
(arithmetic mean ≥ geometric mean);
special cases: Jensen for x2 and 1/x
are familiar consequences of Cauchy-Schwarz
- 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 (45-45-90 triangle),
- triangular with a right triangle at the wall (30-60-90 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
- 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 270-degree angle, require 2-segment 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
right-angled corner and a triangle of permieter P
[easier to solve as AM-GM problem: maximize abc/6 given
- Progress towards isoperimetric inequality for n-gons:
a maximal n-gon 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; Heine-Borel: compact subsets of
Some considerations of the artificial problem-solving environment
that is the coming Putnam exam; recent Putnam examples
(full statement of problems and solutions
- 2006-A4 (additivity of expected values,
a.k.a. interchange of summations);
- 2005-B2 (yet another appearance of some of our standard inequalities);
- 2004-A3 (pattern detection and induction);
- 2004-B2 (an offbeat use of binomial coefficients);
- 2003-B5 (using our beloved(?) Fermat point and complex-number geometry);
- 2003-B2 (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).
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
- 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 Heine-Borel theorem,
which describes compact subsets of Rn)
and application to the isoperimetric theorem for n-gons.
Your final problems (with italicized further commentary,
and [bracketed] additional problems that we didn't have time for):
- Generating-function 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 n-th Lucas number Ln
(starting with L0=2) is
φn + (φ')n
φ = (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
φ20 ~ 15126.999934
approximate L19=9349 and
L20=15127 from above and below
respectively; the formula
Ln = F2n / Fn.
- [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 5m-by-5m playpen; nurse (named "Lionel"
after Sanjay's story) can pick up the babies in any
1m-by-1m 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
- [John again (slightly edited): A final 101-problem 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
Z3 in 3-dimenionsal space
R3. What is the smallest N
such that any N-element 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 x6 sin2 x + 9) / (x3 sin x)
- Alexander: find the maximal absolute value of
x + y (sin x - cos x) + z (sin x + cos x)
on the radius-r sphere
x2 + y2 + z2
- 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 - 2n + 3n - 4n + - ...
+ (-1)x+1 xn.
- Rachel: The sum of the first n cubes equals the square
of the sum of the first n numbers (e.g.
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 side-length n,
but the n-th 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 x3?
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 k-dimensional ball that will fit
into an n-dimensional 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
Čebyev'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 mod-9 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
of derangement numbers, i.e. the sum over
dn xn/n! ?]
- Aaron: How many valid Nurikabe patterns in an m-by-n 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
research-level problem. It is not too hard to get upper and
lower bounds proportional to Cmn
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 non-mathematical (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...)