\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{Shortlist 2008 C5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 8}
\maketitle
\section*{Problem}
Let $ S = \{x_1, x_2, \dots, x_{k + \ell}\}$
be a subset of $[0,1]$.
A $k$-element subset $A \subset S$ is called \emph{nice}
if
\[ \left \lvert\frac {1}{k}\sum_{x_i\in A} x_i
- \frac {1}{\ell}\sum_{x_j\in S\setminus A} x_j\right\rvert
\le \frac {k + \ell}{2k\ell}\]
Prove that the number of nice subsets is at least
$\frac{2}{k + \ell}\binom{k + \ell}{k}$.
\section*{Video}
\href{https://www.youtube.com/watch?v=ikvgjL-82tE&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/ikvgjL-82tE}}
\newpage
\section*{Solution}
We let $\Delta(A)$ denote the quantity
in the absolute value as a function of $A$.
Let $n = k+\ell$ for brevity.
Consider a random permutation $\pi$ of $\{1, 2, \dots, n\}$.
Look at the following $k+\ell$ sets, the ``cyclic shifts'':
\begin{align*}
A_1 &= \left\{ x_{\pi(1)}, x_{\pi(2)}, \dots, x_{\pi(k)} \right\} \\
A_2 &= \left\{ x_{\pi(2)}, x_{\pi(3)}, \dots, x_{\pi(k+1)} \right\} \\
A_3 &= \left\{ x_{\pi(3)}, x_{\pi(4)}, \dots, x_{\pi(k+2)} \right\} \\
&\vdotswithin{=} \\
A_{n-1} &= \left\{ x_{\pi(n-1)}, x_{\pi(n)}, \dots, x_{\pi(n-2)} \right\} \\
A_{n} &= \left\{ x_{\pi(n)}, x_{\pi(1)}, \dots, x_{\pi(n-1)} \right\}.
\end{align*}
We evidently have \[ \sum_1^{n} \Delta(A_i) = 0. \]
However, any two consecutive $\Delta(A_i)$
are going to differ by at most $\delta \defeq \frac 1k + \frac 1\ell$.
However we note that:
\begin{lemma*}
If we have (cyclic) sequence of $n \ge 2$ numbers with mean zero,
and whose consecutive terms differ by at most $\delta$,
then there will always be at least two numbers with absolute
value at most $\delta/2$.
\end{lemma*}
In other words, among these $n$ sets, there
must be at least two nice ones, regardless of $\pi$.
However, if $p$ is the fraction of $k$-element subsets which are nice,
then the expected number of nice sets is exactly $n \cdot p$.
So we conclude $p \ge \frac 2n$ as desired.
\end{document}