High school contest math question (number theory) - prove: Reposting with Mathjax - sorry, first time!
Let $S = \{4,8,9,16,...\}$ 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$.
For example, $f(5) = 0$ since there are no ways to express 5 in this fashion, and $f(17) = 1$ since $17 = 8+9$ is the only way to express 17.
(a) Prove that $f(30) = 0$
(b) Show that $f(n) \ge 1$ for $n \ge 31$.
(c) Let $T$ be the set of integers for which $f(n) = 3$. Prove that $T$ is finite and non-empty, and find the largest element of $T$.
I think that part a) is relatively easy to just check since none of the values in the first few values of the set $S = \{4,8,9,16,25,27,32,64,...\}$ will add to get to 30.
I'm not sure where to start with part b and part c. For part b, I was working at finding sums for each number but figured this was not an intelligent way to proceed. For part c) I'm not sure where to start at all.
Thanks for any help you can give.
 A: For part b, note that all multiples of $4$ can be represented because you have all the powers of $2$ except $1,2$.  Express any multiple of $4$ in binary and read off the numbers to add to get it.  All numbers equivalent to $1 \bmod 4$ that are at least $9$ can be expressed because the number minus $9$ is a multiple of $4$ and therefore expressible.  All numbers equivalent to $2 \bmod 4$ that are $34$ or greater are expressible because $34=9+25$.  All numbers equivalent to $3 \bmod 4$ that are $27$ or greater because we have $27$ available.  Therefore the greatest number that cannot be expressed is $30$.
For c, numbers that are large enough will have too many representations.  We will do each residue class $\mod 4$ in turn.
For $0 \bmod 4$ we have $\emptyset,36, 9+27, 25+27$ as ways to express numbers without any of the $2^n$ terms.  We can therefore express any number $52$ or greater in $4$ or more ways.
For $1 \bmod 4$ we have $9, 25, 9+36, 49$ so we can express any number $49$ or greater in $4$ or more ways.
For $2 \bmod 4$ we have $9+25, 9+49, 9+36+49, 25+49$ so we can express any number $74$ or greater in $4$ or more ways.
For $3 \bmod 4$ we have $27, 27+36, 9+25+49, 9+25+36+49$ so we can express any number $119$ or greater in $4$ or more ways.
The greatest number in $T$ is $115$, which can be expressed as $64+27+16+8, 36+32+27+16+4, 49+32+25+9$ but in no other ways.
