How to Solve It

Course Description and Grading Breakdown

The William Lowell Putnam Mathematics Competition is the most prestigious annual contest for college students. While the problems only employ machinery from the standard undergraduate curriculum, the ability to solve them requires a great deal of ingenuity. This can be developed through systematic and specific training, and it is this class' aim to assist the interested students in the preparation for the Putnam exam. Beyond the competition itself, problem solving is an essential skill in every discipline, so at the same time we will use the contest as an excuse to develop this ability through challenging (but fun) problems. These problems will generally come from mathematical competitions, but the syllabus will be constructed around carefully-selected topics which simultaneously develop problem solving techniques and inspire discussions about more advanced mathematics. Our aim is to use the competition problems to provide a tour through many interesting topics, and to expose a bridge to higher mathematics.   

Grading will be based on attendance and weekly homework. Caltech students who are not officially enrolled are welcome to participate, but should not hand in homework.

Course Meeting Time and Location
Tuesday
7:00 - 8:55 pm
103 Downs Physics Laboratory (DWN)

Course Instructor Contact Information and Office Hours
276 Cahill Center for Astronomy and Astrophysics

210-I Math Building (Building 15)


Office Hours
Baby Putnam Sunday
8:00 - 9:00pm
103 Downs Physics Laboratory (DWN)


Contest and Course Schedule

The Seventy Eight Putnam Examination will be held on Saturday, December 2nd, 2017It will consist of two sessions of three hours each. Also, do not forget to register. You can do that by sending an e-mail to Meagan Heirwegh. The deadline is Monday October 9th at noon. 

The rough schedule for the quarter below.

 DateTopic 
      09/26 counting strategies: tricks with binomial coefficients, comparing coefficients in  (polynomial) identities, bijections/involution arguments, recursion, induction,  inclusion-exclusion, Bonferroni inequalities, double counting (graph   theory/combinatorial geometry examples)
      10/3 linear algebra: properties of and ways of computing determinants, games one  can play with eigenvalues, nilpotent matrices, Cayley-Hamilton, amplifying a  statement about invertible matrices to general matrices, enumerative questions  which involve determinants (e.g. number of odd permutations without fixed   points)
     10/10 independence and some geometric ideas: triangles with integer coordinates   and their areas, Pick's theorem, other area formulas, AM-GM, showing that A <=   B by providing A linearly independent vectors inside a vector space of   dimension B, extending statements from rationals to reals by taking a vector   space over Q, rank-nullity theorem
     10/17 polynomials: a-b divides f(a)-f(b) for polynomials with integer coefficients,   Schur's theorem about the primes dividing the values of f on the integers,   comparing coefficients in polynomial equations, Gauss' Lemma, Eisenstein's   irreducibility criterion and cyclotomic polynomials, root localization with   respect to the unit disk, Rouche's theorem, Perron's irreducibility criterion,   Gauss-Lucas theorem.
     10/24 inequalities: discrete: AM-GM (regular and weighted version), Cauchy-Schwarz, Jensen, Karamata's   majorization/stochastic dominance inequality, Muirhead, Schur's three variable inequality; integral inequalities: Cauchy-Schwarz, Holder, Minkowski, log convexity of L_p norm (proofs with Holder and tensor power trick)
     10/31
  5pm-7pm
 calculus/real analysis: convergent sequences of integers (and rigidity   consequences), Rolle and zeroes of derivatives, Mean-Value theorem and   how to use it to solve mean value problems, interchanging the integral   with the limit (MCT and DCT) in a couple of explicit computations; an   example of Stolz-Cesaro
     11/7 real analysis continued: Stolz-Cesaro theorem, interchanging the integral   with the limit once again, intermediate value property in action, Fermat's   theorem (about stationary points) in "inverse" mean-value problems; (set)   connectedness is preserved by continuity (and how this can be useful for   Fermat if the target is one-dimensional); side note on a few properties of   skew-symmetric (eigenvalues are purely imaginary and the principal   minors, like the determinant itself, are nonnegative)
     11/14
  5pm-7pm
 group/number theory with Vlad Matei from UC Irvine: easy facts about   subgroups, the center of a group, centralizer of an element, Lagrange's   theorem, Cauchy's theorem (about elements of prime order), Sylow   theorems, actions of groups on a set, class equation formula, every   group  of order p^2 is abelian, probability that two arbitrary elements   commute is bounded by 5/8; some facts about permutation groups.
     11/21 functional equations: univariate equations which rely on some kind of "cyclicity" or linear recurrences; Cauchy's equation and reductions to it,  some substitution tricks, exploiting surjectivity, looking at fixed points
     11/28 probability (more like probabilistic method): some prelude on Sperner's theorem, LYM, and a theorem of  Deza and Frankl about intersecting permutations; union bound and linearity of expectation applications: expected number of fixed points of a permutations, alternate proof of Sperner, lower bound for diagonal Ramsey number; alteration method (a lower bound for the size of the largest Sidon subset of a set of n reals)
     12/02      Putnam exam


Course Policies

You are expected to attend class and submit homework every week. You should hand in carefully written solutions to exactly three problems for each assignment. Problem sets will usually contain more problems and you are encouraged to work on more than three for your own enjoyment, but they will not be graded.

Your goal in this class should be to learn the largely individual skill of problem-solving, so collaboration on the homework (before having solved three problems independently), while not forbidden, is rather discouraged. You should spend a significant amount of time tackling a problem on your own before you ask a friend or consult the internet. 

Assignments

Files can be found at the bottom of the page.

 Date PostedAssignment Due Date 
         09/26                     hw1.pdf         10/3    
         10/03             hw2.pdf         10/10
        10/10            hw3.pdf        10/17
        10/17                hw4.pdf            10/24
        10/24                   hw5.pdf        10/31
        10/31            hw6.pdf            11/7
        11/7                hw7.pdf        11/21
        11/21            hw8.pdf      optional


Resources

I will send frequent e-mails with various reading recommendations based on the topics we will be discussing. In addition to these, you are also encouraged to consult:

Putnam archive by Kiran Kedlaya. This page contains all the problems and solutions from the recent Putnam exams.
Putnam and Beyond by Titu Andreescu and Razvan Gelca. This book is available electronically via the Caltech library.







Ċ
hw1.pdf
(113k)
Cosmin Pohoata,
Sep 26, 2017, 6:36 PM
Ċ
hw2.pdf
(101k)
Cosmin Pohoata,
Oct 3, 2017, 5:21 PM
Ċ
hw3.pdf
(96k)
Cosmin Pohoata,
Oct 10, 2017, 4:18 PM
Ċ
hw4.pdf
(44k)
Cosmin Pohoata,
Oct 17, 2017, 4:58 PM
Ċ
hw5.pdf
(98k)
Cosmin Pohoata,
Oct 24, 2017, 5:40 PM
Ċ
hw6.pdf
(121k)
Cosmin Pohoata,
Oct 31, 2017, 2:03 AM
Ċ
hw7.pdf
(97k)
Cosmin Pohoata,
Nov 7, 2017, 6:13 PM
Ċ
hw8.pdf
(94k)
Cosmin Pohoata,
Nov 21, 2017, 6:16 PM