Thanks to all those who came on Saturday to take part in the 79th Putnam Mathematical Competition! Now I invite everyone to this week's Putnam workshop meetings (Dec. 4,6: TuTh 2-3:30, 3113 Etcheverry) in order to discuss solutions to the problems.

Mock-Putnam, a local math Olympiad, intended to provide some training, and also help me to select the team of three to officially represent UC Berkeley in this year's Putnam Mathematical Competition, will be held on Friday, September 28, from 4 to 7 pm, in 1015 Evans Finally I've finished grading Mock Putnam, so you are welcome to pick your papers in my office, 701 Evans. 34 students took part, and many did quite well. For instance, 15 students solved 3 or more problems. But the best result was achieved by Ray Li, who fell just a little short of solving all the 6 problems correctly. Congratulations, Ray!

Fall-18. Math 191 (ccn 22450): Putnam Workshop

Instructor: Alexander Givental
Meetings: TuTh 2-3:30 p.m. in 3113 Etcheverry
Office hours: Wed 4-6 p.m. in 701 Evans

This class will function as a problem-solving seminar intended, in the first place, for those who plan to take the Putnam Exam, the US and Canada math Olympiad for college students (which will be held on Saturday, December 3, 2016). Our objectives will be to build participant's confidence in solving challenging math problems and, more importantly, to learn interesting mathematics, using materials of various Mathematical Circles and Olympiads as motivation.

Useful links:
Past Putnam Exams 1980--2010
Introduction to LaTeX -- Harvard Math Dept
Remote TeXeR at the Art of Problem Solving website

Final: In lieu of the final exam, your participation in the Putnam Competition on Saturday, Dec. 1(?), 2018 is required.
Homework: is due weekly on Thursdays in class. While solutions to all past Putnam problems are available online, reading them before (or even after)submitting your homework is strongly discouraged. However, if for some reason a solution of yours is based on one found online, this should be clearly indicated at the start of the submitted solution (see the rule against "academic plagiarism" below): Our grader's time is valuable and should not be wasted on reading and commenting solutions copied from the web.
Grading: Your best effort during the semester plus full participation in the Putnam competition will be rewarded with an A.

