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.
Problem
Source: ELMO Shortlist 2010, C2
Tags: combinatorics proposed, combinatorics
02.09.2017 17:35
Any solution?
02.09.2017 18:25
Clearly the function $f(y) = \dfrac{2^y-1}{(y+1)^{4022}}$ goes to infinity and strictly increasing for sufficiently large $y$. Choose an integer $N_0$ such that $f(M) >x$ for all $M\ge N_0$ and let $N = 1^{2010}+2^{2010}+...+N_0^{2010}$. I claim this choice for $N$ works. Indeed, choose any $n>N$. We'll write $n = 1^{2010}+2^{2010}+...+m^{2010}+c$ where $m\ge N_0$ is as large as possible and $c$ is some nonnegative integer. Then clearly every non-empty subset of $\{1^{2010}, 2^{2010}, ... m^{2010}\}$ has a sum which is a positive integer less than or equal to $n$. There are $2^m-1$ such sums, hence $\dfrac{\text{max}_{1\le i\le n} s(i)}{n} \ge \dfrac{s(1)+s(2)+...+s(n)}{n^2} \ge \dfrac{2^m-1}{n^2}$, which by our representation of $n$ is at least $\dfrac{2^m-1}{(1^{2010}+2^{2010}+...+(m+1)^{2010}-1 )^2} > \dfrac{2^m-1}{ ((m+1)^{2010} + (m+1)^{2010} + ... + (m+1)^{2010})^2 } = \dfrac{2^m-1}{(m+1)^{4022}}=f(m) >x$, and we're done.
02.09.2017 18:45
I chose $N=N_0^{2011}$ instead. Of course it doesn't make any difference.