## Putnam 2016

Today I picked up the October issue of the American Mathematical Monthly. As traditional, the first article has the questions in this year’s William Lowell Putnam Competition. As displacement activity, I did Paper A, allowing myself two of the usual three hours, but, as is my normal habit, full use of computer algebra. For the entertainment of others (and possibly as a warning to myself), here is a record of the thought processes of an averagely procrastinating mathematician.

A1. Let $A$ and $B$ be points on the same branch of the hyperbola $xy=1$. Suppose that $P$ is a point lying between $A$ and $B$ on this hyperbola, such that the area of the triangle $APB$ is as large as possible. Show that the region bounded by the hyperbola and the chord $AP$ has the same area as the region bounded by the hyperbola and chord $PB$.

Thoughts / solution. This looks like a routine optimization problem. Put $A$ at $(a,1/a)$, $B$ at $(b,1/b)$ and $P$ at $(p,1/p)$, with $a > 0$. The first region is formed from the quadrilateral with vertices $(a,0),(p,0),(p,1/p),(a,1/p)$, missing out the area below the hyperbola from $a$ to $p$. So its area is

$\displaystyle \frac{(p-a)(1/a+1/p)}{2} - \log \frac{p}{a}.$

Similarly the second region has area

$\displaystyle \frac{(b-p)(1/p+1/b)}{2} - \log \frac{b}{p}.$

I can see that $p$ is eliminated when we add the logs. This looks hopeful. I add the areas and promptly make an algebraic slip that says the sum is independent of $p$. This can’t be right. Turning to Mathematica I get the correct sum, and by differentiating, see that it is minimized when $p = \sqrt{ab}$. This maximizes the area of the triangle, and sure enough, the expressions above for the areas under the chords turn out to be equal when $p = \sqrt{ab}$.

(In retrospect, this had to be the right $p$, because by the moral linear independence of arbitrary transcendentals, there’s no way the expressions will be equal without the logs agreeing.)

A2. Let $a_0 = 1, a_1 = 2$, and $a_n = 4a_{n-1} - a_{n-2}$ for $n \ge 2$. Find an odd prime factor of $a_{2015}$.

Thoughts / solution. I immediately load the problem into Mathematica and compute the factorizations of $a_1, \ldots, a_{100}$. It looks like $181$ is always a factor of $a_{5m}$ when $m$ is odd. Since $2015 = 5 \times 13 \times 31$, this would do it. After some dithering with $2 \times 2$ matrices versus direct manipulation of the recurrence, I use Mathematica with

b[0] := b0; b[1] := b1; b[n_] := 4b[n-1] - b[n-2]

to find $b_{10} = -40545 b_0 + 151316 b_1$. It follows that

$b_{n+10} = -40545b_{n} + 151316b_{n+1}$

for all $n$. Since $151316 = 181 \times 836$, the claim follows by induction. Thinking that this wouldn’t have been much fun to do without computer algebra, I press on.

A3. Compute

$\displaystyle \log_2 \Bigl( \prod_{a=1}^{2015} \prod_{b=1}^{2015} (1 + \mathrm{e}^{2\pi i ab/2015}) \Bigr)$.

Here $i$ is the imaginary unit (that is, $i^2 = -1$).

Thoughts / solution. My immediate thought is ‘who is going to know the definition of the complex exponential function, but get confused by $i$‘? Next I put the product into Mathematica, replacing $2015$ with a general $N$. After some confusing errors, I realize that $N$ (even used in pattern matching as N_) is a bad choice, because it clashes with the built in numerical evaluation function. This hitch resolved, the small values suggest that the product is $0$ when $N$ (or rather, a more Mathematica-friendly letter) is even, and a power of $2$ when $N$ is odd. A trivial change in the code lets me compute

$\displaystyle Q(a) = \prod_{b=1}^{N} (1 + \mathrm{e}^{2\pi i ab/N}).$

Of course its still a power of $2$, but the exponent is still not obvious. Fairly quickly I realise I’ve encountered the product

$(1+\zeta)(1+\zeta^2) \ldots (1+\zeta^{M}),$

where $\zeta$ is a primitive $M$th root of unity, before: the standard (and I feel slightly tired) trick, is to note that, up to a sign, it’s obtained by evaluating $X^M-1=(X-1)(X-\zeta)\ldots (X-\zeta^{M-1})$ at $X=-1$. So $(1+\zeta)(1+\zeta^2) \ldots (1+\zeta^{M}) = 2$ and, after some stupid slips and general lack of progress, I realise that

