\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}