Three rules:

  • The use of outside materials or collaboration are not prohibited, but each instance must be explicitly acknowledged.
    Failure to acknowledge one's use of somebody else's ideas is commonly known as academic plagiarism.
  • As a means for developing clear writing style, you are allowed maximum 1/2-page per problem.
  • As a means for offsetting the burden of the previous rule, you are advised to typeset your solutions in LaTeX (see the links above).

    HW1, due Th, Aug. 30: Solve the following problems:
    1. 45 points lie on the line AB outside the segment [A,B]. Prove that the sum of their distances to A differs from the sum of their distances to B.
    2. 51 points are scattered in the square of 1 meter x 1 meter. Prove that one can place a square of size 20 cm x 20 cm in such a way that it covers at least 3 of the points.
    3. Prove that for every integer n, divisible by neither 2 nor 5, there exists an integer m, whose decimal representation consists only of 1s, which is divisible by n (e.g. for n=13, we have m=111111 divisible by 13 ).
    4. . Prove that the connected components of the complement to a closed (possibly self-intersecting) polygonal line on the plane can be colored into 2 colors so that no two components of the same color share a bord er segment. ( Remark: As one of the students, Ajay Kumar Raja, noted, the statement won't be true unless one prohibits the polygonal line to trace the same edges more than once.)
    5. Prove that if x+1/x is an integer, then x^n+1/x^n are integers for all integers n.
    6. n distinct points on a circle are pairwise connected by ("n-choose-2") segments. Find the number of regions into which these segments divide the disk, assuming that no three segments intersect at the same point.

    HW2, due Th, Sep. 6:
    1. Find a winning strategy (and the winning player) in the following game, which starts with number 2: Two players in turn add to the current number any natural number smaller than it; the player who reaches 1000 wins.
    2. Let A be the sum of the digits of 4444^{4444} (4444 to the power 4444), and let B be the sum of the digits of A. Find the sum of the digits of B.
    3. Find the greatest common divisor of 111...111 (1001 ones) and 11...11 (700 ones).
    4. Prove that 300^{3000}-1 (one less than 300 to the power 3000) is divisible by 1001.
    5. Let p be prime other than 3. Prove that 11...11 (p ones) is not divisible by p.
    6. Can a knight travelling on a 4x4-chessboard with the four 1x1-corners removed visit each square exactly once and return to the starting position?

    HW3, due Th., Sep. 13:
    1. Show that the sum of the squares of the binomial coefficients "n-choose-k" over all k and fixed n is equal to "2n-choose-n". (Try to solve it by both methods: directy combinatorial and using generating functions.)
    2. Show that over Z/pZ, where p is prime, (x+y)^p=x^p+y^p (here x,y are not integers but variables). Give two applications: (a) derive Fermat's little theorem; (b) using special case for p=2, draw the entire (infinite) Pascal's triangle modulo 2.
    3. Let 1< d_1, d_2, ... , d_{12} < 12 be twelve numbers between 1 and 12. Prove that there exist three of them which are side lengths of an acute triangle.
    4. A log is divided by 12 blue marks into 13 equal parts, by 16 red marks into 17 equal parts, and then cut into 30 equal pieces. Show that each piece except the first and last ones contains one red or one blue mark.
    5. How many different ways are there to tile the strip of 16 cells (16x1) by "domino" (2x1) and "monomino" (1x1) pieces?
    6. Find the number of geometrically different cubes whose faces are painted into one of the three RGB (Red-Green-Blue) colors. (Two colorings are considered geometrically the same, if they can be identified by rotating the cube.)

    Handout on determinants (theory and exercises)

    HW4, due Th., Sep. 20:
    Do eercises 235,237,239,240,241 from the above handout on determinants, and solve the following problem:
    Compute the number of different necklaces formed by 17 black or white beads of the same spherical chape and size threaded on a circular thread. (The necklaces which can be obtained from each other by rotating and/or flipping them in space are considered the same.)

    HW5, due Th., Sep. 27: Solve Putnam problems 2007 (B1, B2, B4) and 2008 (A1, A5, B3) from Putnam archive

    HW 6, due Th, Oct. 4: If you didn't go to Mock-Putnam on Friday, solve the problems as a HW; if you did go, finish solving the rest (or relax, if you've already done your best). We will discuss the solutionsin class on Th.

    HW 7, due Th, Oct. 11: Solve problems A1, A5, B1, B2, B4 from Putnam 2009, and the following problem:
    Given a convex polyhedron, show that the exterior normal vectors to the faces of the polyhedron of the lengths equal to the areas of the faces iadd up to zero. Gneralize to the integral of the unit normal vector over the area of a closed surface in space.

    HW 8, due Th. Oct 18: Solve A3, A4, B1, B4, B5, B6 from Putnam 2010.

    HW 9, due Th. Oct. 25: Solve A1, A2, A4, B1, B3, B4 from year 2011.

    HW 10, due Th., Nov. 2: Solve A3, A5, B1, B2, B5, B6 from Putnam 2012.

    HW 11, due Th., Nov. 8: Solve A1, A3, B1, B2, B3 from Putnam 2013 and B3 from Putnam 2014.

    HW 12, due Th., Nov. 15: Solve A1, B1 from Putnam 2014 and A1, A2, A4, B1 from Putnam 2015.

    There is no point to submit further hw, since there is no time to get any feedback on it. So, I propose in the remaining 3 meetings to focus on some Putnam problems from 2016 and 2017. Namely, for the meeting on Tue, Nov. 20, let's discuss A1, A3, and B4 from 2016, and over the Thanksgiving weekend, if you have time, try to solve as many of Putnam 2017 problems as you can -- we will discuss them in the last week of November.