2012 USAMO Problems/Problem 1

Problem

Find all integers $n \ge 3$ such that among any $n$ positive real numbers $a_1$ , $a_2$ , $\dots$ , $a_n$ with $\max(a_1, a_2, \dots, a_n) \le n \cdot \min(a_1, a_2, \dots, a_n),$ there exist three that are the side lengths of an acute triangle.

Solution

Without loss of generality, assume that the set $\{a\}$ is ordered from least to greatest so that the bounding condition becomes $a_n \le n \cdot a_1.$ Now set $b_i \equiv \frac{a_i}{a_1},$ and since a triangle with sidelengths from $\{a\}$ will be similar to the corresponding triangle from $\{b\},$ we simply have to show the existence of acute triangles in $\{b\}.$ Note that $b_1 = 1$ and for all $i$ , $b_i \le n.$

Now three arbitrary sidelengths $x$ , $y$ , and $z$ , with $x \le y \le z,$ will form a valid triangle if and only if $x+y>z.$ Furthermore, this triangle will be acute if and only if $x^2 + y^2 > z^2.$ However, the first inequality can actually be inferred from the second, since $x+y>z \longrightarrow x^2 + y^2 +2xy > z^2$ and $2xy$ is trivially greater than $0.$ So we just need to find all $n$ such that there is necessarily a triplet of $b$ 's for which $b_i^2 + b_j^2 > b_k^2$ (where $b_i < b_j < b_k$ ).

We now make another substitution: $c_i \equiv b_i ^2.$ So $c_1 = 1$ and for all $i$ , $c_i \le n^2.$ Now we examine the smallest possible sets $\{c\}$ for small $n$ for which the conditions of the problem are not met. Note that by smallest, we mean the set whose greatest element is as small as possible. If $n=3$ , then the smallest possible set, call it $\{s_3\},$ is trivially $\{1,1,2\}$ , since $c_1$ and $c_2$ are obviously minimized and $c_3$ follows as minimal. Using this as the base case, we see inductively that in general $\{s_n\}$ is the set of the first $n$ Fibonacci numbers. To show this note that if $\{s_n\} = \{F_0, F_1, ... F_n\}$ , then $\{s_{n+1}\} = \{F_0, F_1, ... F_n, c_{n+1}\}.$ The smallest possible value for $c_{n+1}$ is the sum of the two greatest values of $\{s_n\}$ which are $F_{n-1}$ and $F_n$ . But these sum to $F_{n+1}$ so $\{s_{n+1}\} = \{F_0, F_1, ... F_{n+1}\}$ and our induction is complete.

Now since we know that the Fibonacci set is the smallest possible set which does not satisfy the conditions of the problem, then any set $\{c\}$ whose greatest term is less than $F_{n-1}$ must satisfy the conditions. And since $\{c\}$ is bounded between $1$ and $n^2$ , then the conditions of the problem are met if and only if $F_{n-1} > n^2$ . The first $n$ for which this restriction is satisfied is $n=13$ and the exponential behavior of the Fibonacci numbers ensure that every $n$ greater than $13$ will also satisfy this restriction. So the final solution set is $\boxed{\{n \ge 13\}}$ .

2012 USAMO (Problems • Resources)
First Problem	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2012 USAMO Problems/Problem 1

Problem

Solution

See also