$Q(a) = 2^{\gcd(N,a)}$.

This reduces the problem to evaluating $\sum_{a=1}^N \gcd(N,a)$. Turning to a small example, I see how this works for $N = 15$: we have $\phi(15) = 8$ coprime numbers with gcd $1$, then $3,6,9,12$ each contribute $3$, and $5,10$ each contribute $5$. I go off on a tangent trying to get a general formula with the Principle of Inclusion and Exclusion. Nothing seems very nice, and, noting that the sum is over all $a$, not those $a$ satisfying some ‘sievable’ property, it starts to feel like the wrong approach. Going back to the example, I realise that there are exactly $\phi(N/d)$ numbers with gcd $d$. So we need

$P(N) = \prod_{c \mid n} 2^{\phi(c) N/c}.$

It looks like $P$ might be multiplicative. Yes it is. I evaluate $P(p^a)$, then realise I’m wasting time, since I should remember from A2 that $2015 = 5 \times 13 \times 31$ is square-free. Clearly

$P(p) = 2^p \times 2^{p-1} = 2^{2p-1}.$.

So $P(2015) = 2^{9 \times 25 \times 61}.$

A4. For each real number $x$, let

$\displaystyle f(x) = \sum_{n \in S_x} \frac{1}{2^n}$

where $S_x$ is the set of positive integers $n$ for which $\lfloor nx \rfloor$ is even. What is the largest real number $L$ such that $f(x) \ge L$ for all $x \in [0,1)$? (As usual $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$.)

Thoughts / solution. I’m getting a bit tired now, but this looks like an interesting problem. Once again, I load it into Mathematica. This takes a bit more effort, but after a few minutes I’ve got the code and graph shown below.

It looks like the minimum is attained at $2/3$. I evaluate N[f[1000, 2/3 - 0.0001], 20] and get $0.57142857142857142857$. I should recognise this immediately as $4/7$, but instead put it into Google.

I’m now quite keen to solve this problem. I look at some small cases by hand, seeing that if $x \in [0,1/2)$ we get an immediate contribution of $2^{-2}$, so $x \ge 1/2$ is indicated. Then $x \in [1/3,2/3)$ makes sure that we don’t get $2^{-3}$, so it looks like $x \le 2/3$. But then we have $x \in [1/2,3/4)$, so $4 \in S_x$ and we do get $2^{-4}$. Maybe this is unavoidable, … I have my first ‘aha’ moment of the competition, when I realise that this greedy approach is going to solve the problem: since $1/2^n$ is equal to $1/2^{n+1} + 1/2^{n+2} + \cdots$, nothing is more important at the $n$th step than avoiding $n \in S_x$, if we can. I celebrate by taking 10 minutes off to play some blitz chess.

