Problem

Source: ELMO Shortlist 2010, C2

Tags: combinatorics proposed, combinatorics



For a positive integer $n$, let $s(n)$ be the number of ways that $n$ can be written as the sum of strictly increasing perfect $2010^{\text{th}}$ powers. For instance, $s(2) = 0$ and $s(1^{2010} + 2^{2010}) = 1$. Show that for every real number $x$, there exists an integer $N$ such that for all $n > N$, \[\frac{\max_{1 \leq i \leq n} s(i)}{n} > x.\] Alex Zhu.