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

\begin{document}
\title{USAMO 2020/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 16}
\maketitle

\section*{Problem}
Let $n \geq 2$ be an integer.
Let $x_1 \ge x_2 \ge \dots \ge x_n$
and $y_1 \ge y_2 \ge \dots \ge y_n$ be $2n$ real numbers
such that
\begin{align*}
  0 &= x_1 + x_2 + \dots + x_n = y_1 + y_2 + \dots + y_n, \\
  \text{and}\quad
  1 &= x_1^2 + x_2^2 + \dots + x_n^2 = y_1^2 + y_2^2 + \dots + y_n^2.
\end{align*}
Prove that
\[ \sum_{i=1}^n (x_i y_i - x_i y_{n+1-i})
  \geq \frac{2}{\sqrt{n-1}}.  \]

\section*{Video}
\href{https://www.youtube.com/watch?v=r7j0oRtpErA&t=6165}{\texttt{https://youtu.be/r7j0oRtpErA}}

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

\newpage

\section*{Solution}
We present two approaches.
In both approaches, it's helpful motivation that
for even $n$, equality occurs at
\begin{align*}
  (x_i) &= \Big(
    \underbrace{\frac{1}{\sqrt n}, \dots, \frac{1}{\sqrt n}}_{n/2},
    \underbrace{-\frac{1}{\sqrt n}, \dots, -\frac{1}{\sqrt n}}_{n/2} \Big) \\
  (y_i) &= \Big( \frac{n-1}{\sqrt{n(n-1)}},
      \underbrace{- \frac{1}{\sqrt{n(n-1)}},
      \dots,
      - \frac{1}{\sqrt{n(n-1)}}}_{n-1} \Big)
\end{align*}

\paragraph{First approach (expected value).}
For a permutation $\sigma$ on $\{1, 2, \dots, n\}$ we define
\[ S_\sigma = \sum_{i=1}^n x_i y_{\sigma(i)}. \]

\begin{claim*}
  For random permutations $\sigma$,
  $\mathbb E[S_\sigma] = 0$
  and $\mathbb E[S_\sigma^2] = \frac{1}{n-1}$.
\end{claim*}
\begin{proof}
  The first one is clear.

  Since $\sum_{i < j} 2x_i x_j = -1$,
  it follows that (for fixed $i$ and $j$),
  $\mathbb E[y_{\sigma(i)} y_{\sigma(j)}] = -\frac{1}{n(n-1)}$,
  Thus
  \begin{align*}
    \sum_{i} x_i^2 \cdot \mathbb E \left[ y_{\sigma(i)}^2 \right]
      &= \frac 1n \\
    2\sum_{i < j} x_i x_j \cdot \mathbb E \left[
      y_{\sigma(i)} y_{\sigma(j)}
      \right] &= (-1) \cdot \frac{1}{n(n-1)}
  \end{align*}
  the conclusion follows.
\end{proof}

%\begin{claim*}
%  For two independent random permutations $\sigma$ and $\tau$,
%  \[ \mathbb E \left[ \left( S_\sigma - S_\tau \right)^2
%    \right] = \frac{2}{n-1}.  \]
%\end{claim*}
%\begin{proof}
%  Since
%  \[ \mathbb E[S_\sigma S_\tau]
%    = \sum_i \sum_{i'} x_i x_{i'}
%      \mathbb E \left[ y_{\sigma(i)} \right]
%      \mathbb E \left[ y_{\tau(i')} \right] = 0 \]
%  the conclusion follows.
%\end{proof}

\begin{claim*}
  [A random variable in {$[0,1]$} has variance at most $1/4$]
  If $A$ is a random variable with mean $\mu$
  taking values in the closed interval $[m, M]$ then
  \[ \mathbb E[(A-\mu)^2] \le \frac14 (M-m)^2. \]
\end{claim*}
\begin{proof}
  By shifting and scaling, we may assume $m = 0$ and $M = 1$,
  so $A \in [0,1]$ and hence $A^2 \le A$.
  Then
  \[
    \mathbb E[(A-\mu)^2]
    = \mathbb E[A^2] - \mu^2
    \le \mathbb E[A] - \mu^2 = \mu-\mu^2 \le \frac14.
  \]
  This concludes the proof.
\end{proof}
Thus the previous two claims together give
\[ \max_\sigma S_\sigma - \min_\sigma S_\sigma
  \ge \sqrt{\frac{4}{n-1}} = \frac{2}{\sqrt{n-1}}.
\]
But $\sum_i x_i y_i = \max_\sigma S_\sigma$
and $\sum_i x_i y_{n+1-i} = \min_\sigma S_\sigma$
by rearrangement inequality
and therefore we are done.

\paragraph{Outline of second approach (by convexity, due to Alex Zhai).}
We will instead prove a converse result: given the hypotheses
\begin{itemize}
  \ii $x_1 \ge \dots \ge x_n$
  \ii $y_1 \ge \dots \ge y_n$
  \ii $\sum_i x_i = \sum_i y_i = 0$
  \ii $\sum_i x_i y_i - \sum_i x_i y_{n+1-i} = \frac{2}{\sqrt{n-1}}$
\end{itemize}
we will prove that $\sum x_i^2 \sum y_i^2 \le 1$.

Fix the choice of $y$'s.
We see that we are trying to maximize a convex function in $n$
variables $(x_1, \dots, x_n)$ over a convex domain
(actually the intersection of two planes with several half planes).
So a maximum can only happen at the boundaries:
when at most two of the $x$'s are different.

An analogous argument applies to $y$.
In this way we find that it suffices to consider situations
where $x_\bullet$ takes on at most two different values.
The same argument applies to $y_\bullet$.

At this point the problem can be checked directly.

\end{document}
