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

## 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 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 there exists no very convex function.