Fall-20. Math 191 (ccn 19552): Putnam Workshop

Register for the (unofficial, due to covid-19 limitations) 81-st Putnam Mathematical Competition that will occur on February 20, 2021

Instructor: Alexander Givental
Meetings: TuTh 12:30-2 on Zoom
If you are enrolled, you should have received an email message from me with the link to the Zoom meetings. If you are enrolled but haven't received the link, please contact me by email.

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.

Normally, such seminars would have a form of interactive discussions or real-time brainstorming. This might be harder to do in the Zoom version. So, we'll have to experiment and decide in the flight what's the best mode of in-class communication. I'd suggest that you, the participant, think in advance of a way of sharing your screen on Zoom: either from a tablet, or by using the iPhone camera directed to a sheet of paper where you can write.

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 my plan to offer several crash courses on some of these topics. Those who want to take this course for a letter-grade should expect rigorous testing on this material.

You won't submit any written homework for grading, but presenting in class your original solutions to some homework problems can also serve as a basis for letter grading.

If you'd rather not to be concerned with the grades, but want to simply enjoy problem solving, you should probably change the grading option to P/NP.

Solve by Tu, Sep. 1:
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 ).
By Th, Sep. 3: Solve the problem we started discussing in class:
n points are positioned on a circle so that no three chords connecting them are concurrent. Find the number of regions into which these n-choose-2 chords divide the disk.
By Tu, Sep. 8:
1. Suppose that a billiard 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.
2. 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 speeds in an infinite 1-dimensional billiard?
3. For a function f on the set of integers, define its finite-difference derivative (Df)(n):=f(n)-f(n-1). Solve the "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.
By Th, Sep. 10:
1. Prove (in two ways: combinatorially, and using generating functions) that the sum over k of the squares of the binomial coefficients n-choose-k is equal to 2n-choose-n.
2. Prove that the sums of the binomial coefficients over the "slant rows" of Pascal's triangle (as discussed at the end of the seminar) yield the Fibonacci sequence.
3. Derive the general formula for the Fibonacci sequence (try using the method of generating functions).
By Tu, Sep. 15:
1. (left from class): Find out which player has a winning strategy in the game on the 8x8-chessboard, where the king starts at the field A1, is moved by the players in turn one step to the East, North, or North-East, and the player who reaches the field H8 wins.
2. Two players take turns taking from a pile of (initially 20) stones one or two stones at a time, and the player which cannot make the move loses. Which of the players has a winning strategy?
3. Prove that if x+1/x is an integer, then x^n+1/x^n are integers for all integers n.
4. 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.
5. Let 1< d_1, d_2, ... , d_{12} < 12 be twelve real numbers between 1 and 12. Prove that there exist three of them which are side lengths of an acute triangle.

By Th, Sep. 17:
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. Prove that modulo a prime number p, (x+y)^p=x^p+y^p. (Here x and y are not integers, but variables.)
3. Find the greatest common divisor of 111...111 (1001 ones) and 11...11 (700 ones).

