To those who are registered for the 85th Putnam Mathematical Competition: it is time to sharpen your minds and #2 pencils.
To actually take part in the completition, you need to come by 7:30 am on Saturday,
December 7, 2024 to Evans Hall, room 10 .
Enter through the Southwest door to the ground-level of Evans Hall, and proceed to room 10. There you will need to
1. Find and pick your set of cover sheets for solutions to all problems. For this, you should bring your 6-digit PIN assigned to you at your registration
2. Pick blank paper for writing your solutions (NOTE: you are not allowed to bring your own)
3. Pick a wrist-band; there will be security measures in place in the building, and the wrist-band will be your permit for moving around the ground floor (e.g. to the bathroom), and to reenter the bulding after the lunch break.
4. Find a seat (separated by at least one empty seat from others), set to the airplane mode and put away your cell-phones
5. Wait until I hand you Problem set A, but do not look at it (keep it face down), and wait for my signal to start working.
Fall-24. Math 191 (class # 19381): Putnam Workshop
Instructor: Alexander Givental
Meetings: TuTh 2:00-3:30 in 234 Dwinelle
Office hours: Th 4-6 pm in 701 Evans
Description: 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. 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. A typical meeting will have the form of an interactive discussion, or real-time brainstorming, or your presentation of your solutions to the problems assigned as homework.
In Putnam Competitions, the participants are expected to be familiar with
some core material from Linear Algebra, Mathematical Analysis, and
Abstract Algebra.
It is a part of the plan to offer a few mini-courses
on some of these topics.
Grading: There is no real basis for letter-grading in this seminar. So, I'd suggest the participants to change their grading option to P/NP (which is easier than solving the namesake problem in the theory of algorithms).
Those who select the P/NP grading option can expect to PASS provided that they honestly apply themselves to solving challenging math problems and regardless of how successful they are in meeting the challenge.
For those who select the letter-grade option, the policy will be that to obtain a grade above C they will need to take the 3-hour written final exam (in the time slot designated by the official Final Exam Schedule based entirely on the problems discussed in class during the semester.
By Tu, Sep.3 Solve:
1. Can a convex 13-gon be divides into parallelograms?
2. A given 17-digit number is added with another one obtained by reversing the order of the digits in the given one. Show that the sum contains at least one even digit.
3. Prove that in any group of (>1) people there are two who have the same number of friends within the group.
4. Among 25 apples of three sorts (green, yellow, red) there are at least 9 of the same sort.
5. Find the smallest number of squares on the 8x8 board one needs to color green so that every tromino -- this is the figure consisting of 3 square cells connected in the shape of the Greek letter gamma (but not necessarily positioned like it) placed on the board (to cover neatly three cells of the board) covers at least one green cell.
6. 45 points are positioned on a line outside segment [A,B]. Prove that the sum of the distances from the points to A is not equal to the sum of their distances to B.
7. Given 51 points in the square 1 meter x 1 meter, prove that one can place a 20 cm x 20 cm square to cover at least 3 of the points.
8. Prove that if n is divisible by neither 2 nor 5, then there is a number m=11....11 (a string of 1s in base 10) which is divisible by n.
By Th, Sep. 5: Be ready to discuss 6 and 8 from the previous set, and solve:
9. Prove that an 8x8 chesss board with (any) one cell cut out can be tiled with trominos. (Sanity check: 8x8-1=63 is divisible by 3.)
10. Show that n^3+(n+1)^3+(n+2)^3 is divisible by 9 for every integer n.
11. Prove that if x+1/x is an integer, then x^n+1/x^n is also an integer(for any natural n).
By Tu, Sep. 10.: Solve
12. The "map of Discoland" problem we started in calss: Given n points on a circle, draw all n-choose-2 chords connecting them, and, assuming that no 3 pass through the same interior point of the disk, find the number #(n) of regions into which the disk is divided by these chords. We've already determined that #(1)=1, #(2)=2, #(3)=4, #(4)=8, #(5)=16, and conjectured that #(n)=2^{n-1} (2 to the power n-1).
(a) To disprove the conjectire, show that #(n+1)-#(n) is a polynomial of n of degree 3, and so #(n) must be a polynomial of degree 4.
(b) Find this polynomial (e.g. by matching its values at n=0,1,2,3,4 with the known ones).
13. In a modern art museum, in a corner of a hall, both walls and the floor are made of mirrors. A girl holding a flower stands in front of this corner. How many flowers (including the actual flower and its reflections) does she see?
14. Suppose that a billiard table has the shape of a narrow "corner" ---
a sector of, say, 1 degree wide. Prove that a billiard ball sent into this
corner will leave the corner after finitely many bounces.
15. In an infinite 1-dimensional billiard, how many collisions happen (over the entire time, i.e. in the future and in the past together) in a system of n identical billiard balls moving with different initial speeds and starting at random initial positions?
16. Consider the number system R:=\Z[\sqrt{-3}] consisting of all complex numbers of the form a+bi\sqrt{3} where a and b are integers. In R we have
2x2=(1+i\sqrt{3})(1-i\sqrt{3}). Show that 2 is irreducible in R (i.e. cannot be factored in any non-trivial way (and yet 2 divides the product on the right but doesn't divide either factor).
17. For a function f on the set of integers, define its finite-difference derivative (Df)(n):=f(n)-f(n-1). Solve the 10th order "differential equation" D^{10}f=d, where d is the "Dirac delta-function": d(0)=1 and d(n)=0 for all non-zero values of n, and the initial condition for f is f(-1)=Df(-1)=...=D^9f(-1)=0
By Th, Sep. 12: Solve problem 17 and
18. John lives in Nowhere York at the intersection of the 0th street and the 0th avenie, and his school is at the corner of the 7th street and the 5th avenue. How many different shortest ways are there from John's home to his school?
(Of course, in Nowhere York all the streets are parallel and all avenues are parallel.)
19. How many ways are there to tile a 1xn strip of n squares with monominoes and dominoes (i.e. 1x1 and 1x2 pieces)?
20. Prove that out of 12 segments of lengths longer than 1 inch and shorter than 12 inches one can select three to form an acute triangle.
21. Establish a Euclidean algorithm for Gaussian integers
\Z[i]={a+bi | a,b\in \Z}. Why doesn't the same method work for \Z[\sqrt{-3}] from problem 16?
By Tu, Sep. 17: Solve problems 19, 20 from the previous set, and also:
22. Provide two proofs -- one using generating functions, one combinatorial -- of the conjecture we established in class: the sum of the squares of the binomial coefficients n-choose-k from the n-th row of Pascal's triangle is equal to 2n-choose-n.
23. The slant sums in Pascal's triangle are defined as
...+"n-1-choose-k-2"+"n-choose-k"+"n+1-choose-k+2"+... (For instance: 1+3+1, 3+4+1, 1+6+5+1)
Identify the sequence of slant sums.
24. Compute the "infinite" (official name: continued) fraction
1+1/(1+1/(1+1/(1+... (i.e. the limit of a_{n+1}=1+1/a_n with a_0=1).
25. Find the greatest common divisor of 11....11 (100 ones) and 1111111
(7 ones).
26. Given angles 2\pi/5 and 2\pi/7, construct the angle 2\pi/35 (where 2\pi stands for the radian measure of the full angle: 360 degrees), using only straightege and compass (actually compass would suffice).
27. 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.
By Th, Sep. 19: Solve problem 20 from the previous set, and:
28. Prove that for each positive integer n, the number
10^(10^(10^n))+10^(10^n)+10^n-1 is not prime.
29. A log is divided by 6 blue marks into 7 equal parts, by 12 red marks into 13 equal parts, and then cut into 20 equal pieces. Show that with the exception of two end pieces, each of the remaining 18 contains a red mark or a blue mark.
By Tu, Sep. 24: Solve (in 30-32, the problem is to determine which of the players has a winning strategy):
30. Two players in turn place Knights on the chess board so that no two attack each other. The player who cannot make a move loses.
31. Two players start with 20 stones; in one move a player can remove 1 or 2 stones; the player removing the last stone wins.
32. The two-player game begins with the number 2. In one move a player can add to the current number any positive integer smaller than it. The player who reaches 1000 wins.
33. Expand the square root of 2 into its continued fraction a_0+(1/a_1+(1/a_2+(...
34. Prove that for any irrational x and any positive integer N there exists a positive integer q not exceeding N such that the distance from qx to the closest integer is less than 1/N. (Hint: Pigeonhole principle.)
35. Use induction on a to prove Fermat's Little Theorem: If a, p are integers and p is prime, then a^p-a is divisible by p.
36. Prove that 300^{3000}-1 (one less than 300 to the power 3000) is
divisible by 1001.
37. For prime p>2, write 1+1/2+...+1/(p-2)+1/(p-1) as a reduced fraction m/n and prove that m is divisible by p.
By Th, Sep. 26: Solve 37 from the previous set, and also:
38. For prime p, prove that the multiplicative group \Z^*_p is cyclic, that is, all p-1 elements are powers of a single one of them, or equivalently: there exists a congruence class a mod p such that the powers a^1, a^2, ..., a^{p-1} are all dstinct in \Z^*_p. Show that this is not true in \Z^*_8 and in \Z^*_{10}.
39. Given a prime p and a polynomial h with integer coefficients, such that h(1), h(2), ..., h(p^2) are all distinct modulo p^2, prove that h(1), h(2), ... , h(p^3) are all distinct modulo p^3.
40. For a prime p, prove the following mod p congruence relation between binomial coefficients: pn-choose-pm is congruent to n-choose-m modulo p.
41. Find an integer that doubles when its rightmost digit is moved to the leftmost place.
By Tu, Oct. 1: Finish 39, start and finish 38,41, and solve:
42. Compute polynomial (x-1)(x-2)...(x-(p-1)) mod p (p - prime).
43. As everyone knows, 5x5=25, 6x6=36, 7x7=... well, it is not 47.
Show that for every positive k there exist exactly four k-digit base 10 endings ...a_1a_2...a_k such that whenever an integer A ends with this ending, A^2 also ends with this ending. (Hint: Two of these four are ...000 and ...001.)
44. Let d_n denote the determinant of the nxn-matrix whose first row is \cos 1, \cos 2, ... , \cos n, the second row is \cos(n+1), \cos(n+2), ..., \cos (2n), and so on up to \cos n^2. Find the limit of the sequence d_n.
If you don't feel comfortable with determinants (and even if you do), read the handout on this subject.
45. Let p be an odd prime congruent to 2 mod 3 (e.g. 5 or 11, but not 3 or 7). Define permutation f of congrience classes mod p by f(x)=x^3. Prove that f is an even permutation if and only if p is congruent to 3 mod 4.
By Th, Oct. 3: Solve:
46. Prove that every positive integer n equals the sum of \phi(d) over all divisors d of n (where \phi(m) denotes Euler's totient function = |(\Z/m\Z)^x|, the number of remainders mod m coprime to m). Remark: This can serve as a lemma to problem 38.)
Also: take a second try on 38, 43, 44, 45, and a first try on
47. 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.
By Tu, Oct. 8: Finish off 45; try 38 using 46 as a lemma (and also that in arithmetic mod a prime p, x^d-1 cannot have more than d roots); don't forget about 43, 44, and 47. Those who want more problems, here you are:
48. Prove that the 3x3-determinant, with x,y,z in the 1st row, x^p,y^p,z^p in the 2nd,
and x^{p^2},y^{p^2},z^{p^2} in the 3rd, where x,y,z are indeterminates, and p is
prime, factors mod p into a product of linear functions of the form ax+by+cz,
(where a,b,c are some integers mod p).
49. A linear transformation U in 3-space is called orthogonal if it preserves the standard dot-product: (Ux,Uy)=(x,y) for all 3-vectors x,y.
Prove that every orthogonal transformation in 3-space is either a rotation through some angle about an axis passing through the origin, or the composition of such a rotation with the reflection in the plane passing through the origin and perpendicular to the axis of rotation.
50. What is the smallest perimeter that a strictly convex 32-gon
with integer vertices can have?
By Th, Oct.10: I think we have enough unsolved problems to discuss (43,44,47,48); also, do read the handout on determinants and try to do exercises there, especially at the end. But just in case you've done all that, here is one more problem:
51. Let A be the nxn matrix whose entry in the i-th row and j-th column is 1/min(i, j) for i, j from 1 through n. Compute det(A).
By Tu, Oct.15: I think we've solved all problems except 51. Still consider:
52. (continuation of 43): Prove that x:=lim_{k\to \infty} 5^{2^k} saitisfies x^2=x (and ends with 5). Find an analogous limit description of the infinite-digit number y ending with 6 and satisfying y^2=y.
53. Given 5 points on a sphere, show that some 4 of them lie on a closed
hemisphere.
54. A code lock is organized as a 4 x 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.
55. Find the least possible area of a convex set in the plane
that intersects both branches of the hyperbola xy = 1
and both branches of the hyperbola xy = -1.
56. Let f be a real-valued function on the plane such that for every square ABCD in the plane, f(A)+ f(B)+f(C)+f(D) = 0. Does it follow that f(P) = 0 for all points P in the plane?
57. A game involves jumping to the right on the real number
line. If a and b are real numbers and b > a, the cost of
jumping from a to b is b^3-ab^2. For what real numbers
c can one travel from 0 to 1 in a finite number of jumps
with total cost exactly c?
58. Let A=(a_{ij}) be a real n x n-matrix, and let A^[k]=(a_{ij}^k) be the matrix whose entries are k-th powers of the entries of A. Suppose A^[k]=A^k (the usual matrix power) for k=1,2,...,n+1. Prove that A^[k]=A^k for all k>0.
59. How many different pairs (P,Q) of real polynomials with deg P > deg Q
are there such that P^2(x)+Q^2(x)=X^{2n}+1 ?
60. Suppose that a function h : \R^2 -> \R has continuous
partial derivatives and satisfies the equation h=a h_x + b h_y
where h_x, h_y are its partial derivatives and a, b some real constants.
Prove that if h is bounded in the absolute value (i.e. for some M, we have
|h(x,y)| < M for all (x,y)), then h is identically zero.
61. Let A be an invertible nxn-matrix such that in
each row of A one entry is equal to +1 or -1 while all others are 0. Prove
that there exists a positive integer k such that A^k = A^T (``A-transposed'').
62. Let f and g be (real-valued) continuous functions on an
open interval containing 0, and g(0)>0. If fg and f/g are
differentiable at 0, must f be differentiable at 0?
By Tu, Oct. 22: We still have 58 started (using Caley-Hamilton eqn) but unfinished, and 59, 60, 61, 62 not even started. Also, don't forget about 51': find a limit description for the infinite number x ending with 6 and satisfying x^2=x. Yet, if you want new problems, how about these:
63. On each face of an isocahedron (if you do not know what an icosahedron looks like, google it up!) a non-negative integer is written such that their total sum is 39. Show that there exist 2 faces which share a vertex and have the same number written on them.
64. Let f : \R^2 -> \R be a function such that f(x, y)+ f(y,z)+
f(z, x) = 0 for all real numbers x, y, and z. Prove that
there exists a function g : \R -> \R such that f(x, y) =g(x)-g(y)
for all real numbers x and y.
65. For any bounded functions g_1, g_2 from \R to (0, \infty) there exist two functions h_1, h_2 from \R to \R such that sup_s g_1(s)^x g_2(s) = max_t (xh_1(t)+h_2(t))
[the supremum over all real s of g_1(s) to the power x times g_2(s) is equal to the maximum over all real t of x times h_1(t) plus h_2(t)]
66. A sequence of positive integers is defined by a_1=1, and
a_{n+1}=(a_n)^2+1 for each n=1,2,3,... Find the greatest common divisor of
a_{100} and a_{2024}.
67. Suppose that the real numbers a_0, ..., a_n and 0 < x < 1 satisfy a_0/(1-x)+a_1/(1-x^2)+...+a_n/(1-x^{n+1})=0. Prove that there exists a real number y with 0 < y < 1 such that a_0+a_1y+...+a_ny^n=0.
By Tu, Oct. 29: Finish problem 65 and solve
68. Alisa comes from school disappointed. On a math test, she got perfect scores in all problems except one, where she is certain her answer was correct too. What was her answer, if the porblem is this: Find the number of faces of the polyhedron obtained by gluing regular tetrahedron and octahedron to each other along one of their faces (which are congruent equilateral triangles)
Then I will bring some past Putnam texts, and we will try to brainstorm some problems together.
By Th, Oct. 31: We will continue 'brainstorming' past Putnam problems, but we have two outstanding issues to resolve:
69. Prove that the length of the average value of a vector field V over a region does not exceed the average value of the length |V| of the vector field over the region,
and the equality occurs only when V is positive proportional to a constant vector field.
70. Prove that the integral over a closed surface in space of the exterior unit normal vector to the surface is equal to zero. [This is a 'smooth' version of the following solid geometry problem: For a closed polyhedron in space, let F_i be the "pressure" vectors: exterior normal vectors to the faces of the lengths equal to the areas of the faces. Show that the vectors add up to zero.]
Hint: A vector is 0 if and only if its dot-product with any (unit) vector equals 0.
By Tu, Nov. 5:
71. Solve B1 from 2011: Is there a sequence a_i of real numbers such that a_1^m+a_2^m+...=m for all m=1,2,3,...
72. Finish A4 from 2011, which we have reduced to the following: For which n the symmetric bilinear form on (\Z_2)^n defined by Q(x,y):=\sum x_iy_j (the sum is over all pairs of distinct i,j = 1,...,n) can be obtained from (x,y):=x_1y_1+...+x_ny_n by a linear map A from (\Z_2)^n to (\Z_2)^n i.e. Q(x,y)=(Ax,Ay).
Hint: consider first the case of invertible A (and also find out for which n the coefficient matrix of Q is invertible).
73. Solve one of the fundamental problems of linear algebra: Classify quadratic forms \sum q_{ij} x_ix_j with complex (resp. real) coefficients q_{ij}=q_{ji} up to linear invertible complex (resp. real) changes of coordinates x_i = \sum_j c_{ij} y_j (that is, find out which quadratic forms can be transformed into each other and which cannot).
By Th, Nov. 7: We will probbaly discuss some of B2 from 2012, and A5 and B2 from 2013. Meanwhile
74. Finish A2 from Putnam 2011.
75. Solve B1 from Putnam 2013.
By Tu, Nov. 12:
76. Finish A5 from 2013; the problem was reduced (sort of) to finding a formula for the length |F| of a vector F in \R^3 in terms of the absolute values of its dot-products with all unit vectors u in a way that would be independent of the direction of F.
77. Try B2 from 2012 (we will probably 'brainstorm' it together).
By Th, Nov. 14:
78. Finish B3 from 2015: Show that an m x n-matrix (a_ib_j) with positive rational a_i, b_j cannot have m+n entries to be distinct primes.
79. Try A4 from 2015 (it is not hard).
By Tu, Nov. 19:
Probably the next set of interesting problems that we will discuss is: A2, B3, A6 from 2017, and B4, B6 from 2018.
You are welcome to take a look at them.
By Tu, Nov. 26: Finish the trigonometry in B4 from 2018, and take a look at A5 and B6 from the same year.
Th, Dec. 5: About the two probability problems we discussed during the last meeting:
2021, B3. There was nothing wrong in what we did. The probability P_n of the event Z=n was found to be d (-\log d)^{n-1})/(n-1)! (where by d I denote the delta). It does not have to be "normalized", and it is less than 1, because the sum over n gives d \exp(-\log d)=d/d=1. A similar summation of n P_n yields E(Z)=1-\log d.
2014, A4. There was nothing wrong in what we did. We found that we need to maximize 1-p_0=p_1+p_2+p_3+... under the costraints p_1+2p_2+3p_3+...=1, 2p_2+6p_3+...=1, 6p_3+...=1, and assuming that 0=p_4=p_5=... we got p_0=1/3. However, to prove this is the optimum, the best I managed to do was to exclude p_1,p_2,p_3 using the constaints to find that 1-p_0=2/3-\sum_{n>3} n(n^2-6n+11)p_n/6 and conclude that the maximum cannot exceed 2/3 since n^2-6n+11 has negative discriminant.