Putnam 2012, Problem A-1

Let $d_1, d_2, \ldots, d_{12}$ be real numbers in the open interval $(1,12)$. Show that there exist distinct indices $i, j, k$ such that $d_i, d_j, d_k$ are the side lengths of an acute triangle.

Solution:
Without loss of generality, assume $d_1 \leq d_2 \leq \cdots \leq d_{12}$. If $d_{i+2}^2 < d_i^2 + d_{i+1}^2$ for some $i \leq 10$, then $d_i, d_{i+1}, d_{i+2}$ are the side lengths of an acute triangle, since in this case $d_i^2 < d_{i+1}^2 + d_{i+2}^2$ and $d_{i+1}^2 < d_i^2 + d_{i+2}^2$ as well. Thus we may assume $d_{i+2}^2 \geq d_i^2 + d_{i+1}^2$ for all $i$. But then by induction, $d_i^2 \geq F_i d_1^2$ for all $i$, where $F_i$ is the $i$-th Fibonacci number (with $F_1 = F_2 = 1$): $i = 1$ is clear, $i = 2$ follows from $d_2 \geq d_1$, and the induction step follows from the assumed inequality. Setting $i = 12$ now gives $d_{12}^2 \geq 144d_1^2$, contradicting $d_1 > 1$ and $d_{12} < 12$.

**Remark.** A materially equivalent problem appeared on the 2012 USA Mathematical Olympiad and USA Junior Mathematical Olympiad.