This past weekend, I participated in the William Lowell Putnam Mathematical Competition with a couple of my friends. It was my first time competing in any sort of math competition and I hadn’t prepared much beforehand (I did have a peek at some problems from previous years the day before, but I didn’t manage to solve any). On the day itself, I ended up submitting three out of the twelve questions, though I wouldn’t be surprised if I still got a score of 0/120, given how tough the grading is supposed to be. I thought it’d be a good idea to record my incomplete solutions (and what they were missing) so that when the marks come out in a couple months I’ll be able to refer to what I actually did.
Update (18 February 2020): Results were released today! I got a score of 10/120, with 3 points for question A1 and 7 points for question B1.
What is the Putnam?
The Putnam, first held in 1938, is an annual mathematical competition open to undergraduate students across universities in North America. While the exam is taken individually, universities are ranked according to the scores of their three highest-scoring participants. The exam itself consists of two sessions of three hours each, with a lunch break in between. Questions in the first half are numbered A1 to A6, roughly in increasing order of difficulty. Likewise, questions in the second half are numbered B1 to B6.
The exam is well known for being really difficult, and the median score is 0 or 1 most years. While the problems don’t usually require much concrete background beyond first-year linear algebra and calculus, the proofs require a lot of creativity and very little partial credit is given. The correct answer alone is worth 0 points and getting even 1 or 2 points out of 10 on a question demands that one sketch out a large part of the proof.
The questions I did
I managed to get the correct answer (though definitely not a complete proof) on both problems A1 and B1 and I submitted my work on problem B5 even though I was nowhere close to a full answer. I have included my partial solutions; the full answers can be found here.
A1. Determine all possible values of the expression
\[A^3 + B^3 + C^3 - 3ABC\]where $A$, $B$, and $C$ are nonnegative integers.
What I did. I spent the entirety of the first three-hour session on this problem. For convenience, let
\[f(A,B,C) = A^3 + B^3 + C^3 - 3ABC.\](I wish I’d done this on the actual exam!) On scratch paper, I wrote out tables of the values of the expression for small $A,B,C$ and noticed the following two patterns:
\[f(0,0,1) = 1,\quad f(1,1,2) = 4,\quad f(2,2,3) = 7,\ldots\] \[f(0,1,1) = 2,\quad f(1,2,2) = 5,\quad f(2,3,3) = 8,\ldots\]This pattern would generate all the numbers of the form $3k + 1$ and $3k + 2$ for $k = 0,1,2\ldots$. I knew this couldn’t be it, since I also occasionally got numbers that were divisible by 3, the smallest positive one being $9 = f(0,1,2)$. I then noticed that
\[f(0,1,2) = 9,\quad f(1,2,3) = 18,\quad f(2,3,4) = 27,\ldots\]So I wrote down my claim: The values are of the form
\[3k + 1,\quad 3k + 2,\quad 9k,\]for $k = 0,1,2\ldots$. I only ended up being able to prove that values of this form were expressible, but I didn’t prove that these were the only ones. I did a clumsy proof by induction. First I showed that
\[f(A+1, B+1, C+1) = f(A,B,C) + 3(A^2 + B^2 + C^2 - AB - AC - BC).\]Then for the case where $A = B$ and $C = A+1$, incrementing each of $A, B, C$ by one increases the value of the whole expression by $3$. This shows that $1,4,7,\ldots$ are expressible. In the case where $A = B$ and $C = A-1$ (with base case $A = 1$), incrementing each of $A,B,C$ also increases the value of the whole expression by $3$. This shows that $2,5,8,\ldots$ are expressible. Lastly, when $B = A + 1$ and $C = A+2$, the expression increases by $9$, showing that $9,18,27,\ldots$ are expressible. $0 = f(1,1,1)$ is a special case and my solution ended here.
What I was missing. I was missing a formal proof that $f(A,B,C)$ takes on only nonnegative values, as well as a proof that no numbers of the form $9k + 3$ and $9k+6$ are expressible. I hope that what I did include is enough to get a couple points.
B1. Denote by $\mathbb{Z}^2$ the set of all points $(x,y)$ in the plane with integer coordinates. For each integer $n\geq 0$, let $P_n$ be the subset of $\mathbb{Z}^2$ consisting of the point $(0,0)$ together with all points $(x,y)$ such that $x^2 + y^2 = 2^k$ for some integer $k\leq n$. Determine, as a function of $n$, the number of four-point subsets of $P_n$ whose elements are the vertices of a square.
What I did. I found the pattern pretty quickly by sketching out $P_n$ for a couple values of $n$. (This forum thread includes a nice visualisation of the problem.) I defined the set
\[S_k = \{(x,y) \in \mathbb{Z}^2 : x^2 + y^2 = 2^k\}\]and showed (with some handwaving) that $S_k$ only contains four points for all $k\geq 0$. I then let $f(n)$ denote the number of squares in $P_n$ and claimed that $f(n) = 5n + 1$. When $n = 0$, the only square is formed by the points $(1,0), (0,1), (-1, 0), (0, -1)$. Since
\[P_0 = \{(0,0)\} \cup S_0 \quad\text{and}\quad P_{k+1} = P_k \cup S_{k+1},\]on the induction step we need only consider squares that use a new point (another square would already have been counted). I showed — again, with some handwaving — that exactly 5 squares are added each time: diagonal ones when $k$ is even and regular ones when $k$ is odd.
What I was missing. I was missing a lot of rigour for this question, even though I believe my results were all correct as written. I would not be surprised if I got 0 for this question, though of course I’m hoping I got a point or two!
B5. Let $F_m$ be the $m$th Fibonacci number, defined by $F_1 = F_2 = 1$ and $F_m = F_{m-1} + F_{m-2}$ for all $m\geq 3$. Let $p(x)$ be the polynomial of degree $1008$ such that $p(2n+1) = F_{2n+1}$ for all $n = 0,1,2,\ldots,1008$. Find integers $j$ and $k$ such that $p(2019) = F_j - F_k$.
What I did. I defined the polynomial $p_k(x)$ to be the polynomial of degree $k$ such that $p(2n+1) = F_{2n+1}$ for all $n= 0,1,2,\ldots,k$. Then $p(x) = p_{1008}(x)$. I found that
\[p_0(x) = 1,\quad p_1(x) = \frac{1}{2}x + \frac{1}{2},\quad p_2(x) = \frac{1}{4}x^2 - \frac{1}{2}x + \frac{5}{4}.\]I thought that since $p(2019) = p_{1008}(2\cdot 1008 + 3)$, I’d be able to spot a pattern by finding the values of $p_k(2k+3)$. I found that
\[p_0(3) = 1,\quad p_1(5) = 3,\quad p_2(7) = 9,\]but then I was stuck because I couldn’t find Fibonacci numbers whose difference is 9. [This was a crucial mistake, because $\frac{49}{4} - \frac{7}{2} + \frac{5}{4}$ is actually 10.]
What I was missing. This was actually a good first step towards a correct solution, but because of my computational mistake I didn’t see the pattern, namely that
\[p_k(2k+3) = F_{2k+3} - F_{k+2}.\]In any case, I’m not sure I would have been able to construct the proof.
Remarks
I had a really great time doing the Putnam and I definitely plan to take it again next year. Because one is no longer eligible to take the exam after obtaining a bachelor’s degree, it’ll probably be my last chance to take the test and I’ll spend more time preparing for it than I did this year.