Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 3)
(→‎Solution 3)
Line 35: Line 35:
 
=== Solution 3 ===
 
=== Solution 3 ===
  
−
The softmax function can be expressed as
+
We consider the function
−
<cmath>\text{softmax}_\tau(x,y)=\frac{xe^{x/\tau}+ye^{y/\tau}}{e^{x/\tau}+e^{y/\tau}}.</cmath> As we take <math>\tau\rightarrow 0^+</math>, observe that this converges and is strictly bounded above by <cmath>\text{max}(x,y)=\frac{x+y}{2}+\frac{|x-y|}{2}<\frac{x+y}{2}+|x-y|</cmath> so such a function does not exist.  
+
<cmath>
 +
f(x, y) = \frac{x + y}{2} + |x - y|,
 +
</cmath>
 +
defined on <math>\mathbb{R}^2</math>. Define the graph of <math>f</math> as the manifold
 +
<cmath>
 +
\mathcal{M} = \{ (x, y, z) \in \mathbb{R}^3 : z = f(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>.
  
−
We also have a geometric argument. The graph of softmax function is a symmetric one-to-one function with two mirrored tails reflected across the <math>x=y</math> plane (think same behavior like <math>xy=1</math> 45 degree rotated hyperbola). Bringing those tails closer together would mean the that the graph is no longer an invertible function, being both not one-to-one yet symmetric—a contradiction (think a 45 degree rotated hyperbola with acute axes). In fact this geometry is known as a non-functional manifold with a kink (non-differentiable) at <math>x=y</math>. In 3D, this would be
+
Proof:
 +
We first observe that <math>f</math> is symmetric:
 
<cmath>
 
<cmath>
−
f(x, y) =
+
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}
 
\begin{cases}
−
\frac{3x - y}{2}, & \text{if } x \ge y \\
+
\left( \frac{3}{2}, -\frac{1}{2} \right), & x > y, \\
−
\frac{3y - x}{2}, & \text{if } y > x
+
\left( -\frac{1}{2}, \frac{3}{2} \right), & x < y.
−
\end{cases},
+
\end{cases}
−
</cmath> and the angle between the major axes is the same as the angle between the 3 and 5 of a 3-4-5 triangle. The reason we use the softmax function and take the temperature as it goes close to 0 is because the max function has the kink that makes its manifold not functional at <math>x=y</math>.
+
</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>
 +
\boxed{\text{Therefore, } \mathcal{M} \text{ is a non-functional manifold.}} \quad \blacksquare
 +
</cmath>
  
  

Revision as of 03:31, 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

We consider the function \[f(x, y) = \frac{x + y}{2} + |x - y|,\] defined on $\mathbb{R}^2$. Define the graph of $f$ as the manifold \[\mathcal{M} = \{ (x, y, z) \in \mathbb{R}^3 : z = f(x, y) \}.\]

Claim: The manifold $\mathcal{M}$ is not the graph of a function $\mathbb{R} \to \mathbb{R}^2$, i.e., it cannot be inverted to express $(x, y)$ as a function of $z$.

Proof: We first observe that $f$ is symmetric: \[f(x, y) = f(y, x),\] and convex, as it is the sum of a linear function and the convex function $|x - y|$.

Consider the behavior of $f$ along the line $x = y$. For $x > y$, we have \[f(x, y) = \frac{x + y}{2} + (x - y) = \frac{3x - y}{2},\] while for $x < y$, we have \[f(x, y) = \frac{x + y}{2} + (y - x) = \frac{3y - x}{2}.\] The partial derivatives with respect to $x$ and $y$ do not match along $x = y$, creating a non-differentiable crease. Specifically, \[\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}\] At $x = y$, the gradient does not exist; the directional derivatives have a jump discontinuity, forming a kink along the line $x = y$.

Suppose for contradiction that $\mathcal{M}$ is the graph of a function $g: \mathbb{R} \to \mathbb{R}^2$ such that $g(z) = (x, y)$ with $f(x, y) = z$. Then each level set \[L_z = \{ (x, y) \in \mathbb{R}^2 : f(x, y) = z \}\] must be the image of a unique point $g(z) \in \mathbb{R}^2$.

However, since $f(x, y) = f(y, x)$, the level sets are symmetric across the line $x = y$. Furthermore, near any $z$ for which the level set intersects the kink $x = y$, the gradient directions from either side differ, and the level set contains multiple points mapping to the same height $z$. Therefore, the preimage $f^{-1}(z)$ contains at least two distinct points, violating the definition of a function $z \mapsto (x, y)$.

Hence, $\mathcal{M}$ cannot be the graph of a function $\mathbb{R} \to \mathbb{R}^2$. The surface folds along the kink, failing the vertical line test in the direction of $z$.

\[\boxed{\text{Therefore, } \mathcal{M} \text{ is a non-functional manifold.}} \quad \blacksquare\]


~Lopkiloinm

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_USAMO_Problems/Problem_1&oldid=252902"