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

\begin{document}
\title{USAMO 1996/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 77}
\maketitle

\section*{Problem}
For any nonempty set $S$ of real numbers,
let $\sigma(S)$ denote the sum of the elements of $S$.
Given a set $A$ of $n$ positive integers,
consider the collection of all distinct sums $\sigma(S)$ as $S$ ranges
over the nonempty subsets of $A$.
Prove that this collection of sums can be
partitioned into $n$ classes so that in each class,
the ratio of the largest sum to the smallest sum does not exceed $2$.

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

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

\newpage

\section*{Solution}
By induction on $n$ with $n=1$ being easy.

For the inductive step, assume
\[ A = \left\{ a_1 > a_2 > \dots > a_n \right\}. \]
Fix any index $k$ with the property that
\[ a_k > \frac{\sigma(A)}{2^k} \]
(which must exist since $\half+\frac14+\dots+\frac{1}{2^k} < 1$).
Then
\begin{itemize}
  \ii We make $k$ classes for the sums between $\frac{\sigma(A)}{2^k}$
  and $\sigma(A)$; this handles every set
  which has any element in $\{a_1, \dots, a_k\}$.
  \ii We make $n-k$ classes via induction hypothesis
  on $\{a_{k+1}, \dots, a_n\}$.
\end{itemize}
This solves the problem.

\end{document}
