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

\begin{document}
\title{Shortlist 2000 N6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 58}
\maketitle

\section*{Problem}
Show that the set of positive integers that
cannot be represented as a sum of distinct perfect squares is finite.

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

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

\newpage

\section*{Solution}
Say a number is ``good'' if it satisfies the property.
We start with the following base cases:
\begin{claim*}
  Every $1 \bmod 4$ number from $37$ to $133$ is good,
  and in fact can be written using squares at most $121$.
\end{claim*}
\begin{proof}
  We only need to check numbers which have a $3 \bmod 4$
  prime factor with odd multiplicity, by Christmas theorem.
  This is easy:
  \begin{align*}
    57 &= 6^2 + 4^2 + 2^2 + 1^2 \\
    69 &= 8^2 + 2^2 + 1^2 \\
    77 &= 8^2 + 3^2 + 2^2 \\
    93 &= 8^2 + 5^2 + 2^2 \\
    105 &= 10^2 + 2^2 + 1^2 \\
    129 &= 10^2 + 5^2 + 2^2 \\
    133 &= 8^2 + 7^2 + 4^2 + 2^2.
    \qedhere
  \end{align*}
\end{proof}

Then, the following corollaries take place:
\begin{itemize}
  \ii Every $1 \bmod 4$ number from $37$ to $97$ can be written
    with squares at most $81$.

  \ii By adding $10^2 = 100$, to the previous bullet,
    in tandem with the claim itself,
    every $1 \bmod 4$ number from $37$ to $197$ can be written
    with squares in the set $\{1^2,2^2, \dots, 11^2\}$.

  \ii By adding $12^2 = 144$ to the previous bullet,
    every $1 \bmod 4$ number from $37$ to $331$ can be written
    with squares in the set $\{1^2,2^2, \dots, 11^2, 12^2\}$.

  \ii By adding $14^2 = 196$ to the previous bullet,
    every $1 \bmod 4$ number from $37$ to $527$ can be written
    with squares in the set $\{1^2,2^2, \dots, 11^2, 12^2, 14^2\}$.

  \ii \dots and so on.
\end{itemize}

In this way, every sufficiently large $1 \bmod 4$ number
may be written as the sum of distinct squares
from the set
\[ \{1^2, 2^2, \dots, 11^2 \} \cup \{12^2, 14^2, 16^2, 18^2 \dots\}. \]

Then a general sufficiently large number
may be reduced to this case by subtracting $13^2$, $15^2$, $17^2$ if
necessary to reduce it to a $1 \bmod 4$ number.

\end{document}