Back at the problem, I see that I have to rule out an interval of the form $[2r/n, (2r+1)/n)$ containing $2/3$, such that the lower bound from the greedy strategy after $n-1$ steps is less than $2r/n$. Then we would `dodge’ left of this interval, and lose control of $x$. I try to make this work for at least 10 minutes, not getting anywhere much. Maybe only prime values of $n$ are relevant? I get Mathematica to show me the relevant intervals with the code below.

This shows that $x \ge 5/8$ is a lower bound from the greedy strategy not coming from prime $n$. But more importantly, I finally see the pattern: starting at $n=3m-1$, we have

$\frac{2}{3} \in [(2m-1)/(3m-1), 2m/(3m-1));$

since $2m-1$ is odd, the greedy strategy tells us that $x \ge (2m-1)/(3m-1)$. For the next $m$ we have

$\frac{2}{3} \in [(2m-1)/3m, (2m+1)/3m,]$

so $x \ge (2m-1)/3m$, but this is already implied. Next

$\frac{2}{3} \in [2m/(3m+1), (2m+1)/(3m+2)),$

and since $2m/(3m+1) \le (2m-1)/(3m-1)$, there is no way to avoid $3m+1 \in S_x$. So taking $x$ arbitrarily close to $2/3$ we can get $f(x)$ arbitrarily close to

$\frac{1}{2^1} + \frac{1}{2^4} + \frac{1}{2^7} + \cdots = \frac{1}{2} \times \frac{1}{1-1/8} = \frac{4}{7}.$

A5. Let $q$ be an odd positive integer, and let $N_q$ denote the number of integers $a$ such that $0 < a < q/4$ and $\mathrm{gcd}(a,q) = 1$. Show that $N_q$ is odd if and only if $q$ is of the form $p^k$ with $k$ a positive integer and $p$ a prime congruent to $5$ or $7$ modulo $8$.

Thoughts. My immediate thought: this is too much, and I’m wasting time doing this anyway. Maybe it is something to do with arithmetic sums (which I know I don’t know well). I decide to skip it.

A6. Let $n$ be a positive integer. Suppose that $A, B$, and $M$ are $n \times n$ matrices with real entries such that $AM = MB$ and such that $A$ and $B$ have the same characteristic polynomial. Prove that $\mathrm{det}(A-MX) = \mathrm{det}(B-XM)$ for every $n \times n$ matrix $X$ with real entries.

Thoughts / sketched solution. Surely as a professional user of linear algebra, this can’t be hard for me? Reluctantly I commit to solving it. Immediately I see that if $M$ is invertible then we’re done, since then $M^{-1}AM = B$ and so

$\mathrm{det}(B-XM) = \mathrm{det}(M^{-1}A-X) \mathrm{det}(M)$

and similarly

$\mathrm{det}(A-MX) = \mathrm{det}(M)\mathrm{det}(M^{-1}A - X).$

Thinking about the other extreme case, when $M$ is $0$, the $AM = MB$ condition tells us nothing, but now all we need is $\mathrm{det}(A) = \mathrm{det}(B)$, which follows from the assumption on the characteristic polynomials.

By Fitting’s Lemma we can write $M$ as the direct sum of a nilpotent matrix and an invertible matrix. I mess around with block decompositions for a few minutes: it looks very fiddly. Throwing some more technology at the problem, I decide we can assume $M$ is diagonalizable (by density passing to the complex numbers), and in fact diagonal (by conjugation). Then the block decompositions look more tractable: putting

$M = \left( \begin{matrix} D & 0 \\ 0 & 0 \end{matrix} \right), A = \left( \begin{matrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} \right), B = \left( \begin{matrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{matrix} \right)$

we get

$AM = \left( \begin{matrix} A_{11} D & 0 \\ A_{21} D & 0 \end{matrix} \right) = \left( \begin{matrix} D B_{11} & DB_{12} \\ 0 & 0 \end{matrix} \right) = MB$

so $A_{21} = 0$, $B_{12} = 0$ and $A_{11}D = DB_{11}$ with $D$ invertible. So we need

$\left( \begin{matrix} A_{11} - DX_{11} & A_{12} - DX_{12} \\ 0 & A_{22} \end{matrix} \right), \left( \begin{matrix} B_{11} - X_{11}D & 0 \\ B_{21} - X_{21} D & B_{22} \end{matrix} \right)$

to have the same determinant. The determinants factorize: the contributions from the top left are equal by the invertible case. The characteristic polynomials also factorize, so, as in the zero case, $\mathrm{det} A_{22} = \mathrm{det} B_{22}$.

Final thoughts. All this took about two hours, with some breaks for chess / tea-making. I don’t feel inclined to go back to A5, so call it a day. I enjoyed doing A4, but otherwise it felt like a bit of a slog. Maybe I am too quick to reach for my trusty computer algebra system? Or maybe my experience also shows the increasing artificiality of time-limited, closed-book, no-internet, no-collaboration, no-technological-assistance tests such as the Putnam?

It seems to me that A1 can be solved without any calculation by the following reduction to a symmetric situation. Given $A$ and $B$ on the same branch of the hyperbola, let $P$ maximize the area of the triangle $APB$ as assumed. Now perform a change of coordinates, namely a “scaling” in $y$, say, by which I mean $x'=x$ and $y'=my$, so as to bring P onto the line $x'=y'$. Note that all areas scale accordingly by the same factor (so the problem is sort of “invariant” under this). Because of maximality of the area of $APB$ it is clear that the segment $AB$ must be parallel to the tangent in $P$, hence to the line $x'+y'=0$. But then the two regions bounded by the hyperbola and the chord $AP$, and by the hyperbola and the chord $BP$, are symmetric with respect to the line $x'=y'$, and hence have the same area.
Nice! It’s important that scaling the $y$-coordinate alone does not change the shape of the hyperbola. This is algebraically obvious: $xmy = 1$ if and only if $xy = 1/m$, but it hadn’t occurred to me before. Thank you for your comment.