Difference between revisions of "2012 USAMO Problems/Problem 1"
(→See also) |
(→Solution) |
||
Line 12: | Line 12: | ||
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>. | 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:''' | ||
+ | |||
+ | 1. 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>. | ||
+ | |||
+ | 2. 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} (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. | ||
+ | |||
+ | 3. 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. | ||
+ | |||
+ | 4. 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== | ==See also== |
Revision as of 23:10, 23 April 2014
Contents
[hide]Problem
Find all integers such that among any positive real numbers , , , with there exist three that are the side lengths of an acute triangle.
Solution
Without loss of generality, assume that the set is ordered from least to greatest so that the bounding condition becomes Now set and since a triangle with sidelengths from will be similar to the corresponding triangle from we simply have to show the existence of acute triangles in Note that and for all ,
Now three arbitrary sidelengths , , and , with will form a valid triangle if and only if Furthermore, this triangle will be acute if and only if However, the first inequality can actually be inferred from the second, since and is trivially greater than So we just need to find all such that there is necessarily a triplet of 's for which (where ).
We now make another substitution: So and for all , Now we examine the smallest possible sets for small 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 , then the smallest possible set, call it is trivially , since and are obviously minimized and follows as minimal. Using this as the base case, we see inductively that in general is the set of the first Fibonacci numbers. To show this note that if , then The smallest possible value for is the sum of the two greatest values of which are and . But these sum to so 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 whose greatest term is less than must satisfy the conditions. And since is bounded between and , then the conditions of the problem are met if and only if . The first for which this restriction is satisfied is and the exponential behavior of the Fibonacci numbers ensure that every greater than will also satisfy this restriction. So the final solution set is .
Solution 2
Outline:
1. Define the Fibonacci numbers to be and for .
2. If the chosen is such that , then choose the sequence such that for . It is easy to verify that such a sequence satisfies the condition that the largest term is less than or equal to times the smallest term. Also, because for any three terms , , x, y, z do not form an acute triangle. Thus, all such that do not work.
3. It is easy to observe via a contradiction argument that all such that produce an acute triangle.
4. Note that and . It is easily to verify through strong induction that all greater than 12 make . Thus, is the desired solution set.
See also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.