Fall-19. Math 191 (ccn 19502): Putnam Workshop

For those who have registered for the 80th Putnam Mathematical Competition, it is time to sharpen their minds and # 2 pencils for the actual event. It will happen on Saturday, December 7, in room 145 Dwinelle. You must come by 7:30 am, since there will be some organizational work to do before the competition begins. Bring sharpened pencils, erasers, and your student ID. You will also need to remember your UC Berkeley email: it serves as the assurance that you are a UC Berkeley student. Do not bring your own scratch paper - it is not allowed. Plan on spending the whole day -- Session A: 8-11 am, Session B: 1-4 pm.

Instructor: Alexander Givental
Meetings: TuTh 12:30-2 p.m. in 3 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 competition for college students (which will be held on Saturday, December 7, 2019). 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. 7 (?), 2019 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, Sep. 5:
    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 border segment. ( Remark: For the statement to be true one should assume that the polygonal line doesn't 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. 12:
    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. Let p be prime other than 3. Prove that 11...11 (p ones) is not divisible by p.
    5. 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?
    6. Evaluate the line integral \int (xdy-ydx)/(x^2+y^2) along the boundary of the square |x|,|y|<1 oriented counter-clockwise.

    HW3, due Th., Sep.19:
    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.)

    HW4, due Th., Sep. 26:
    1. On a 3x3 chess board, two white knights are situated in the 2 lower corners (a1 and c1) and two black knights in the two upper ones (a3 and c3). Can they, using the usual knight moves, move to the position a1 and c3 for white knights, and a3 and c1 for black ones?
    2. Which of the two players has a winning strategy in the following game: From a pile of 20 coins, a player takes away one or two coins in each move, and the player who takes the last coin wins.
    3. Let p be prime. Show that the numerator m of the fraction m/n = 1+1/2+1/3+...+1/(p-1) is divisible by p.
    4. A code lock is organized as a 4 × 4 switch board. Changing a switch from “up” to “down” position or vice versa automatically reverses positions of all the other six switches in the same row and column as the first one. In the unlocked position, all switches are up. Find an algorithm of unlocking the code lock starting from any given initial configuration of the switches.
    5. On each side of n cards, one of the numbers 1, 2, . . . , n is written in such a way that overall each of the numbers occurs exactly twice. Prove that the cards can be laid out on the table in such a way that all numbers from 1 through n will be on the top sides.
    6. Find all numbers whose leftmost digit is 1, and which double when their rightmost digit is moved to the leftmost decimal place.

    HW5, due Th, Oct. 3: Read handout on determinants (theory and exercises)
    Solve exercises 235,237,239,240,241 from the above handout on determinants, and 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.)

    HW6, due Th, Oct.10: Solve Putnam problems 2007 (B1, B2, B4) and 2008 (A1, A5, B3) from Putnam archive

    HW7, due Tuesday(!) Oct. 22: 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 add up to zero. Gneralize to the integral of the unit normal vector over the area of a closed surface in space.

    HW8, due Tue, Oct. 29: Solve A3,A4,B1,B6 from Putnam 2010, A4 from Putnam-2011, and the following
    Problem. We have: (...5)^2=...5 and (...6)^2=...6. Generalize these facts; namely show that beside ...000 and ...001 there are two more decimal sequences infinite to the left with the property that for each k>0, if an integer ends with k rightmost digits of this sequence, then its square ends with the same k digits.

    HW9, due Tue, Nov. 5: Solve B1,B3 from Putnam 2011, A3,B5,B6 from Putnam 2012. and A1 from Putnam 2013.

    HW10, due Tue, Nov. 12: Solve A3, A5, B1, B2 from Putnam 2013, and A2, B3 from Putnam 2014.

    HW11, due Tue, Nov. 19: Solve A3 from Putnam 2014, A1, A2, B1 from Putnam 2015, A4, B3 from Putnam 2016.
    ,
    HW12, due Tue, Nov. 26: Solve A3, A4, A6, B1, B3, B6 from Putnam 2017.

    HW13, due Tue, Dec. 3: Solve as many problems as you can from Putnam 2018, and be ready to discuss them in class, but don't submit your solutions in writing.