\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{Shortlist 1995 N8}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 38}
\maketitle

\section*{Problem}
Let $ p$ be an odd prime.
Determine positive integers $x$ and $y$ for which $x \le y$
and $\sqrt{2p} - \sqrt{x} - \sqrt{y}$
is non-negative and as small as possible.

\section*{Video}
\href{https://www.youtube.com/watch?v=ePkZIVu9YJs&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/ePkZIVu9YJs}}

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

\newpage

\section*{Solution}
We claim the best case is if $x = \frac{p-1}{2}$
and $y = \frac{p+1}{2}$.
The fact that $\sqrt x + \sqrt y \le \sqrt{2p}$ follows by Jensen.
Moreover, it is best possible among choices with $x+y=p$ by Karamata,
and hence is also better than any choice with $x+y < p$
(since $(x,y)$ will be worse than $(x,p-y)$).

We are left to show that we cannot have
\[ \sqrt{\frac{p-1}{2}} + \sqrt{\frac{p+1}{2}} < \sqrt x + \sqrt y <
  \sqrt{2p} \]
for positive integers $x$ and $y$ satisfying $x+y > p$.
Let $z = x+y$ and $t = x-y$.
\begin{claim*}
  [Calculation]
  Let $A = z + \sqrt{z^2-t^2}$. Then we have $A < 2p < A + \frac 1A$.
\end{claim*}
\begin{proof}
  Square both sides:
  \begin{align*}
    \sqrt{\frac{p-1}{2}} + \sqrt{\frac{p+1}{2}} &< \sqrt x + \sqrt y < \sqrt{2p} \\
    \sqrt{p^2-1} + p &< x+y + 2\sqrt{xy} < 2p \\
    \sqrt{p^2-1} &< x+y-p + 2\sqrt{xy} < p.
  \end{align*}
  which simplifies to
  \[ p^2-1 < (x+y-p)^2 + 4xy + 4(x+y-p)\sqrt{xy} < p^2. \]
  Let $z = x+y$ and $t=x-y$.
  Simplify further:
  \begin{align*}
    p^2-1 &< (z-p)^2 + (z^2-t^2) + 2(z-p)\sqrt{z^2-t^2} < p^2 \\
    \iff t^2-1 &< 2(z-p)\left[ z + \sqrt{z^2-t^2} \right] < t^2 \\
    \iff (1-t^{-2})(z-\sqrt{z^2-t^2}) &< 2(z-p) < z-\sqrt{z^2-t^2} \\
    \iff z + \sqrt{z^2-t^2} &< 2p < z + \sqrt{z^2-t^2}
        + \frac{1}{z + \sqrt{z^2-t^2}}.
  \end{align*}
  Hence done.
\end{proof}

The idea from here is that ``square roots don't approximate integers too well''.
We formalize this using the following lemma.
\begin{lemma*}
  Let $n \ge 2$ be an integer which is not a perfect square.
  Then $n - \sqrt{n^2-1} > \frac{1}{2n}$.
\end{lemma*}
\begin{proof}
  Write $n - \sqrt{n^2-1} = \frac{1}{n + \sqrt{n^2-1}}$.
\end{proof}
Assume for contradiction $A$ really exists with
\[ A < 2p < A + \frac 1A \] and $z > p$.
If $A$ is an integer, we have a contradiction.
Else, since $z \ge p+1$ it follows that the fractional part of $A$ satisfies
\[ 1 - \frac{1}{2(2p-z)} \overset{\text{lemma}}{\ge}
  \{\sqrt{z^2-t^2}\} = \{A\} > 1 - \frac 1A \]
hence
\[ A < 2(2p-z) \le 2\left[ 2p-(p+1) \right] = 2p-2 \]
which is a contradiction.

\end{document}
