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!