## 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.

### 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.