Let $s(k)$ be the number of ways to express $k$ as the sum of distinct $2012^{th}$ powers, where order does not matter. Show that for every real number $c$ there exists an integer $n$ such that $s(n)>cn$. Alex Zhu.
Problem
Source: ELMO Shortlist 2012, N3
Tags: number theory, Additive Number Theory, Extremal combinatorics, Perfect Powers
08.07.2012 21:18
28.10.2015 19:01
EDIT: Oops I didn't read the condition 'distinct' here. This solution can be used if repetition is allowed. There are $n^n$ ways to select $n$ numbers, with repetitions, out of $1^{2012}, 2^{2012}, \cdots, n^{2012}$. Each cases have no more than $n!$ permutations, so if order does not matter, there are $N \ge \frac{n^n}{n!}$ cases possible. Now denote the sums as $s_1, s_2, \cdots s_N$. Clearly, $s_i \le n^{2013}$. By the Pigeonhole Principle, there are at least $\frac{n^n}{n! \cdot n^{2013}}$ same numbers in $s_1, s_2 \cdots s_N$. Therefore, there exists a positive integer $k$, no more than $n^{2013}$ such that $s(k) \ge \frac{n^n}{n! \cdot n^{2013}}$. Claim: There is a positive integer $n$ large enough such that for a given $c$, $\frac{n^n}{n! \cdot n^{4026}} \ge c$. Proof: Trivial from Stirling's Approximation. Now we have that $s(k) \ge \frac{n^n}{n! \cdot n^{2013}} \ge c \cdot n^{2013} \ge ck$. $\blacksquare$
18.09.2021 11:29
Wrong.....
01.09.2023 14:09
Consider $S_n=\{1^{2012}, 2^{2012}, \dots, n^{2012}\}.$ The amount of numbers (counted with multiplicity) wich can be written as sum of some elements of $S_n$ is $2^{n}.$ But at the same time, all number that can be written as this sum is at most $1^{2012}+\cdots+n^{2012}<n^{2013}.$ But now notice that for any $c\in\mathbb{R}$ one can choose $n$ for which $2^n>>>cn^{2013},$ which solves the problem by $PHP.$