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

Latest revision as of 03:48, 30 June 2025

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.

Solution 3

Define the symmetric average $F(x, y) = \frac{f(x) + f(y)}{2}.$ Then the inequality becomes $F(x, y) \ge f\left( \frac{x + y}{2} \right) + |x - y|.$

Because $|x - y|$ is not differentiable along the line $x = y$ , the surface defined by $F(x, y)$ must have a permanent kink along the diagonal. A kink is a sharp crease where the surface fails to have a well-defined tangent plane.

If f were a true function on $\mathbb{R}$ satisfying the inequality at all scales, then this kink would have to persist no matter how closely x and y are chosen. That means the graph of F never becomes smooth near the diagonal.

But every differentiable real-valued function f produces a smooth symmetric average F. Therefore, the presence of a permanent kink contradicts the assumption that f is differentiable at any scale. The kink cannot be removed by local smoothing.

Hence, the geometric shape of the inequality forces a kink that no function f can produce, so no function can be very convex.

~Lopkiloinm

@@ Line 35: / Line 35: @@
 === Solution 3 ===
-We consider the function
+Define the symmetric average
 <cmath>
-f(x, y) = \frac{x + y}{2} + |x - y|,
+F(x, y) = \frac{f(x) + f(y)}{2}.
 </cmath>
-defined on <math>\mathbb{R}^2</math>. Define the graph of <math>f</math> as the manifold
+Then the inequality becomes
 <cmath>
-\mathcal{M} = \{ (x, y, z) \in \mathbb{R}^3 : z = f(x, y) \}.
+F(x, y) \ge f\left( \frac{x + y}{2} \right) + |x - y|.
 </cmath>
-Claim: The manifold <math>\mathcal{M}</math> is not the graph of a function <math>\mathbb{R} \to \mathbb{R}^2</math>, i.e., it cannot be inverted to express <math>(x, y)</math> as a function of <math>z</math>.
+Because <math>|x - y|</math> is not differentiable along the line <math>x = y</math>, the surface defined by <math>F(x, y)</math> must have a permanent kink along the diagonal. A kink is a sharp crease where the surface fails to have a well-defined tangent plane.
-Proof:
+If f were a true function on <math>\mathbb{R}</math> satisfying the inequality at all scales, then this kink would have to persist no matter how closely x and y are chosen. That means the graph of F never becomes smooth near the diagonal.
-We first observe that <math>f</math> is symmetric:
-<cmath>
-f(x, y) = f(y, x),
-</cmath>
-and convex, as it is the sum of a linear function and the convex function <math>|x - y|</math>.
-Consider the behavior of <math>f</math> along the line <math>x = y</math>. For <math>x > y</math>, we have
-<cmath>
-f(x, y) = \frac{x + y}{2} + (x - y) = \frac{3x - y}{2},
-</cmath>
-while for <math>x < y</math>, we have
-<cmath>
-f(x, y) = \frac{x + y}{2} + (y - x) = \frac{3y - x}{2}.
-</cmath>
-The partial derivatives with respect to <math>x</math> and <math>y</math> do not match along <math>x = y</math>, creating a non-differentiable crease. Specifically,
-<cmath>
-\nabla f(x, y) =
-\begin{cases}
-\left( \frac{3}{2}, -\frac{1}{2} \right), & x > y, \\
-\left( -\frac{1}{2}, \frac{3}{2} \right), & x < y.
-\end{cases}
-</cmath>
-At <math>x = y</math>, the gradient does not exist; the directional derivatives have a jump discontinuity, forming a kink along the line <math>x = y</math>.
-Suppose for contradiction that <math>\mathcal{M}</math> is the graph of a function <math>g: \mathbb{R} \to \mathbb{R}^2</math> such that <math>g(z) = (x, y)</math> with <math>f(x, y) = z</math>. Then each level set
-<cmath>
-L_z = \{ (x, y) \in \mathbb{R}^2 : f(x, y) = z \}
-</cmath>
-must be the image of a unique point <math>g(z) \in \mathbb{R}^2</math>.
-However, since <math>f(x, y) = f(y, x)</math>, the level sets are symmetric across the line <math>x = y</math>. Furthermore, near any <math>z</math> for which the level set intersects the kink <math>x = y</math>, the gradient directions from either side differ, and the level set contains multiple points mapping to the same height <math>z</math>. Therefore, the preimage <math>f^{-1}(z)</math> contains at least two distinct points, violating the definition of a function <math>z \mapsto (x, y)</math>.
-Hence, <math>\mathcal{M}</math> cannot be the graph of a function <math>\mathbb{R} \to \mathbb{R}^2</math>. The surface folds along the kink, failing the vertical line test in the direction of <math>z</math>.
-<cmath>
+But every differentiable real-valued function f produces a smooth symmetric average F. Therefore, the presence of a permanent kink contradicts the assumption that f is differentiable at any scale. The kink cannot be removed by local smoothing.
-\boxed{\text{Therefore, } \mathcal{M} \text{ is a non-functional manifold.}} \quad \blacksquare
-</cmath>
+Hence, the geometric shape of the inequality forces a kink that no function f can produce, so no function can be very convex.
 ~Lopkiloinm

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

Page

Toolbox

Search