The 74th Putnam mathematics Competition Saturday, December 7, 8-11 am and 1-4 pm (location will be announced later)

Thanks to everyone who took part in the Mock Putnam on October 4. You can get your papers back this Th, Oct. 10, 2:30-3:30 or next Tu 2:30-3:30, in 701 Evans. Solutions to the problems will be discussed on Tu, Oct. 15 during the regular meeting of this class (12:30-2, in 71 Evans)

This year, we have a clear-cut winner: Indraneel Kasmalkar, who solved correctly all the 6 problems. Congratulations, Indraneel!

The statistics of the competition was as follows: out of 35 participants, the numbers of those who more or less solved 6, 5, 4, 3, 2 and 1 problems were 1, 0, 5, 10, 5, and 7 respectively.


Putnam Competition this year will happen on Saturday, December 7, at 10 Evans, from 8 to 11 am and form 1 to 4 pm. You need to be at 10 Evans at least 20 minites early, i.e. at 7:40, to do some paperwork. Bring your student ID and pencils with erasers.

Thanks to everyone who took part in Putnam 2013. Most problems appeared rather hard, but it turns out that many of them are related to interesting mathematics. We will discuss solutions on Tu Dec. 10 and Th Dec. 12 from 12:30 to 2 pm in 31 Evans. Everyone is welcome!

Fall-13. Math 191 (ccn 54294): Putnam Workshop

Instructor: Alexander Givental
Meetings:
TuTh 12:30-2:00 p.m. in 31 Evans
Office hours: Tu 2:30--3:30 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, in December 2013. 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
LaTeX help at Art of Problem Solving website
Website of Olga Holtz (previous instructor of this workshop)
Please visit thas page, and among other materials, pay close attention to the academic honesty policy.

Homework: is due weekly on Thursdays.

