Sunday, December 7, 2008

Selected Putnam Problems

At least one reader (Susan!) expressed interest in seeing the Putnam problems.

For those not in the know, the William Lowell Putnam Competition is a national math competition intended for college undergrads such as myself. The yearly contest consists of twelve problems (rigorous proof required) and six hours' time. The problems range from moderate to very difficult. Well that's kind of subjective. A more enlightening description: a few thousand students participate each year, and the median (not the mean!) is roughly zero.

I have it on good authority that it's safe to talk about them now. You can refer to the Art of Problem Solving forums for a more complete discussion of the entire 2008 contest.

So here are three of the problems. I picked out easy ones with more of an "aha!" feel to them.

A1: Let f: ℝ2 → ℝ be a function such that f(x,y) + f(y,z) + f(z,x) = 0 for all real numbers x, y, and z. Prove that there exists a function g: ℝ→ ℝ such that f(x,y) = g(x) - g(y) for all real numbers x and y.

A2: Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008x2008 array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all the entries are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?

B1: What is the maximum number of rational points that can lie on a circle in ℝ2 whose center is not a rational point? (A rational point is a point both of whose coordinates are rational numbers.)

How did I do, you ask? I think I got four correct, but I hear the graders are particularly harsh, so you never know. I didn't get A2 and B1, but they sure seemed obvious afterwards. If you're still curious, ask me in the comments.

1 comment:

intrinsicallyknotted said...

In my experience (and from what I've been told), for a very complete answer, you'll get 9 or 10 points, but for a nearly complete answer, you'll only get 1 or 2 points. That said, last year I missed the trivial case on one question and still got full credit on it (I got 12 points total, and I'm assuming 10 of those came from that one question).

A1 is actually surprisingly easy (either that or a semester of grad school has boosted my problem-solving ability considerably!)

For any x, f(x, x) + f(x, x) + f(x, x) = 0, so f(x, x) = 0. Therefore for any x, y, f(x, y) + f(y, x) + f(x, x) = 0 implies f(x, y) = -f(y, x). So fix z (any real number will do), and let g(x) = f(x, z). Then for any x, y, f(x, y) = -f(z, x) - f(y, z) = f(x, z) - f(y, z) = g(x) - g(y).

I considered for a moment the possibility that f(x, y) = 0 for all x, y, but that's not the case: f(x, y) = x - y is a nontrivial example.

Thanks for posting these! I'll have to think about the others for a bit.