2008 Putnam problems

This year's Putnam exam problems, via 360.

I haven't thought about these, but I might as a break from writing things up over the next few days.

Street Fighting Mathematics

18.098/6.099. Street Fighting Mathematics, a course currently being offered during MIT's Independent Activities Period, by Sanjoy Mahajan. (I got a call from MIT asking me for money tonight; I donated some; that got me thinking about the Institute so I poked around the web site a bit.)

The course description is as follows:

The art of guessing results and solving problems without doing a proof or an exact calculation. Techniques include extreme-cases reasoning, dimensional analysis, successive approximation, discretization, generalization, and pictorial analysis. Application to mental calculation, solid geometry, musical intervals, logarithms, integration, infinite series, solitaire, and differential equations. (No epsilons or deltas are harmed by taking this course.)

Personally, I always thought the epsilons and deltas were harming me. The text (a draft version of which can be found on the course web page) stresses the idea that approximate answers, heuristics, etc. are more valuable than they are often claimed to be, which is a question that Mahajan also took on in his PhD thesis, which is a combination of a version of such a textbook and some extended examples on what one might call "research-level" problems, one of which is a probabilistic model of the primes which it is too late at night to seriously read.

From a quick poke around the web page, it looks like Mahajan also offered a similar, but more physics-oriented course in IAP 2006, as well as TAing a couple more substantial courses in the same vein at Caltech called "Order-of-Magnitude Physics". (The MIT IAP course meets three hours a week for four weeks and carries one-quarter the credit that a "normal" course at MIT would carry; the Caltech courses appear to have met three hours a week for ten weeks. As such, they have more problem sets. But they're also more physics-y, which may be good or bad depending on how you feel about physics.

Problem A3 from the Putnam

Here is problem A3 from the 2007 Putnam exam:

Let k be a positive integer. Suppose that the integers 1, 2, 3, ..., 3k+1 are written down in random order. What is the probability that at no time during this process, the sum of the integers that have been written up to that time is a positive integer divisible by 3?

I'm going to give a solution that probably wouldn't get full credit on the Putnam (I'm leaving out some details) -- a lot gets lost in the details.

First, instead of considering these numbers, just consider everything modulo 3. In particular, we want to know what the probability is that if we arrange k+1 +1s, k -1s, and k 0s in random order, no partial sum will be divisible by 3. (The number of permutations of {1, ..., 3k+1} which map to a given sequence modulo 3 is the same for any such sequence, so this is legitimate.) The number of ways to arrange k+1 +1s, k -1s, and k 0s is, of course, .

Now we consider the simpler problem of arranging k+1 +1s and k -1s so that no partial sum is divisible by 3. Clearly the last partial sum (i. e. the full sum) is 1, and the sequence of partial sums moves upwards or downwards by 1 at each step. Such an arrangement must begin with a +1; if it began with a -1 then the first partial sum would be -1, the last partial sum would be 1, so some intermediate partial sum would have to be zero. This +1 must be followed with another +1 to avoid having the second partial sum be 0; then a -1 so that the third partial sum is not 3; and so on. Thus there is exactly one such arrangement, namely

+1, +1, -1, +1, -1, +1, -1, ..., +1, -1

where the partial sums are

1, 2, 1, 2, 1, 2, 1, ..., 2, 1.

The probability of obtaining an arrangement with no partial sums divisible by three if we pick at random from all arrangements of k+1 +1s and k -1s is thus .

Now, to obtain an arrangement of k+1 +1s, k -1s, and k 0s uniformly at random, we can first place the 0s at random, then the +1s and -1s. There are ways in which the 0s can be placed. Interspersing 0s among some arrangement of +1s and -1s doesn't change the set of partial sums which occur -- unless a 0 precedes all the +1s and -1s. So the probability of placing the 0s such that a "good" arrangement is still possible is . There is exactly one way to place the +1s and -1s once we've done this that actually gives a "good" arrangement. So the final probability is

For example, f(1) = 1/4 = 6/24; this corresponds to the six "good" arrangements of {1, 2, 3, 4}, namely 1342, 1432, 1423, 4312, 4132, 4123. The function f(k) is asymptotic to from Stirling's approximation. I like to interpret the 4 there as meaning that if we are building up such an arrangement of +1s, -1s, and 0s, we have a probability of roughly 1/4^1/3 of making an acceptable choice at each step; the "1/3" comes from the fact that we actually make 3k choices in building up such an arrangement. This constant is about 0.63, and seems about right; it should be around two-thirds, since at each step except the first, exactly two of {0, +1, -1} are valid ways to extend the sequence.

The simplicity of the problem seems to hinge on the fact that the partial sums have to fluctuate within a very narrow band, and only move by ± 1. If we instead required that no partial sums were divisible by, say, 4, so the partial sums could move around in {1, 2, 3}, this would be trickier. But I think the best way to work that problem would still be to work modulo 3, so each summand is either +1, -1, or 0; the crucial observation I made early on was that if the partial sum was -1 at some point and +1 later it had to go through zero, but you don't get this sort of "continuity" (the observation is a discrete analogue of the Intermediate Value Theorem) in any modulus other than 3.

(This is basically the same as the solution given at the UNL Putnam archive, but I came up with it independently.)

N ways to solve a differential equation

Mark Dominus writes about how to solve the differential equation (f(x))² + (f^'(x))² = 1, which arises in the analysis of LC-circuits.
Go ahead, try it. There are at least four distinct solutions given there (bearing in mind the usual caveats about distinctness of solutions); I won't give any of them. If you want to know how I solved it, read Dominus' post, which ends with:

I would like to add a pithy and insightful conclusion to this article, but I've been working on it for more than a week now, and also it's almost lunch time, so I think I'll have to settle for observing that sometimes there are a lot of ways to solve math problems.

That's something definitely worth remembering.

As to why I ended up using a power series approach, which you'll see explained in the link: I'd been teaching the solution of differential equations by power series at the time, so it seemed natural to do that rather than to look for some kind of trick.

Partitions with maximal products

Consider all the ways that we can write an integer n as a sum of nonnegative integers. Then for each of these sums take the product of the summands. What is the largest such product?

For example, we can write
6 = 5+1 = 4+2 = 4+1+1 = 3+3 = 3+2+1 = 3+1+1+1 = 2+2+2 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1
and the corresponding products are
6, 5, 8, 4, 9, 6, 3, 8, 4, 2, 1
of which 9 = 3 × 3 is the largest.

First, any partition of n (that's what these sums are called) which includes a 1 does not give rise to the maximal product. If we have n = a₁ + ... + a_k-1 + a_k + 1, then this corresponds to the product a₁...a_k; clearly we can rewrite n as
n = a₁ + ... + a_k-1 + (a_k + 1)
(where we've combined a_k and 1 into a single part), and
a₁a₂...a_k-1(a_k+1)
is larger.
Similarly, any partition of n which contains a part which is 5 or larger can't give rise to the maximal product. Simply replace a part k ≥ 5 by (k-3)+3.

So any partition of n having maximal product has all its parts equal to 2, 3, or 4. Furthermore, we can break a part equal to 4 into two parts equal to 2 without changing the product; for example 4+3 and 3+2+2 both give the product 12. So if we just care about the value of the maximal product, it's enough to consider parts equal to 2 or 3.

Finally, any partition containing three or more parts equal to 2 doesn't have maximal product; we can replace 2+2+2 with 3+3 and increase the product. For example, 3+2+2+2+2 is not the partition of 11 having maximal product (it has product 48) since we can replace three of the parts equal to 2 with two parts equal to 3, giving 3+3+3+2, which has product 54.

So the maximal product of a partition of n must be given by a partition which has all parts equal to 3, except for zero, one, or two parts equal to 2. Furthermore, considering n modulo 3 tells us that only one of these three situations is possible. Thus, we see that:
- the maximal product of a partition of 3n has n parts equal to 3, and has product 3 × 3^n-1;
- the maximal product of a partition of 3n+1 has n-1 parts equal to 3 and two parts equal to 2, and has product 4 × 3^n-1;
- the maximal product of a partition of 3n+2 has n parts equal to 3 and one part equal to 2, and has product 6 × 3^n-1.
For example, the partition of 12 having maximal product is 3+3+3+3, with product 81; the partition of 13 having maximal product is 3+3+3+2+2, with product 108; the partition of 14 having maximal product is 3+3+3+3+2, with product 162. These are unique, except that in the 3n+1 case we can replace the two 2s with one 4.

The sequence generated in this way is in the Encyclopedia of Integer Sequences; although I invented the problem myself, it's (unsurprisingly) well-known in problem-solving circles. For example, it was 1979 Putnam exam problem A1 (in the special case n = 1979) and 1976 IMO problem B1 (in the special case n = 1976).

What is the simplest problem you cannot solve?

I'm currently reading The Cauchy-Schwarz Master Class (link goes to MAA review, which pretty well explains the book's raison d'etre and contents) by J. Michael Steele. (How did I find this book? I'm taking Steele's course "Probability Inequalities and Machine Learning"; he alludes to this book every so often.)
It is full of interesting inequalities, and I may have something to say about them later, but I just wanted to share the following, where Steele is talking about George Polya and his book How to Solve It:

Some of the richest of Polya's suggestions may be repackaged as the modestly paradoxical question: "What is the simplest problem you cannot solve?".... Perhaps no other discipline can contribute more to one's effectiveness as a solver of mathematical problems.

I think this is worth remembering.