Three rules:

  • Use of outside materials or collaboration are not prohibited, but each instance must be explicitly acknowledged (see Academic Honesty policy mentioned above).
  • As a means for developing clear writing style, you are allowed maximum 1/2-page per problem.
  • As a means to offset 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. What is the maximal number of kings can be placed on an 8x8 chess board so that no two of them attack each other?
    2. 25 boys and 25 girls are seated in a circle around a table. Show that both neighbors of at least one of them are boys.
    3. 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.
    4. 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.
    5. 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).
    6. Find: (a)the remainder after division of polynomila x^m-1 by polynomial x^n-1; (b) the greatest commn divisor of x^m-1 and x^n-1.

    HW2, due by Th, Sep. 12:
    1. Prove that an infinite decimal is repeating if and only if the real number it represents is a fraction.
    2. Prove that the sum of the squares of 1,2,...,n is equal to n(n+1)(2n+1)/6. Hint: Use induction on n.
    3. Prove that 1x2+2x3+...+(n-1)xn=(n-1)n(n+1)/3.
    4. The map of Flatland consists of several lines and circles dividing the plane into countries. Prove that the map can be painted into two colors in such a way that countries with a common border have opposite colors.
    5. Into how many regions is the plane divided by n straight lines, no two of which are parallel, and no three of which pass through the same point?
    6. On the boundary circle of a disk, n points are selected, and each two are connected by a chord. It happened so, that no three of the chords intersect at one point. Into how many regions is the disk divided by these chords?

    HW3, due by Th, Sep. 19:
    1. 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.
    2. Prove that 300^{3000}-1 (300 to the power 3000, minus 1) is divisible by 1001.
    3. Compute \sum_{r+s=m}(n choose r) (n choose s)
    4. Let p be prime other than 3. Prove that 11....1 (p ones) is not divisible by p.
    5. Find all those n for which the numbers "n choose k" are odd for all k=0,...,n.
    6. 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.

    HW4, due Th, Sep. 26:
    1. Two players take turns taking one or two stones off a pile of 20 stones. The player taking the last stone wins. Which player has a winning strategy?
    2. Two players, starting with number 60, and subtracting from the current number one of its divisors (1 or the number itself are allowed on the role of divisors). The player who reaches 0 looses. Whis player has a winning strategy?
    3. 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?
    4. How many different ways are there to tile the strip of 16 cells (16x1) by "domino" (2x1) and "monomino" (1x1) pieces?
    5. 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 blue mark.
    6. There are 12 coins one of which is counterfeit. It differs by weight from genuine ones, but it is not known if it is lighter or heavier. Using at most 3 weighings on balances (without arrows or weights) identify the counterfeight coin.

    HW5, due Oct. 3: Referring to handout Problems on Determinants, solve problems 34, 35, 36, 37, 38. Solve Problem A3 from Putnam-2009 .
    HW6, due Th Oct. 10: If you did not take part in the Mock Putnam on Ocober 4, solve those problems. (If you did take part, then you don't have to submit this homework.)
    HW7, due Th Oct. 17:
    1. Let F be a field. A nested chain of subspaces
    0\subset V^1\subset V^2 \subset ... \subset V^{n-1}\subset F^n
    of dimension 1,2,...,n-1 in the n-dimensional space F^n is called a complete flag in F^n. Assuming that F is finite, consisting of q elements, find the total number of complete flags in F^n.
    2. Factor x^p-x into linear factors over the field (the majic word!) Z_p or remainder modulo a given prime number p.
    3. For which primes p, the quadratic polynomial x^2+1 can be factored over Z_p?
    4. Justify division with remainders for the ring of Gaussian integers Z[i] ={ a+bi | a,b - integers }. Namely, given two non-zero Gaussian integers z, w, prove existene of Gaussian integers q and r such that |r|<|w| and z=qw+r.
    5. 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.)
    6. Compute \sqrt(6+\sart(6+\sqrt(6+... ...))), infinitely many parentheses, where \sqrt() is the positive square root function.
    HW8, due Th, Oct. 24:
    1. Prove Wilson's Theorem: If p is prime, then (p-1)!+1 is divisible by p.
    2. Prove that, up to multiplicatuion by units 1,-1,i,-i of the ring Z[i], a prime Gaussian integer must be either an ordinary integer p prime in Z, or a+bi where a^2+b^2=q is prime in Z. Give examples of such p and such q.
    3. In space, consider an ellispsoid with semi-axes A>=B>=C (e.g. given by the coordinate equation x^2/A^2+y^2/B^2+z^2/C^2=1). Let E be an ellipse obtained by intersecting the ellipsoid by a plane passing through the center of it. Prove that the semiaxes a>=b of the ellipse satisfy the inequalities A>=a>=B>=b>=C. [ By >= the sign "reater than of equal to" is meant.]
    4. To commemorate two centuries of Gauss' Disquisitiones Arithmeticae the Institute of Mathematical History is selling necklaces priced $ 62.50 each and consisting of 17 identically shaped symmetrical black or white beads moving freely on a circular band. Find the price the Institute of Historical Mathematics will have to pay for a complete collection of such necklaces.
    5.A hunter is shoting from the origin on the coordinate plane, in every other integer point of which, a round rabbit of radious \epsilon >0 is sitting. Prove that no matter what direction the shoots, the hunter is guaranteed to hit a rabbit.
    6. Let a priome p have remainder 2 modulo 3. Prove that the map x \--> x^3 defines a permutation on the multiplicative group (\Z_p)^*, and find for which p it is even and for which odd.
    HW9, due by Th, Oct. 31:
    1. Let Q=[q_{ij}] be a real symmetric matrix, the coefficient matrix of a quadratic form. Denote by D_k, k=0,1,...,n, the kxk-determinant obtained by removing all rows and columns of Q with the indices i,j>k. Suppose that all D_k are non-zero (by definition, D_0=1). Prove that there is a Q-orthogonal basis f_1,...,f_n such that each f_k lies in the first coordinate subspace Span(e_1,...,e_k) of dimension k.
    2. Derive from Problem 1 the following Sylvester's Rule: The negative inertia index of Q (i.e. the number of negative squares in the normal form) is equal to the number of sign changes in the sequence D_0,D_1,...,D_n.
    3. Given a graph with n vertices, one forms a quadratic form in n variables subtracting from the sum of the squares x_i^2 of the variables the products x_ix_j for each edge connecting the vertices i and j. (E.g. for the graph with two vertices connected by one edge, the quadratic form is x_1^2-x_1x_2+x_2^2.) The graph T_{p,q,r} has the shape of a letter T with the three legs formed by chains of edges and vertices of lengths p, q, and r (Thus, T_{p,q,r} has p+q+r edges and p+q+r+1 vertices.) Find out for which p,q, r the corresponding quadratic form is positive definite (i.e. positive everywhere outside the origin).
    4. A great circle on the sphere is obtained by intersecting it with a plane passing through the center. Three great circles partition the sphere into 8 spherical triangles. Prove that on the sphere of radius 1, the area of a spherical triangle with angles \a, \b, \c (in radians) is equal to \a + \b +\c - \pi.
    5. Find all triples (p,q,r) of integers >1 such that 1/p+1/q+1/r>1, and show that for each such a triple, the sphere can be tiled with spherical triangles with the angles \pi/p, \pi/q, and \pi/r.
    6. Let k be a positive integer. A graph is called a k-graph , if one can assign to its vertices positive integerss in such a way that for each vertex the number written in it times k is equal to the sum of the numbers written at the vertices connected to it by the edges of the graph. (E.g. the graph with two vertices connected by two edges is a 2-graph, because assigning to both vertices the number 1, we get 1x2=1+1.) Describe all 2-graphs. (Do not allow edges of a graph to connect a vertex to itself.)

    HW10, due Th, Nov. 7: Solve any 6 out of 12 problems of Putnam-1999. Beware of a typo in Problem B2: P+QP'' should be P=QP''.

    HW11, due Th, Nov. 14: Solve any 6 out of 12 problems of Putnam-2004.

    HW12, due Th, Nov. 21: Solve any 6 out of 12 problems of Putnam-2010.
    HW13, due Th, Nov. 28: Have a nice Thanksgiving!