On 2012 Putnam problem A1

The Putnam competition was last weekend, on December 1. I was coaching Smith’s team this year, so I’d like to go through solutions to each of the problems (or as many as I can solve), with my students being the intended audience. But I’ll post the solutions on this blog, since I’m sure they’ll be of interest to a wider audience.

I’ll start with the first one, Problem A1. It’s often the case that Putnam problems can be solved in several different ways, but sometimes you discover a solution that is clearly the most elegant of all possible approaches. That’s the case with this one, although I will include greater-than-necessary detail for pedagogical purposes.

Here is the problem, rephrased in what I think is simpler language (I’ll save my complaints about the wording of the problems for another day): Show that, if you are given a set of twelve numbers d_1, d_2, \dots, d_{12} on the interval (1,12), then, no matter what those numbers are, it’s always possible to pick three of the numbers d_i, d_j, d_k such that these three numbers are the side lengths of an acute triangle.

The solution is below Nyan Cat, so stop reading now if you don’t want to see the solution yet.

poptart1red1

Solution:

The first thing to observe is that the geometric aspect of the problem (“acute triangle”) can be restated in purely algebraic terms. If a,b,c are the three sides of a triangle, with c being the longest side, then the triangle is acute if and only if a^2 + b^2 > c^2. You could say that this is a direct consequence of the Law of Cosines, but it’s probably okay to justify it by referring to the Pythagorean Theorem (If you start with a right triangle and then shrink the right angle, then the hypotenuse will shrink, and vice versa).

Without loss of generality, assume that the numbers are arranged in order: d_1 \leq d_2 \leq \dots \leq d_{12}. Since the numbers are on the interval (1,12), we know that d_1 and d_2 are greater than 1. If d_3 \leq \sqrt{2}, then we could conclude that d_1,d_2,d_3 form the side lengths of an acute triangle, and we would be done. So we can reduce the problem to the case where d_3 > \sqrt{2}.

Next, proceed similarly with d_4. If d_4 \leq \sqrt{3}, then we could conclude that d_2,d_3,d_4 form the side lengths of an acute triangle (since d_2 > 1 and d_3 > \sqrt{2}), and we would be done. So we can reduce the problem to the case where d_4 > \sqrt{3}.

It’s worth doing this one more time before claiming a general pattern. If d_5 \leq \sqrt{5}, then we could conclude that d_3,d_4,d_5 form the side lengths of an acute triangle (since d_3 > \sqrt{2} and d_4 > \sqrt{3}), and we would be done. So we can reduce the problem to the case where d_5 > \sqrt{5}.

To summarize where we are so far, either we’ve already found an acute triangle among the first five numbers, or the following inequalities hold:

d_1 > 1,

d_2 > 1,

d_3 > \sqrt{2},

d_4 > \sqrt{3},

d_5 > \sqrt{5}.

Hopefully you see the pattern; we’re getting the square roots of the numbers in the Fibonacci sequence! With hindsight, we can look back at the algorithm we’ve been using and see that this isn’t a coincidence. For each number, we squared the previous two numbers, added, and then took the square root; this is exactly the recurrence relation that the square roots of the Fibonacci numbers satisfy.

Now it’s easy to keep going. Either we’ll find an acute triangle, or

d_6 > \sqrt{8},

d_7 > \sqrt{13},

d_8 > \sqrt{21},

d_9 > \sqrt{34},

d_{10} > \sqrt{55},

d_{11} > \sqrt{89}.

Finally, we know from the assumptions of the problem that d_{12} < 12, so if we haven’t found an acute triangle among the first eleven numbers, then d_{10}^2 + d_{11}^2 > 144 > d_{12}^2, and there we have an acute triangle.

QED.

Remarks

Something we can observe from this proof is that the result is sharp. That is, if the numbers were allowed to be on the closed interval [1,12], then we could take d_1 = 1, d_2 = 1, d_3 = \sqrt{2}, … ,d_{11} = \sqrt{89}, d_{12} = 12, and then there would be no acute triangles. Alternatively, if there were eleven numbers, instead of twelve, on the interval (1,12), then it would be possible for there to be no acute triangles.

This type of sharpness is typical of Putnam problems. If they could weaken the assumptions without making the result false (or significantly harder to prove), then they would have done so. If you came up with a solution like this, then it should have “felt” correct since it fully used all the assumptions of the problem, and the unexpected appearance of the Fibonacci sequence made it more interesting than it might have seemed at first. These are common characteristics of Putnam problems.

Advertisements
Tagged , , ,

2 thoughts on “On 2012 Putnam problem A1

  1. […] to write solutions to the problems on this year’s Putnam competition. I previously posted a solution to problem A1. Problem A2 seems like it should have been reasonable for students familiar with abstract algebra, […]

  2. […] write detailed solutions to the problems on this year’s Putnam exam (previous solutions are here and here). More than the actual solutions, I hope that students will find my commentary valuable. […]

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: