Difference between revisions of "2012 USAMO Problems/Problem 1"

Latest revision as of 01:17, 7 March 2018

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\}}$ .

Solution 2

Outline:

1. Define the Fibonacci numbers to be $F_1 = F_2 = 1$ and $F_k = F_{k-1} + F_{k-2}$ for $k \ge 3$ .

2. If the chosen $n$ is such that $F_n \le n^2$ , then choose the sequence $a_n$ such that $a_k = \sqrt{F_k}$ for $1 \le k \le n$ . It is easy to verify that such a sequence satisfies the condition that the largest term is less than or equal to $n$ times the smallest term. Also, because for any three terms $x = \sqrt{F_a}, y = \sqrt{F_b}, z = \sqrt{F_c}$ with $a<b<c$ , $x^2 + y^2 = F_a + F_b \le F_{b-1} + F_b = F_{b+1} \le F_c = z^2$ , x, y, z do not form an acute triangle. Thus, all $n$ such that $F_n \le n^2$ do not work.

3. It is easy to observe via a contradiction argument that all $n$ such that $F_n > n^2$ produce an acute triangle. (If, without loss of generality, $a_n$ is an increasing sequence, such that no three (in particular, consecutive) terms form an acute triangle, then $a_2^2 \ge F_1a_1^2, a_3^2 \ge a_2^2 + a_1^2 \ge F_2a^2$ , and by induction $a_n^2 > F_na_1^2$ , a contradiction to the condition's inequality.)

4. Note that $F_{12} = 144 = 12^2$ and $F_{13} = 233 > 169 = 13^2$ . It is easily to verify through strong induction that all $n$ greater than 12 make $F_n > n^2$ . Thus, $\boxed{n \ge 13}$ is the desired solution set.

@@ Line 5: / Line 5: @@
 ==Solution==
+Without loss of generality, assume that the set <math>\{a\}</math> is ordered from least to greatest so that the bounding condition becomes <math>a_n \le n \cdot a_1.</math> Now set <math>b_i \equiv \frac{a_i}{a_1},</math> and since a triangle with sidelengths from <math>\{a\}</math> will be similar to the corresponding triangle from <math>\{b\},</math> we simply have to show the existence of acute triangles in <math>\{b\}.</math> Note that <math>b_1 = 1</math> and for all <math>i</math>, <math>b_i \le n.</math>
+Now three arbitrary sidelengths <math>x</math>, <math>y</math>, and <math>z</math>, with <math>x \le y \le z,</math> will form a valid triangle if and only if <math>x+y>z.</math> Furthermore, this triangle will be acute if and only if <math>x^2 + y^2 > z^2.</math> However, the first inequality can actually be inferred from the second, since <math>x+y>z \longrightarrow x^2 + y^2 +2xy > z^2</math> and <math>2xy</math> is trivially greater than <math>0.</math> So we just need to find all <math>n</math> such that there is necessarily a triplet of <math>b</math>'s for which <math>b_i^2 + b_j^2 > b_k^2</math> (where <math>b_i < b_j < b_k</math>).
+We now make another substitution: <math>c_i \equiv b_i ^2.</math> So <math>c_1 = 1</math> and for all <math>i</math>, <math>c_i \le n^2.</math> Now we examine the smallest possible sets <math>\{c\}</math> for small <math>n</math> 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 <math>n=3</math>, then the smallest possible set, call it <math>\{s_3\},</math> is trivially <math>\{1,1,2\}</math>, since <math>c_1</math> and <math>c_2</math> are obviously minimized and <math>c_3</math> follows as minimal. Using this as the base case, we see inductively that in general <math>\{s_n\}</math> is the set of the first <math>n</math> Fibonacci numbers. To show this note that if <math>\{s_n\} = \{F_0, F_1, ... F_n\}</math>, then <math>\{s_{n+1}\} = \{F_0, F_1, ... F_n, c_{n+1}\}.</math> The smallest possible value for <math>c_{n+1}</math> is the sum of the two greatest values of <math>\{s_n\}</math> which are <math>F_{n-1}</math> and <math>F_n</math>. But these sum to <math>F_{n+1}</math> so <math>\{s_{n+1}\} = \{F_0, F_1, ... F_{n+1}\}</math> 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 <math>\{c\}</math> whose greatest term is less than <math>F_{n-1}</math> must satisfy the conditions. And since <math>\{c\}</math> is bounded between <math>1</math> and <math>n^2</math>, then the conditions of the problem are met if and only if <math>F_{n-1} > n^2</math>. The first <math>n</math> for which this restriction is satisfied is <math>n=13</math> and the exponential behavior of the Fibonacci numbers ensure that every <math>n</math> greater than <math>13</math> will also satisfy this restriction. So the final solution set is <math>\boxed{\{n \ge 13\}}</math>.
+==Solution 2==
+'''Outline:'''
+. Define the Fibonacci numbers to be <math>F_1 = F_2 = 1</math> and <math>F_k = F_{k-1} + F_{k-2}</math> for <math>k \ge 3</math>.
+. If the chosen <math>n</math> is such that <math>F_n \le n^2</math>, then choose the sequence <math>a_n</math> such that <math>a_k = \sqrt{F_k}</math> for <math>1 \le k \le n</math>. It is easy to verify that such a sequence satisfies the condition that the largest term is less than or equal to <math>n</math> times the smallest term. Also, because for any three terms <math>x = \sqrt{F_a}, y = \sqrt{F_b}, z = \sqrt{F_c}</math> with <math>a<b<c</math>, <math>x^2 + y^2 = F_a + F_b \le F_{b-1} + F_b = F_{b+1} \le F_c = z^2</math>, x, y, z do not form an acute triangle. Thus, all <math>n</math> such that <math>F_n \le n^2</math> do not work.
+. It is easy to observe via a contradiction argument that all <math>n</math> such that <math>F_n > n^2</math> produce an acute triangle. (If, without loss of generality, <math>a_n</math> is an increasing sequence, such that no three (in particular, consecutive) terms form an acute triangle, then <math>a_2^2 \ge F_1a_1^2, a_3^2 \ge a_2^2 + a_1^2 \ge F_2a^2</math>, and by induction <math>a_n^2 > F_na_1^2</math>, a contradiction to the condition's inequality.)
+. Note that <math>F_{12} = 144 = 12^2</math> and <math>F_{13} = 233 > 169 = 13^2</math>. It is easily to verify through strong induction that all <math>n</math> greater than 12 make <math>F_n > n^2</math>. Thus, <math>\boxed{n \ge 13}</math> is the desired solution set.
 ==See also==
 *[[USAMO Problems and Solutions]]
+*[[USAJMO Problems and Solutions]]
 {{USAMO newbox|year=2012|beforetext=|before=First Problem|num-a=2}}
+{{USAJMO newbox|year=2012|ab=A|num-b=1|num-a=3}}
+{{MAA Notice}}
+[[Category:Olympiad Algebra Problems]]

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

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

Page

Toolbox

Search

Difference between revisions of "2012 USAMO Problems/Problem 1"

Latest revision as of 01:17, 7 March 2018

Contents

Problem

Solution

Solution 2

See also