\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{COMC 2020/C4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 36}
\maketitle
\section*{Problem}
Let $S = \{4, 8, 9, 16, \dots\}$ be
the set of integers of the form $m^k$ for integers $m, k \ge 2$.
For a positive integer $n$, let $f(n)$ denote the
number of ways to write $n$ as the sum of
(one or more) distinct elements of $S$.
\begin{enumerate}[(a)]
\ii Prove that $f(30) = 0$.
\ii Show that $f(n) \ge 1$ for $n \ge 31$.
\ii Let $T$ be the set of integers $n$ for which $f(n) = 3$.
Prove that $T$ is finite and nonempty, and find $\max(T)$.
\end{enumerate}
\section*{Video}
\href{https://www.youtube.com/watch?v=8g21cEWiomg&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/8g21cEWiomg}}
\newpage
\section*{Solution}
We define $S'$ as $S$ with powers of $2$ removed, so that
\begin{align*}
S' &= \left\{ 9, 25, 36, 49, 81, 100, 121, 144, 169, 196, 225 \right\} \\
&\cup \left\{ 27, 125, 216, 343 \right\} \\
&\cup \left\{ 243, \dots \right\}
\end{align*}
The main idea is that every multiple of $4$
has a unique representation as a sum of powers of $2$ larger than $2$,
while no other number can be represented at all.
In other words:
\begin{claim*}
We have $f(n)$ is the number of ways
to write $n$ as the sum of distinct elements of $S$,
plus some multiple of $4$.
\end{claim*}
Part (a) is clear now.
For part (b), note that:
\begin{itemize}
\ii for $n \equiv 0 \pmod 4$, we vacuously have $f(n) > 0$;
\ii for $n \equiv 1 \pmod 4$,
we have $n-9 \equiv 0 \pmod 4$ so $f(n) > 0$ for $n \ge 9$;
\ii for $n \equiv 2 \pmod 4$,
we have $n-(9+25) \equiv 0 \pmod 4$ so $f(n) > 0$ for $n \ge 34$;
\ii for $n \equiv 3 \pmod 4$,
we have $n-27 \equiv 0 \pmod 4$ so $f(n) > 0$ for $n \ge 27$.
\end{itemize}
So this finishes part (b).
The proof of part (c) is similar but more annoying.
\begin{itemize}
\ii For $n \equiv 0 \bmod 4$:
all of $n$, $n-(9+27)$, $n-36$, $n-(25+27)$ are divisible by $4$,
so $f(n) > 3$ for $n \ge 52$.
\ii For $n \equiv 1 \bmod 4$:
all of $n-9$, $n-25$, $n-(9+36)$, $n-49$ are divisible by $4$;
so $f(n) > 3$ for $n \ge 49$.
\ii For $n \equiv 2 \bmod 4$:
all of $n-(9+25)$, $n-(9+49)$, $n-(9+25+36)$, $n-(25+49)$ are divisible by $4$;
so $f(n) > 3$ for $n \ge 74$.
\ii For $n \equiv 3 \bmod 4$:
all of $n-27$, $n-(27+36)$, $n-(9+25+49)$, $n-(9+25+81)$ are divisible by $4$;
so $f(n) > 3$ for $n \ge 115$.
\end{itemize}
On the other hand, one can check manually that $f(111) = 3$,
by exhaustively checking that there are no smaller combinations
of elements of $S'$ that add up to a $3 \pmod 4$ number less than $111$
(i.e.\ that $9+25+81=115$ really is the fourth smallest possible).
So $f(111) = 3$ follows and part (c) is completed.
\end{document}