Fall-23. Math 191 (class # 19325): Putnam Workshop
Having registered for the Putnam Competition, come by 7:30 am on Saturday,
December 2, 2023 to Evans 10 (west ground-level entrances to Evans should be open). Bring only pencils and erasers (no scratch paper of your own is allowed) and your student id (just in case). To remind you: the morning session is 8-11 am, the afternoon session is 1-4 pm.
Instructor: Alexander Givental
Meetings: TuTh 9:30-11:00 in 234 Dwinelle
Office hours: TuTh 2-4 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: which is Tu, Dec. 12, 3-6 pm in 234 Dwinelle) based entirely on the problems discussed in class during the semester.
Solve by Tu, Aug. 29:
1. Prove that in any group of 5 people there are two who have the same number of friends within the group.
2. Among 25 apples of three sorts (green, yellow, red) there are at least 9 of the same sort.
3. 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.
4. 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.
5. 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.
6. 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.
Solve by Th, Aug. 31:
1. Prove that an 8x8 chess board with one (arbitrary) cell removed can be tiled by trominoes.
2. 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). So, it only remains to prove the conjecture.]
Solve by Tu, Sep. 5:
0. In one of our problems in class, a girl with a flower in her hand was facing a room corner where both walls and the floor were mirror surfaces. The question was: how many flowers (including the one in her hand) will the girl see? As I've mentined, a hint can be found in this poem.
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
4. In Nowhere York, strictly parallel avenues are intersected perpendicularly by strictly parallel streets (so that all blocks are congruent ractangles). Peter is standing at the corner of the 1st avenue and 1st street and needs to choose a shortest rout to reach the intersection of the 7th avenue and the 4th street (where ice cream is sold - but this doesn't matter). Your goal is to find the number of such shortest routs.
Solve by Th, Sep. 7:
1. Find the sum of the squares of the binomial coefficients "n-choose-k"
over k ranging from 0 to n. (The conjecture we arrived in class was "2n-choose-n".) Try to do this both ways: (a) combinatorially, and (b) based on the definition of the numbers as coefficients in (x+1)^n.
2. The slant sums in the Pascal 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.
3. Find the number of tilings of a strip of n square cells on the grid paper with domino and monomino pieces (E.g. for n=4 there are 5 such tilings:
1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2.)
Here you can find my notes for seminars 1 through 4.
Solve by Tu, Sep. 12:
Several games on the chess board. Two players make moves in turn. The player who can't make the move loses. Each problem is to determine which player has a winning strategy.
0. Place rooks so that no two attack each other. (We've solved this, it turned out to be a pseudo-game - with the outcome independed of the players' moves.)
1. Place knights so that no two attack each other.
2. Place bishops so that no two attack each other.
3. Playing with one rook, the players make legitimate moves but only in the north or east directions. The starting position is A1 (the southwest corner of the board).
4. Similar to Problem 3, but playing with one King, which is allowed to move (one step) only in the north, east, or northeast directions, and starting at A1.
Some non-game problems:
5. Prove that from 12 segments of lengths ranging between 1 and 12 inches one can find three which are sides of an acute triangle.
6. 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).
Solve by Th, Sep. 14: Problems 5, 6 from the previous set, and any of the following:
A. Two players start with 20 stones; in one move a player can remove 1 or 2 stones; the player removing the last stone wins.
B. Prove that if x+1/x is an integer, then x^n+1/x^n is an integer for all integer n.
C. Prove that the set of all subsets of a given set cannot be put in one-to-one correspondence with all elements of that set.
D. 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.
(This was an axiomatic definition.) 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.
E. 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.
And don't forget to explain to me what mathematical proof is.
Solve by Tu, Sep. 19: problems C and D from the previous set, and
1. Show that the greatest common divisor d of m and n is representable as a linear combination d=km+ln with some integer coefficients k and l.
2. Consider the number system R consisting of all complex numbers of the form a+b\sqrt{3}, where a and b are arbitrary integers (and \sqrt{3} denotes the squre root of 3). Show that in R, the Fundamental Theorem of Arithmetic (about existence and uniquess of prime factorization) does not hold. ( Hint:, try to factor 4.
3. Find the greatest common divisor of 11....11 (100 ones) and 1111111
(7 ones).
4. 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), the using only straightege and compass (actually compass would suffice).
5. Two tribes, Mumbo and Jumbo, argue whose language is richer. Mumbo linguists claim that their Jumbo-Mumbo dictionary translates each Jumbo word by a distinct Mumbo word, but some Mumbo words remain unused. Jumbo linguists make the symmetric claim about their Mumbo-Jumbo dictionary. Prove that there is a third dictionary which establishes a one-to-one correspondence between the two vocabularies.
Solve by Th, Sep. 21: 3, 4,5 from the previous set, and any of the following (though we probably won't have time to discuss all of them on Th):
A. Prove that for each positive integer n, the number
10^(10^(10^n))+10^(10^n)+10^n-1 is not prime.
B. 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).
C. 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.
D. 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.
Solve by Tu, Sep. 26: A,B,C,D from the previous set, and
1. Given a prime p, show that binomial coefficients p-choose-k are divisible by p when k=1,2,,..., p-1.
2. Use induction on a in order to prove Fermat`s Little Theorem:
For any prime p and any integer a, p|(a^p-a)
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. Prove that 300^{3000}-1 (one less than 300 to the power 3000) is
divisible by 1001.
5. Using only straighedge and compass, construct a triangle given (the lengths of) its median, altitude, and angle bisector issued from the same vertex.
Solve by Th, Sep. 28: all the remaining problems from the previous list: D,1,2,3,4,5.
Solve by Tu, Oct. 3: Problem D from the previous week, and:
1. The multiplicativity of Euler's totient function: |\Z^*_{mn}|=|\Z^*_m||\Z^*_n| provided that m and n are coprime.
2. 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}.
3. 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.
4. 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.
5. Construct a triangle given its three altitudes.
Solve by Th, Oct. 5: 3, 2, 4 from the previous list (if you don't know this yet, you might want to learn what the parity of a permutation is), and the log problem (D from the previous week), and
A. 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.
B. Compute polynomial (x-1)(x-2)...(x-(p-1)) mod p (p - prime).
C. Find an integer which doubles when its rightmost digit is moved to the leftmost place.
Solve by Tu, Oct. 12: A,B and 2,4 from the previous week; the log problem from long ago; problems
I. 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.)
II. 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?
III. 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.
Also, (a) read the handout on determinants and (b) register for the 84-th Putnam Mathematical Completition (using the link at the top of this page).
Solve by Th, Oct. 12: anything left unfinihsed from Tu, of course: I, III, the log problem, and finish 4.
Solve by Tu, Oct. 17: Exercises 234-241 from the handout on determinants,
and
0. Convince yourself that the "infinite integer" x=\lim 5^{2^n} satisfies x^2=x. In what sense does the sequence converge? Find an analogous limit description
for the other such number, whose rightmost digit is 6.
1. 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.
2.
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).
Solve by Th, Oct. 19: The remaining exercises from the handout on determinants, as well as problems 1 and 2 from the Tu set.
Solve by Tu, Oct 24: Problem 1 about n cards from the previous set, and
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. What is the smallest perimeter that a strictly convex 32-gon
with integer vertices can have?
5. 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.
6. 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.
Solve by Th, Oct. 26: Finish off 5, solve 6 (at least (a) and (b) possibly with the icosahedron replaced by the cube - for simplicity), and
A. 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?
B. 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?
Solve by Tu, Oct. 31: parts (a) and (c) of Problem 6 of the previous week, and
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 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.
3. 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)]
4. A sequence of positive integers is defined by a_0=1, and
a_{n+1}=a_n^2+1 for each n\geq 0. Find the greatest common divisor of
a_{105} and a_{2023}.
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.
Solve by Th, Nov 2: parts (a) and (c) of Problem 6 of the previous week, and
A. John says that over the weekend he planted 12 trees in 6 rows of 4 trees per row. Does he lie?
B. 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)?
C. 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.
D. 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 ?
E. 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.
On Tu, Nov. 7: we need to finish C, and discuss the "convex bodies" problem, especially the case of the sphere. To have something else to do, solve
1. 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'').
2. 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?
Then I will bring some past Putnam text, and we will try to brainstorm some problems together.
By Tu, Nov. 14: Solve A1, B1, and B3 from 2017 (see the Putnam archive )
By Tu, Nov. 21: Solve A2 from 2018, and finish B6 from 2018. To remind you: we decided that the cardinality of S is the coefficient at x^{3860} in the polynomial (x+x^2+x^3+x^4+x^5+x^6+x^10)^{2018}.
By Tu, Nov. 28: Finish A6 from 2009 (this is what the "2-dim mean value problem" was), and also solve B2 from 2013.
By Th, Nov. 30: which is our last seminar,
A. finish problem A5 from 2013 (about area-definite collections of numbers); to remind you: we seem to have decided that the key would be to connect the areas of a plane figure with the average area of its orthogonal projections to all planes in space.
B. prove what is left in A6 from 2009: the vector average of unit vectors has length not exceeding 1, and equal to 1 only when all the vectors are equal.
C. solve B3 from 2019.
-