By Tu, Sep. 22:
1*. Prove that for each positive integer n, the number 10^(10^(10^n))+10^(10^n)+10^n-1 is not prime.
2. Use induction on x in order to prove Fermat`s Little Theorem: For any prime p and any integer x, p|(x^p-x).
3. Show that every positive rational number can be written as a quotient of products of factorials of (not necessarily distinct) primes.
4. Compute (x-1)(x-2)...(x-(p-1)) mod p (p is prime).
5. For a prime p and m greater than or equal to n, show that pm-choose-pn is congruent to m-choose-n modulo p.

By Th, Sep. 24:
1. Prove that 300^{3000}-1 (one less than 300 to the power 3000) is divisible by 1001.
2. Prove that the numerator m of the fraction m/n:=1+1/2+1/3+...+1/(p-1), where p is an odd prime, is divisible p.
3. Prove that every positive integer n equals the sum of \phi(d) over all divisors d of n, where \phi(m) is the Euler totient function (equal to the number of remainders modulo m coprime to m).
4. How many differnt pairs (P,Q) of real polynomials with deg P > deg Q are there such that P^2(x)+Q^2(x)=X^{2n}+1 ?

By Tu, Sep. 29:
0. Take another chance to solve Problem 2 from the previous homework, plus
1. Prove that for every prime p there exists a congruence class a mod p such that the smallest positive k, such that a^k is 1 mod p, equals p-1 (as the Fermat Little Theorem suggests).
2. 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.
3. 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. 1: Solve 2 and 3 from the previous HW.

By Tu, Oct. 6: Still, solve problem 3 from the Sep. 29 HW. Also:
1. "5x5=25, 6x6=36, 7x7=47?" Show that there exist exactly 4 base-10 "integers" x infinite to the left satisfying the quadratic equation x^2=x. (That is, for any k, if an ordinary integer has k rigthmost digits the same as in x, then its square has the same k rightmost digits.) Can you give an a priori explaination of why the number of solutions is 4 (which is greater than the degree of the polynomial)?
2. Prove that the multiplicative group \Z^*_{p^2} (=invertible congruence classes of integers mod p^2) is cyclic for every prime p.
3. 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 Th, Oct. 8:
Still the same problems: 1,2,3 from the previous HW. In 3, we have figured out in class that x ending with 5 can be written as the "limit" of the sequence 5^{2^k} of consecutive squares. Can you find a similar formula (algorithm) for the solution ending with 6?
4. On a 3x3 chess board, two white knights are positioned at a1 and c3, and two black ones at a3 and c1. Is it possible to move the knights (using legitimate knight moves) so that at the end the while knights are at a1 and a3, and the black knights are at c1 and c3?

By Tu, Oct. 13: Read handout on determinants (theory and exercises), and be prepared to present solutions to exercises 235,237,239,240,241 from it. Also, solve the following game problem:
Alan and Barbara play a game in which they take turns filling entries of an initially empty 2020 x 2020 array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all the entries are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?

By Th, Oct. 15: We have not discussed yet the exercises on determinants listed in the previous homework; so you still have a chance to present your solutions. If you are done with the exercises, here is one more problem for you:
Let A=(a_{ij}) be a real n x n-matrix, and let A^[k]=(a_{ij}^k) - 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.

By Tu, Oct. 20: ... and two more:
1. 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).
2. Given 5 points on a sphere, show that some 4 of them lie on a closed hemisphere.

By Th, Oct. 22: Take another shot at the problem about A^[k]=A^k, and solve
1. A 4x4 switch board (where each of the 16 swiches can be in either horizontal or vertical position) serves as a code lock: the lock opens when all switches are horisontal. When a switch is turned, all shwitches in the same row and column turn too. Find a way to open the lock starting with any initial positions of the switches.
2. For which positive integers n is there an n x n matrix with integer entries such that every dot product of a row with itself is even, while every dot product of two different rows is odd?

By Tu, Oct. 27: Be ready to present your solutions of problems 1 and 2 from the previous assignment, and also solve:
3. Consider the set S of cosine polynomials of the form f(x)=1+\sum a_n cos nx which are everywhere non-negative, and where a_n =0 if n is divisible by 3. Find the maximum of f(0) over this set S.
4. Let h and k be positive integers. Prove that for every \e > 0 (positive epsilon) there exist positive integers m and n such that \e <|h m^{1/2} -k n^{1/2}| < 2\e

By Th, Oct.29: Problems 3 and 4 were still left untouched, and in connection with Problem 2 (which was solved) we have arrived at the question of classification of square matrices Q up to transformations A^T Q A. Since the answer may depend on the constext, assume A invertible, Q (say) symmetric, and the entries (a) real, (b) complex, (c) integers mod 2.

By Tu, Nov.3: You have got some hint for Problem 3, and you still have the three questions (a),(b),(c) to think of -- so please make your best effort to solve the problems.

By Th, Nov.5: We have made progress in linear algebra by classifying linear maps between two vector spaces of dimensions m and n up to linear changes of coordinates: it turned out that all such maps of the same rank are equivalent. Still, we have the questions (a,b,c) open (though there was a suggestion to think of Q as a linear map from a space to its dual). Here are some other problems to be solved by Thursday:
0. If two subspaces in R^n of dimensions p and q with p+q>n span the whole of R^n, then their intersection has dimension p+q-n.
1. 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.
2. Let A be an invertible nxn matrix such that in each row of A there is one entry equal to +1 or -1, and all aother are zeroes. Prove that there exists a positive k such that A^k = A^T (A-transposed).

By Tu, Nov.10: We have made more progress in linear algebra by interpreeting the problem of classifying symmetric n x n matrices Q up to tranformations A^T Q A as the problem of classification of homogeneous degree 2 polynomials in n variables up to linear changes of coordinates. For you, it only remains to solve the latter problem. Here are some other problems which you can solve:
1. Find the least possible area of a convex set in the plane which intersects both branches of the hyperbola xy=1 and both branches of the hyperbola xy=-1.
2. Find the greatest common divisor of a_{25} and a_{2020} where the sequence a_n is definied by a_1=1 and a_{n+1}=(a_n)^3+1.
3. Let f be a real-valued function on the plane such that for any square ABCD, f(A)+f(B)+f(C)+f(D)=0. Does it imply that f(P)=0 for all points P in the plane?
4. A game involves jumping to the right on the real number line. The cost of jumping from a to b (>a) is defined as b^3-ab^2. For what numbers c one can travel from 0 to 1 in a finite number of jumps with total cost exactly c ?
5. Is there a 3x3 matrix A such that A^3=0 but A^2 is non-zero?

By Th, Nov. 12: We will continue with problems 1,2,4, and maybe something else.

By Tu, Nov. 17:
1. What is the smallest perimeter a convex 32-gon with integer vertices can have?
2. Suppose a_{n+1}-a_n/2 tends to 0. Prove that a_n tends to 0.
3. Show that for any positive integer n there exists a 2020x2020 matrix A such that A^n=B where B is the upper triangular matrix with all 1s on the main diagonal, all 2s on the diagonal above it, all 3s on the diagonal above it, etc. (and hence 2020 in the upper right corner).
4. Given a (non-degenerate) polyhedron P, show that there exists a constant c(P)>0 with the property: if a collection of n balls of total volume V contains the entire surface of P, then n>c(P)/V^2.

By Th, Nov. 19: Think through the soulution to problem 3 based on Jordan canonical forms. Apply your best effort to problem 4. Besides, solve:
A. Given a finite set of points in the plane such that the area of the triangle formed by any three of them does not exceed 1, prove that this set can be covered by a triangle of area not exceeding 4.
B. Let A be an m x n matrix with rational entries. Suppose that among the absolute values of the entries of A there are at least m+n distinct prime numbers. Show that the rank of A is at least 2.

On Tu, Nov. 24: We want to discuss the Jensen inequality, solve problem B, and hopefully also solve C and D below:
C. Suppose that f(x)=c_0+c_1 x+c_2 x^2+ ... is a power series with all coefficients c_n=0 or 1. Show that if f(2/3)=3/2, then f(1/2) must be irrational.
D. Let Q be an orthogonal n x n matrix, and P = I - 2u u^T, where u is a unit vector. Prove that if 1 is not an eigenvalue of Q, then 1 is an eigenvalue of PQ.

By Tu, Dec. : Solve problems
1. Prove that a sequence defined by x_{n+1}=2x_n x_{n-1}-x_{n-2}, x_0=1, x_1=x_2=a, is periodic if for some n x_n=0.
2. How many ways are there to paint the 30 edges of an icosadedron in red, green, or blue, so that each of the 20 faces of the icosahedron have two edges of the same color and the third one of a different color. (The 30 edges are considered distinguishable - e.g. numbered by 1,2,...,30).
3. Let S be the set of sequences of length 2018 whose terms are in the set {1,2,3,4,5,6,10} and sum to 3860. Prove that the cardinality of S is at most 2^{3860}(2018/2048)^{2018}.