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 Mth 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 nth 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?


2 Responses to Putnam 2016

  1. Sandro Mattarei says:

    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.

    • mwildon says:

      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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: