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

\begin{document}
\title{Shortlist 2012 C2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 1}
\maketitle

\section*{Problem}
Let $n \ge 1$ be an integer.
What is the maximum number of possible disjoint pairs
of elements of the set $\{1, 2, \dots, n\}$
such that the sums of the pairs are different integers
not exceeding $n$?



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

\newpage

\section*{Solution}
The answer is $N = N(n) \le \left\lfloor \frac{2n-1}{5} \right\rfloor$.
The proof is nearly identical to that of IMO SL 2009 C2.

To prove the bound, suppose the pairs
are $(a_1, b_1)$, \dots, $(a_N, b_N)$.
Then on the one hand
\[ \sum_1^N (a_i + b_i) \le
  \underbrace{n + \dots + (n-N+1)}_{\text{$N$ largest sums } < n}
  = \half N\left( 2n - N + 1 \right). \]
On the other hand,
\[ \sum_1^N (a_i + b_i)
  \ge \underbrace{1 + 2 + \dots + 2N}_{\text{$2N$ smallest possible entries}}
  = N \cdot (2N+1) \]
Putting these two bounds together and solving works.

For the construction,
it suffices to exhibit the construction
when $n \equiv 1 \pmod 5$ and $n \equiv 3 \pmod 5$,
since for all other $n$ we have $N(n) = N(n-1)$.
We just give examples which generalize readily.
\begin{itemize}
  \ii When $n=18$, we use the following:
  \[ \begin{array}{cccc|ccc}
      1 & 2 & 3 & 4 & 5 & 6 & 7 \\
      +&+&+&+&+&+&+ \\
      14 & 12 & 10 & 8 & 13 & 11 & 9
    \end{array} \]
  The general construction for $n=5k+3$ is analogous,
  using $(k+1)+k=2k+1$ pairs.
  \ii When $n=21$, we use the following:
  \[ \begin{array}{ccc|ccccc}
    1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
    +&+&+&+&+&+&+&+ \\
    14 & 12 & 10 & 17 & 15 & 13 & 11 & 9
  \end{array} \]
  The general construction for $n=5k+1$ is analogous,
  using $(k-1)+(k+1) = 2k$ pairs.
\end{itemize}

\end{document}
