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 and be points on the same branch of the hyperbola . Suppose that is a point lying between and on this hyperbola, such that the area of the triangle is as large as possible. Show that the region bounded by the hyperbola and the chord has the same area as the region bounded by the hyperbola and chord .
Thoughts / solution. This looks like a routine optimization problem. Put at , at and at , with . The first region is formed from the quadrilateral with vertices , missing out the area below the hyperbola from to . So its area is
Similarly the second region has area
I can see that 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 . This can’t be right. Turning to Mathematica I get the correct sum, and by differentiating, see that it is minimized when . 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 .
(In retrospect, this had to be the right , because by the moral linear independence of arbitrary transcendentals, there’s no way the expressions will be equal without the logs agreeing.)
A2. Let , and for . Find an odd prime factor of .
Thoughts / solution. I immediately load the problem into Mathematica and compute the factorizations of . It looks like is always a factor of when is odd. Since , this would do it. After some dithering with matrices versus direct manipulation of the recurrence, I use Mathematica with
b := b0; b := b1; b[n_] := 4b[n-1] - b[n-2]
to find . It follows that
for all . Since , the claim follows by induction. Thinking that this wouldn’t have been much fun to do without computer algebra, I press on.
Here is the imaginary unit (that is, ).
Thoughts / solution. My immediate thought is ‘who is going to know the definition of the complex exponential function, but get confused by ‘? Next I put the product into Mathematica, replacing with a general . After some confusing errors, I realize that (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 when (or rather, a more Mathematica-friendly letter) is even, and a power of when is odd. A trivial change in the code lets me compute
Of course its still a power of , but the exponent is still not obvious. Fairly quickly I realise I’ve encountered the product
where is a primitive 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 at . So and, after some stupid slips and general lack of progress, I realise that
This reduces the problem to evaluating . Turning to a small example, I see how this works for : we have coprime numbers with gcd , then each contribute , and each contribute . 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 , not those satisfying some ‘sievable’ property, it starts to feel like the wrong approach. Going back to the example, I realise that there are exactly numbers with gcd . So we need
It looks like might be multiplicative. Yes it is. I evaluate , then realise I’m wasting time, since I should remember from A2 that is square-free. Clearly
A4. For each real number , let
where is the set of positive integers for which is even. What is the largest real number such that for all ? (As usual denotes the greatest integer less than or equal to .)
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 . I evaluate
N[f[1000, 2/3 - 0.0001], 20] and get . I should recognise this immediately as , 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 we get an immediate contribution of , so is indicated. Then makes sure that we don’t get , so it looks like . But then we have , so and we do get . 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 is equal to , nothing is more important at the th step than avoiding , 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 containing , such that the lower bound from the greedy strategy after steps is less than . Then we would `dodge’ left of this interval, and lose control of . I try to make this work for at least 10 minutes, not getting anywhere much. Maybe only prime values of are relevant? I get Mathematica to show me the relevant intervals with the code below.
This shows that is a lower bound from the greedy strategy not coming from prime . But more importantly, I finally see the pattern: starting at , we have
since is odd, the greedy strategy tells us that . For the next we have
so , but this is already implied. Next
and since , there is no way to avoid . So taking arbitrarily close to we can get arbitrarily close to
A5. Let be an odd positive integer, and let denote the number of integers such that and . Show that is odd if and only if is of the form with a positive integer and a prime congruent to or modulo .
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 be a positive integer. Suppose that , and are matrices with real entries such that and such that and have the same characteristic polynomial. Prove that for every matrix 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 is invertible then we’re done, since then and so
Thinking about the other extreme case, when is , the condition tells us nothing, but now all we need is , which follows from the assumption on the characteristic polynomials.
By Fitting’s Lemma we can write 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 is diagonalizable (by density passing to the complex numbers), and in fact diagonal (by conjugation). Then the block decompositions look more tractable: putting
so , and with invertible. So we need
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, .
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?