Difference between revisions of "2000 USAMO Problems/Problem 1"
Lopkiloinm (talk | contribs) (→Solution 3) |
Lopkiloinm (talk | contribs) (→Solution 3) |
||
Line 38: | Line 38: | ||
<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>\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. | ||
− | 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 | + | 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 |
+ | <cmath> | ||
+ | f(x, y) = | ||
+ | \begin{cases} | ||
+ | \frac{3x - y}{2}, & \text{if } x \ge y \\ | ||
+ | \frac{3y - x}{2}, & \text{if } y > x | ||
+ | \end{cases} | ||
+ | </cmath> | ||
+ | |||
~Lopkiloinm | ~Lopkiloinm |
Revision as of 03:01, 30 June 2025
Problem
Call a real-valued function very convex if
holds for all real numbers and
. Prove that no very convex function exists.
Solution
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,
A straightforward induction shows that:
for all nonnegative integers
Using a similar line of reasoning as above,
Therefore, for every nonnegative integer
Now, we choose
large enough such that
This is always possible because
and
are fixed for any particular function
It follows that:
However, by the very convex condition,
This is a contradiction. It follows that no very convex function exists.
Solution 3
The softmax function can be expressed as
As we take
, observe that this converges and is strictly bounded above by
so such a function does not exist.
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 plane (think same behavior like
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
. In 3D, this would be
~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.