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

(Solution)
m (Problem)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
Call a real-valued function <math>f</math> ''very convex'' if
+
Call a real-valued [[function]] <math>f</math> ''very convex'' if
  
 
<cmath>\frac {f(x) + f(y)}{2} \ge f\left(\frac {x + y}{2}\right) + |x - y|</cmath>
 
<cmath>\frac {f(x) + f(y)}{2} \ge f\left(\frac {x + y}{2}\right) + |x - y|</cmath>
  
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 1 ==
+
== 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,
  
Line 14: Line 15:
  
  
== Solution 2 ==
+
=== 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, 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,
 
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>
+
<cmath>\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:
 
A straightforward induction shows that:
</cmath>f\left(2^{-n}\right) \le \frac{A - 2n}{2^n}</math><math>
+
<cmath>f\left(2^{-n}\right) \le \frac{A - 2n}{2^n}</cmath>
for all nonnegative integers </math>n.<math>
+
for all nonnegative integers <math>n.</math>
 
Using a similar line of reasoning as above,
 
Using a similar line of reasoning as above,
 
<cmath>f\left(-2^{-n}\right) \le \frac{B - 2n}{2^n}.</cmath>
 
<cmath>f\left(-2^{-n}\right) \le \frac{B - 2n}{2^n}.</cmath>
Therefore, for every nonnegative integer </math>n,<math>
+
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>
 
<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:
+
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.</math> It follows that:
 
<cmath>f\left(2^{-n}\right) + f\left(-2^{-n}\right) < \frac{1}{2^{n-2}}.</cmath>
 
<cmath>f\left(2^{-n}\right) + f\left(-2^{-n}\right) < \frac{1}{2^{n-2}}.</cmath>
 
However, by the very convex condition,
 
However, by the very convex condition,
 
<cmath>f\left(2^{-n}\right) + f\left(-2^{-n}\right) \ge \frac{1}{2^{n-2}}.</cmath>
 
<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.
+
This is a contradiction. It follows that no very convex function exists.
  
 
== See Also ==
 
== See Also ==
Line 36: Line 37:
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 +
[[Category:Functional Equation Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 00:45, 9 July 2017

Problem

Call a real-valued function $f$ very convex if

\[\frac {f(x) + f(y)}{2} \ge f\left(\frac {x + y}{2}\right) + |x - y|\]

holds for all real numbers $x$ and $y$. Prove that no very convex function exists.

Solution

Solution 1

Let $y \ge x$, and substitute $a = x, 2b = y-x$. Then a function is very convex if $\frac{f(a) + f(a+2b)}{2} \ge f(a + b) + 2b$, or rearranging,

\[\left[\frac{f(a+2b)-f(a+b)}{b}\right]-\left[\frac{f(a+b)-f(a)}{b}\right] \ge 4\]

Let $g(a) = \frac{f(a+b) - f(a)}{b}$, which is the slope of the secant between $(a,f(a))(a+b,f(a+b))$. Let $b$ be arbitrarily small; then it follows that $g(a+b) - g(a) > 4$, $g(a+2b) - g(a+b) > 4,\, \cdots, g(a+kb) - g(a+ [k-1]b) > 4$. Summing these inequalities yields $g(a+kb)-g(a) > 4k$. As $k \rightarrow \infty$ (but $b << \frac{1}{k}$, so $bk < \epsilon$ is still arbitrarily small), we have $\lim_{k \rightarrow \infty} g(a+kb) - g(a) = g(a + \epsilon) - g(a) > \lim_{k \rightarrow \infty} 4k = \infty$. This implies that in the vicinity of any $a$, 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 $f.$ Notice that $f(x)$ is convex if and only if $f(x) + C$ is convex, where $C$ is a constant. Thus, we may set $f(0) = 0$ for convenience.

Suppose that $f(1) = A$ and $f(-1) = B.$ By the very convex condition, \[\frac{f(0) + f\left(2^{-n}\right)}{2} \ge f\left(2^{-(n+1)}\right) + \frac{1}{2^n}.\] A straightforward induction shows that: \[f\left(2^{-n}\right) \le \frac{A - 2n}{2^n}\] for all nonnegative integers $n.$ Using a similar line of reasoning as above, \[f\left(-2^{-n}\right) \le \frac{B - 2n}{2^n}.\] Therefore, for every nonnegative integer $n,$ \[f\left(2^{-n}\right) + f\left(-2^{-n}\right) \le \frac{A+B-4n}{2^n}.\] Now, we choose $n$ large enough such that $n > \frac{A+B}{4} - 1.$ This is always possible because $A$ and $B$ are fixed for any particular function $f.$ It follows that: \[f\left(2^{-n}\right) + f\left(-2^{-n}\right) < \frac{1}{2^{n-2}}.\] However, by the very convex condition, \[f\left(2^{-n}\right) + f\left(-2^{-n}\right) \ge \frac{1}{2^{n-2}}.\] This is a contradiction. It follows that no very convex function exists.

See Also

2000 USAMO (ProblemsResources)
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. AMC logo.png