Difference between revisions of "2000 USAMO Problems/Problem 1"
(→Solution) |
|||
Line 6: | Line 6: | ||
holds for all real numbers <math>x</math> and <math>y</math>. Prove that no very [[convex]] [[function]] exists. | holds for all real numbers <math>x</math> and <math>y</math>. Prove that no very [[convex]] [[function]] exists. | ||
− | == Solution == | + | == Solution 1 == |
Let <math>y \ge x</math>, and substitute <math>a = x, 2b = y-x</math>. Then a function is very convex if <math>\frac{f(a) + f(a+2b)}{2} \ge f(a + b) + 2b</math>, or rearranging, | Let <math>y \ge x</math>, and substitute <math>a = x, 2b = y-x</math>. Then a function is very convex if <math>\frac{f(a) + f(a+2b)}{2} \ge f(a + b) + 2b</math>, or rearranging, | ||
<cmath>\left[\frac{f(a+2b)-f(a+b)}{b}\right]-\left[\frac{f(a+b)-f(a)}{b}\right] \ge 4</cmath> | <cmath>\left[\frac{f(a+2b)-f(a+b)}{b}\right]-\left[\frac{f(a+b)-f(a)}{b}\right] \ge 4</cmath> | ||
− | Let <math>g(a) = \frac{f(a+b) - f(a)}{b}</math>, which is the slope of the secant between <math>(a,f(a))(a+b,f(a+b))</math>. Let <math>b</math> be arbitrarily small; then it follows that <math>g(a+b) - g(a) > 4</math>, <math>g(a+2b) - g(a+b) > 4,\, \cdots, g(a+kb) - g(a+ [k-1]b) > 4</math>. Summing these inequalities yields <math>g(a+kb)-g(a) > 4k</math>. As <math>k \rightarrow \infty</math> (but <math>b << \frac{1}{k}</math>, so <math>bk < \epsilon</math> is still arbitrarily small), we have <math>\lim_{k \rightarrow \infty} g(a+kb) - g(a) = g(a + \epsilon) - g(a) > \lim_{k \rightarrow \infty} 4k = \infty</math>. This implies that in the vicinity of any <math>a</math>, the function becomes vertical, which contradicts the definition of a function. Hence no very convex function exists. | + | Let <math>g(a) = \frac{f(a+b) - f(a)}{b}</math>, which is the slope of the secant between <math>(a,f(a))(a+b,f(a+b))</math>. Let <math>b</math> be arbitrarily small; then it follows that <math>g(a+b) - g(a) > 4</math>, <math>g(a+2b) - g(a+b) > 4,\, \cdots, g(a+kb) - g(a+ [k-1]b) > 4</math>. Summing these inequalities yields <math>g(a+kb)-g(a) > 4k</math>. As <math>k \rightarrow \infty</math> (but <math>b << \frac{1}{k}</math>, so <math>bk < \epsilon</math> is still arbitrarily small), we have <math>\lim_{k \rightarrow \infty} g(a+kb) - g(a) = g(a + \epsilon) - g(a) > \lim_{k \rightarrow \infty} 4k = \infty</math>. This implies that in the vicinity of any <math>a</math>, the function becomes vertical, which contradicts the definition of a function. Hence no very convex function exists. |
+ | |||
+ | |||
+ | == Solution 2 == | ||
+ | Suppose, for the sake of contradiction, that there exists a very convex function <math>f.</math> Notice that <math>f(x)</math> is convex if and only if <math>f(x) + C</math> is convex, where <math>C</math> is a constant. Thus, we may set <math>f(0) = 0</math> for convenience. | ||
+ | |||
+ | Suppose that <math>f(1) = A</math> and <math>f(-1) = B.</math> By the very convex condition, | ||
+ | <math>\frac{f(0) + f\left(2^{-n}\right)}{2} \ge f\left(2^{-(n+1)}\right) + \frac{1}{2^n}.<cmath> | ||
+ | A straightforward induction shows that: | ||
+ | </cmath>f\left(2^{-n}\right) \le \frac{A - 2n}{2^n}</math><math> | ||
+ | for all nonnegative integers </math>n.<math> | ||
+ | Using a similar line of reasoning as above, | ||
+ | <cmath>f\left(-2^{-n}\right) \le \frac{B - 2n}{2^n}.</cmath> | ||
+ | Therefore, for every nonnegative integer </math>n,<math> | ||
+ | <cmath>f\left(2^{-n}\right) + f\left(-2^{-n}\right) \le \frac{A+B-4n}{2^n}.</cmath> | ||
+ | Now, we choose </math>n<math> large enough such that </math>n > \frac{A+B}{4} - 1.<math> This is always possible because </math>A<math> and </math>B<math> are fixed for any particular function </math>f.$ It follows that: | ||
+ | <cmath>f\left(2^{-n}\right) + f\left(-2^{-n}\right) < \frac{1}{2^{n-2}}.</cmath> | ||
+ | However, by the very convex condition, | ||
+ | <cmath>f\left(2^{-n}\right) + f\left(-2^{-n}\right) \ge \frac{1}{2^{n-2}}.</cmath> | ||
+ | This is a contradiction. It follows that there exists no very convex function. | ||
== See Also == | == See Also == |
Revision as of 00:55, 5 April 2016
Contents
Problem
Call a real-valued function very convex if
holds for all real numbers and
. Prove that no very convex function exists.
Solution 1
Let , and substitute
. Then a function is very convex if
, or rearranging,
Let , which is the slope of the secant between
. Let
be arbitrarily small; then it follows that
,
. Summing these inequalities yields
. As
(but
, so
is still arbitrarily small), we have
. This implies that in the vicinity of any
, the function becomes vertical, which contradicts the definition of a function. Hence no very convex function exists.
Solution 2
Suppose, for the sake of contradiction, that there exists a very convex function Notice that
is convex if and only if
is convex, where
is a constant. Thus, we may set
for convenience.
Suppose that and
By the very convex condition,
n.
n,
n
n > \frac{A+B}{4} - 1.
A
B
f.$ It follows that:
However, by the very convex condition,
This is a contradiction. It follows that there exists no very convex function.
See Also
2000 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.