If you find a mistake, omission, etc., please let me know by e-mail.

• 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

September 22:

• 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: 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₃ 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 Cauchy-Schwarz: minimize (1/x₁) + (1/x₂) + (1/x₃) subject to x₁ + x₂ + x₃ = 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 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.
• 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 n-gon. 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₀ 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!(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 = 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.

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 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 e^axe^bx.

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 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).]

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 Knight-path 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 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(θ) = e^i&theta and some of its uses; start on product of distances in a regular n-gon.

October 27:
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+r²C 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, see
these further problems (and the LaTeX source). [corrected Nov.5]

November 3:

• 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 (x-1) (x-ω) (x-ω²) (1-ω³) ... (x-ω^n-1) = xⁿ - 1 (guessed by trying n=1,2,3,4,5, and proved using invariance under multiplication of x by ω). Application: (1-ω) (1-ω²) (1-ω³) ... (1-ω^n-1) = n, 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?

November 10:

• Finish cross-product problems (except 8-10 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 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 x² and 1/x are familiar consequences of Cauchy-Schwarz

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 (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 π² [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 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 (a²+b²)^1/2 + (a²+c²)^1/2 + (a²+c²)^1/2]
• 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 Rⁿ)

December 1: Some considerations of the artificial problem-solving environment that is the coming Putnam exam; recent Putnam examples (full statement of problems and solutions here):

• 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).

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 Heine-Borel theorem, which describes compact subsets of Rⁿ) and application to the isoperimetric theorem for n-gons.

December 15:

• 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 L_n (starting with L₀=2) is φⁿ + (φ')ⁿ 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. φ¹⁹ ~ 9349.000107 and φ²⁰ ~ 15126.999934 approximate L₁₉=9349 and L₂₀=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 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 playpen sides.
    • [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 Z³ in 3-dimenionsal space R³. 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 x⁶ sin² x + 9) / (x³ 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 radius-r sphere x² + y² + z² = r².
  • 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ⁿ + 3ⁿ - 4ⁿ + - ... + (-1)^x+1 xⁿ.
    • 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)²). 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 x³? 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 Č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 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 {d_n} of derangement numbers, i.e. the sum over n=0,1,2,... of d_n xⁿ/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 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 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...)