\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/J3cOwLGB2ZY}}

\section*{External Link}
\url{https://aops.com/community/p20672681}

\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}
