\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USA TST 2021/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 56}
\maketitle
\section*{Problem}
Find all functions $f \colon \RR \to \RR$ that satisfy the inequality
\[
f(y) -
\left(\frac{z-y}{z-x} f(x) + \frac{y-x}{z-x}f(z)\right) \leq
f\left(\frac{x+z}{2}\right) - \frac{f(x)+f(z)}{2}
\]
for all real numbers $x < y < z$.
\section*{Video}
\href{https://www.youtube.com/watch?v=J3cOwLGB2ZY}{\texttt{https://youtu.be/A3mS8QrYH6E}}
\newpage
\section*{Solution}
Answer: all functions of the form $f(y) = a y^2 + by + c$, where
$a, b, c$ are constants with $a \leq 0$.
If $I = (x,z)$ is an interval,
we say that a real number $\alpha$ is a
\emph{supergradient} of $f$ at $y \in I$
if we always have
\[ f(t) \le f(y) + \alpha(t-y) \]
for every $t \in I$.
(This inequality may be familiar as the so-called ``tangent line trick''.
A cartoon of this situation is drawn below for intuition.)
We will also say $\alpha$ is a supergradient of $f$ at $y$,
without reference to the interval,
if $\alpha$ is a supergradient of \emph{some} open interval containing $y$.
\begin{center}
\begin{asy}
size(4cm);
pair X = (0,0);
pair Z = (7,3);
pair Y = (3,4);
draw(X..Y..Z, blue);
pair t = 3*dir(X..Y..Z, 1);
draw( (Y-t)--(Y+t), red, Arrows);
label(rotate(15)*"slope $\alpha$", Y+0.45*t, dir(90), red );
dot("$x$", X, dir(-90), blue);
dot("$z$", Z, dir(-90), blue);
dot("$y$", Y, dir(90), blue);
\end{asy}
\qquad
\begin{asy}
size(5cm);
pair X = (-3,-9/3);
pair Z = (2,-4/3);
draw( X..(-2,-4/3)..(-1,-1/3)..(0,0)..(1,-1/3)..Z, blue );
pair Y = (-0.5,-0.25/3);
draw(X--Z, deepgreen);
draw((Y-1.5*dir(Z-X))--(Y+1.5*dir(Z-X)), red, Arrows );
label(rotate(18)*"slope $\frac{f(z)-f(x)}{z-x}$",
midpoint(X--Z), dir(110), deepgreen);
dot("$x$", X, dir(-90), blue);
dot("$y = \frac{x+z}{2}$", Y, 1.5*dir(-60), blue);
dot("$z$", Z, dir(-90), blue);
\end{asy}
\end{center}
\begin{claim*}
The problem condition is equivalent to asserting
that $\frac{f(z) - f(x)}{z-x}$ is a supergradient of $f$
at $\frac{x+z}{2}$ for the interval $(x,z)$, for every $x < z$.
\end{claim*}
\begin{proof}
This is just manipulation.
\end{proof}
At this point, we may readily verify that all claimed
quadratic functions $f(x) = ax^2+bx+c$ work --- these functions are concave,
so the graphs lie below the tangent line at any point.
Given $x < z$, the tangent at $\frac{x+z}{2}$ has slope
given by the derivative $f'(x)=2ax+b$, that is
\[ f'\left(\frac{x+z}{2}\right) = 2a \cdot \frac{x+z}{2} + b
= \frac{f(z)-f(x)}{z-x} \]
as claimed.
(Of course, it is also easy to verify the condition directly
by elementary means, since it is just a polynomial inequality.)
Now suppose $f$ satisfies the required condition; we prove that it has
the above form.
\begin{claim*}
The function $f$ is concave.
\end{claim*}
\begin{proof}
Choose any $\Delta > \max\{z-y,y-x\}$.
Since $f$ has a supergradient $\alpha$ at $y$ over the interval
$(y-\Delta,y+\Delta)$, and this interval includes $x$ and $z$, we have
\begin{align*}
\frac{z-y}{z-x}f(x) + \frac{y-x}{z-x}f(z) &\leq
\frac{z-y}{z-x}(f(y) + \alpha(x-y)) + \frac{y-x}{z-x}(f(y) +
\alpha(z-y)) \\
&= f(y).
\end{align*}
That is, $f$ is a concave function.
Continuity follows from the fact that any concave
function on $\RR$ is automatically continuous.
\end{proof}
\begin{lemma*}
[see e.g.\ {\url{https://math.stackexchange.com/a/615161}} for picture]
Any concave function $f$ on $\RR$ is continuous.
\end{lemma*}
\begin{proof}
Suppose we wish to prove continuity at $p \in \RR$.
Choose any real numbers $a$ and $b$ with $a < p < b$.
For any $0 < \eps < \max(b-p,p-a)$ we always have
\[ f(p) + \frac{f(b)-f(p)}{b-p} \eps \le f(p+\eps) \le f(p) + \frac{f(p)-f(a)}{p-a} \eps \]
which implies right continuity; the proof for left continuity is the same.
\end{proof}
\begin{claim*}
The function $f$ cannot have more than one supergradient
at any given point.
\end{claim*}
\begin{proof}
Fix $y \in \RR$.
For $t > 0$, let's define the function
\[ g(t) = \frac{f(y)-f(y-t)}{t} - \frac{f(y+t)-f(y)}{t}. \]
We contend that $g(\eps) \le \frac35g(3\eps)$
for any $\eps > 0$.
Indeed by the problem condition,
\noindent
\begin{minipage}{0.5\textwidth}
\begin{align*}
f(y) &\le f(y-\eps) + \frac{f(y+\eps)-f(y-3\eps)}{4} \\
f(y) &\le f(y+\eps) - \frac{f(y+3\eps)-f(y-\eps)}{4}.
\end{align*}
Summing gives the desired conclusion.
\end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{asy}
size(6cm);
real f(real x) { return -x*x/6; }
pair A = (-3, f(3));
pair B = (-2, f(2));
pair C = (-1, f(1));
pair D = (-0, f(0));
pair E = (1, f(1));
pair F = (2, f(2));
pair G = (3, f(3));
draw(A..B..C..D..E..F..G, blue);
draw(A--E, lightred);
draw(C--G, deepgreen);
draw( (C-2*dir(E-A))--(C+2*dir(E-A)), lightred, Arrows );
draw( (E-2*dir(G-C))--(E+2*dir(G-C)), deepgreen, Arrows );
dot("$y-3\varepsilon$", A, dir(-90), blue);
dot("$y-\varepsilon$", C, dir(-90), blue);
dot("$y$", D, dir(-90), blue);
dot("$y+\varepsilon$", E, dir(-90), blue);
dot("$y+3\varepsilon$", G, dir(-90), blue);
\end{asy}
\end{minipage}
Now suppose that $f$ has two supergradients $\alpha < \alpha'$ at point $y$.
For small enough $\eps$, we should have
we have $f(y-\eps) \leq f(y) - \alpha'\eps$
and $f(y+\eps) \leq f(y) + \alpha\eps$, hence
\[ g(\eps) = \frac{f(y)-f(y-\eps)}{\eps} - \frac{f(y+\eps)-f(y)}{\eps}
\geq \alpha' - \alpha. \]
This is impossible since $g(\eps)$ may be arbitrarily small.
\end{proof}
\begin{claim*}
The function $f$ is quadratic on the rational numbers.
\end{claim*}
\begin{proof}
Consider any four-term arithmetic progression $x, x+d, x+2d, x+3d$.
Because $(f(x+2d)-f(x+d))/d$ and $(f(x+3d)-f(x))/3d$ are both
supergradients of $f$ at the point $x+3d/2$, they must be equal, hence
\begin{equation} \label{quadratic}
f(x+3d) - 3f(x+2d) + 3f(x+d) - f(x) = 0.
\end{equation}
If we fix $d = 1/n$, it follows inductively
that $f$ agrees with a quadratic function $\wt f_n$ on the set $\frac1n \ZZ$.
On the other hand, for any $m \neq n$,
we apparently have $\wt f_n = \wt f_{mn} = \wt f_m$,
so the quadratic functions on each ``layer'' are all equal.
\end{proof}
Since $f$ is continuous, it follows $f$ is quadratic, as needed.
\begin{remark*}
[Alternate finish using differentiability due to Michael Ren]
In the proof of the main claim (about uniqueness of supergradients),
we can actually notice the two terms $\frac{f(y)-f(y-t)}{t}$
and $\frac{f(y+t)-f(y)}{t}$ in the definition of $g(t)$ are both monotonic
(by concavity).
Since we supplied a proof that $\lim_{t \to 0} g(t) = 0$,
we find $f$ is differentiable.
Now, if the derivative at some point exists,
it must coincide with all the supergradients;
(informally, this is why ``tangent line trick'' always has the slope
as the derivative, and formally, we use the mean value theorem).
In other words, we must have
\[ f(x+y) - f(x-y) = 2f'(x) \cdot y \]
holds for all real numbers $x$ and $y$.
By choosing $y=1$ we obtain that $f'(x) = f(x+1) - f(x-1)$
which means $f'$ is also continuous.
Finally differentiating both sides with respect to $y$ gives
\[ f'(x+y) - f'(x-y) = 2f'(x) \]
which means $f'$ obeys Jensen's functional equation.
Since $f'$ is continuous, this means $f'$ is linear.
Thus $f$ is quadratic, as needed.
\end{remark*}
\end{document}