Problem: Let $m, n$ be positive integers with $m > 1$.
Anastasia partitions the integers $1, 2, \dots , 2m$ into $m$ pairs.
Boris then chooses one integer from each pair
and finds the sum of these chosen integers.
Prove that Anastasia can select the pairs
so that Boris cannot make his sum equal to $n$.

Solution: Overall the idea is to try find a few constructions which eliminate most of the cases,
then clean out the last few ones leftover.
% (It's like using reavers on zerglings:
% knock out 90\% of the lings with a couple scarabs
% and then have the zealots finish the rest.)

\begin{itemize}
  \ii If $n \notin [m^2, m^2+m]$, then use the construction
  \[
  \begin{array}{ccccc}
    1 & 3 & \dots & 2m-3 & 2m-1 \\
    2 & 4 & \dots & 2m-2 & 2m
  \end{array}
  \]

  \ii If $n \not\equiv 1 + 2 + \dots + m = \half m(m+1) \pmod m$, use the construction
  \[
  \begin{array}{ccccc}
    1 & 2 & \dots & m-1 & m \\
    m+1 & m+2 & \dots & 2m-1 & 2m
  \end{array}
  \]
\end{itemize}
Henceforth, assume $m \ge 4$ (smaller cases can be dispensed with by hand).
\begin{itemize}
  \ii Assume $m$ is odd, and either $n = m^2$ and $n = m^2 + m$.
  Use the construction
  \[
    \begin{array}{ccccc}
      1 & 2 & \dots & m-1 & m \\
      m+2 & m+3 & \dots & 2m & m+1
    \end{array}.
  \]
  The possible values of this modulo $m+1$ are
  \[ \tfrac 12 m(m+1) + \{0,1\} \equiv \tfrac12(m+1) + \{0,1\} \pmod{m+1} \]
  since $m$ is odd.
  But $m^2$ and $m^2+m$ leave residues $1$ and $2$ modulo $m$, done.

  \ii Assume $m$ is even (so $m+1$ is odd), and $n = m^2 + \half m \equiv \half \pmod{m+1}$.
  The same pairing as before has possible residues
  \[ \tfrac 12m (m+1) + \{0,1\} \equiv \{0,1\} \pmod{m+1}. \]
  This completes the proof.
\end{itemize}