Fall-20. Math 191 (class # 32456): Putnam Workshop

Registration for the 83-rd Putnam Mathematical Competition which will occur on Saturday, December 3, 2022, is now open to regularly enrolled UC Berkeley undrgraduates at the registration portal

For the Putnam Competition itself, come by 7:30 am on Saturday, December 3, 2022 to the Hearst Field Annex A1 . Bring only pencils and erasers, and your student id. To remind you: the morning session is 8-11 am, the afternoon session is 1-4 pm.

Instructor: Alexander Givental
Meetings: TuTh 2:00-3:30 in 736 Evans
Office hours: Wed 2-4 pm 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 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 a form of interactive discussions, or real-time brainstorming, or your presentation of you 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. However, I am teaching Math H110 and Math H113 this semester, and if you feel ready, you are welcome to enroll there too.

There is no real basis for letter-grading in this seminar. So, I'd urge the participants to change their grading option to P/NP (which is easier than solving the namesake problem in the theory of algorithms)

Solve by Tu, Aug. 30:
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 ).
I was asked to post my notes from today's (08.25) discussion. Here they are.

By Th, Sep. 1: From the last page in the notes notes that I was using today:(a) continue working on the problem of tiling 64-1-chessboard by trominos, and (b) for n=1,2,3,4,5 find out into how many states is Discoland divided by n chords no three of which intersect at the same point inside the disk.

By Tu, Sep. 6:
0. In the Discoland problem, try to find a direct (non-inductive) argiment confirming the answer 1+ (n-choose-2)+(n-choose-4) found in class.
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 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. 8:
1. Find the sums of binomial coefficients along the "slant rows" of Pascal's triangle (as was explained at the end of the seminar; e.g. the 5th slant row will contain the left 1 from the row 1 2 1, the right 3 from the row 1 3 3 1, and the right 1 from the row 1 4 6 4 1), with the sum 1+3+1=5).
2. Find the number of ways to tile a strip of n square cells (i.e. the shape 1 x n) with monomino (1 x 1) and domino (1 x 2) pieces.

By Tu, Sep. 13:
1. 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. 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.
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.

By Th, Sep. 15:
1. Show that in R={ a+b\sqrt{-3} | a,b\in Z}, 2 x 2 = (1+\sqrt{-3})(1-\sqrt{-3}) are two different factorizations of 4 into irreducibles (which are therefore not prime).
2. Prove (relying on consequences of the Euclidean algorithm) that in Z (integers) every irredicible p>1 is prime (i.e. p|ab implies p|a or p|b).
3. Prove that if x+1/x is integer then x^k+1/x^k is integer for every k=2,3,4,....

By Tu, Sep. 20:
0. Constuct a regular pentagon by straightedge and compass.
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 for each positive integer n, the number 10^(10^(10^n))+10^(10^n)+10^n-1 is not prime.
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. 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.
5. Compute polynomial (x-1)(x-2)...(x-(p-1)) mod p (p - prime).
6. 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 Th, Sep. 22: Solve probplems 5 and 6 remaining from the previous set, and also:
A. 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.
B. Show that 300^{3000}-1 is divisible by 1001 (if you don't know this yet from another class :-)

By Tu, Sep. 27:
0. To finish off the log problem: Explain why the fraction (k+l)/(m+n) lies between k/m and l/n.
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.
4. 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 ?
5. "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)?

By Tu, Oct. 4: To remind you: on Tu/Th of the previous week we finished problems 0,1,3 of the previous list and started 2 by noting that in effect it is a calculus problem. So, finish problem 2, solve 4 and 5 from that list, and also solve
6. 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. 6: Solve
A. In problem 5 from the previous list, we have figured out in class that and infinite decimal integer x ending with 5 and such that x^2=x 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?
B. Problem 6 from the previous list
C. 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?
D. 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+1), ..., \cos (2n), and so on up to \cos n^2. Find the limit of the sequence d_n.

By Tu, Oct. 11: Read handout on determinants (theory and exercises), and be prepared to present solutions to exercises 235,237,239,240,241 from it. Also, solve problem D from the previous list and the following game problem:
Alan and Barbara play a game in which they take turns filling entries of an initially empty 2022 x 2022 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. 13: 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. 18: Solve
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.
3. 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.
4. In the linear space C[0,1] of all real-valued continuous functions on [0,1], the unit cube K is defined as the set of those functions whose maximal absolute value equals 1: K ={ f:[0,1] --> \R | max |f(x)| = 1}. Show that C[0,1] has a linear subspace whose intersection with K is (a) a circle; (b) an icosahedron; (c) a sphere.
5. What is the smallest perimeter that a strictly convex 32-gon with integer vertices can have?
6. 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.

By Th, Oct. 20: Solve problems 1 and 4 from the previous list, and also
A. 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.
B. 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 Tu, Oct. 25: Continue with Problem 4 of the previous list, parts (b) and (c). Also, solve:
1. Given a sequence a_n of real numbers such that a_{n+1}-a_n/2 tends to 0 as n tends to infinity, prove that a_n tends to 0 as well.
2. 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'').
3. A sequence of positive integers is defined by a_1=1, and a_{n+1}=a_n^2+1 for each n\geq 1. Find the greatest common divisor of a_{300} and a_{2022}.
4. 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?
5. 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?

By Tu, Nov. 1: Solve problem 2 from the previous list, and the following five (fairly simple) problems:
1. Let f be a non-constant polynomial with positive integer coefficients. Prove that if n is a positive integer, then f(n) divides f(f(n) + 1) if and only if n = 1.
2. Show that every positive rational number can be written as a quotient of products of factorials of (not necessarily distinct) primes. For example, 10/9=2! 5! / 3! 3! 3!
3. 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.
4. 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 f 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.
5. 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 Th, Nov. 3: Solve problem 5 from the previous list and the following scary-looking but actually simple problems
6. 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)]
7. Let f and g be (real-valued) functions defined on an open interval containing 0, with g nonzero and continuous at 0. If fg and f/g are differentiable at 0, must f be differentiable at 0?

By Tu, Nov. 8: Solve problems A4, B3, B4 from Putnam 2016 and B1 and A6 from Putnam 2017 (found in this archive ). Do not read solutions!

By Th, Nov. 10: Solve A2, A4, A6, B3 from Putnam 2017.

By Tu, Nov. 15: Solve A4 from Putnam 2017 and A4, B4, B6 from Putnam 2018.

By Th, Nov. 17: Solve B3 and B6 of from Putnam 2018, and A5 and B3 from Putnam 2019.

By Tu, Nov. 22: It is time to look at the problems of 2021, the December session. Solve as many as you can/want. At the moment I am ready to discuss A1, A2, A3, A5, and B1. So, perhaps, start with these.
P.S. And B6.

For Tu, Nov. 29: In our zoom meeting on Tu, Nov. 22 we discussed A1, A2, A3 and A5 from Putnam 2021, so B3 and B6 are left from the previous list, and I am also ready to discuss B4.

By Th, Dec. 1: Add B5 (about very odd matrices) if you have time to think of it.