A conjecture on a Subset Power Sum Problem motivated by Computer Science Let $X=\{x_{1}, \cdots , x_{n}\}$ be a set of $n$ positive integers and integer $i \ge 1$. Let’s say that the set $X$ is $i$-sum-avoiding if for any nonnegative integers $c_{1}, \cdots, c_{n}$ such that $\sum_{j=1}^{n}c_{j} = n$ and $(c_{1},\cdots, c_{n}) \ne (1,\cdots, 1)$, it holds that
$\displaystyle \sum_{j=1}^{n}c_{j}x_{j}^{i} \ne \displaystyle \sum_{j=1}^{n}x_{j}^{i}$
Let $f(n,i)$ be the minimum value for a given $i \ge 1$ such that there exists an $i$-sum-avoiding set $X$ consisting of $n$ positive integers at most $f(n,i)$. Does there exist a constant $k_{i}$ for every $i$ such that $\forall n \in \mathbb N$, it holds $f(n,i) \le n^{k_{i}}$? If it does, what is the minimum of such $k_{i}$ for every $i$?
Showing such a set would help solve hard problems in computer science given some space relaxations. It seems that the hardness of such problems is directly related to non-existence of such sets. I could only show such sets when $k=n$ that is $k$ is not a constant. My example for $X$ is $X = \{n^{1}, n^{2},\cdots, n^{n}\}$.
$\underline{Conjecture}$: $k_{i} = \infty$ $\forall i \ge 1$.
 A: Here is what I think proves that for any i, there is no constant ki satisfying f(n,i)≤nki.  That is:
Claim.  Let i be a positive integer.  Then the function f(n,i) is not polynomially bounded in n.
Proof.  First consider the case of i=1.  A key observation is that if X={x1,…,xn} contains two subsets A and B such that |A|=|B|, A≠B, and the sum of A is equal to the sum of B, then X cannot be 1-sum-avoiding since assigning cj as follows violates the condition: cj=2 if xj belongs to A but not to B, cj=0 if xj belongs to B but not to A, and cj=1 if neither holds.
Let m be a positive integer and X be a 1-sum-avoiding set of size 2m.  By the above observation, all m-element subsets of X must have distinct sums, and therefore the largest sum must be at least $\binom{2m}{m}$.  Therefore, the largest element in X must be at least $\binom{2m}{m}/m>2^{m-1}$, which implies that f(2m,1) > 2m−1.  This establishes the claim for i=1.
Now observe that if a set X={x1,…,xn} is i-sum-avoiding, then the set {x1i,…,xni} is 1-sum-avoiding.  This means that f(n,1) ≤ f(n,i)i.  Since we already know that f(n,1) is not polynomially bounded, f(n,i) is not polynomially bounded in n, either.  QED.
A: I still find the statement of the problem very confusing. For $i=1$, you want your set $X$ to be a non-averaging set, that is, a set containing no three distinct elements $a,b,c$ such that $a+b=2c$. You want more than that, but that's a start, and there's enough literature on non-averaging sets to give you some kind of lower bound on $k$. 
Tsuyoshi Ito posted an answer while I was typing mine, you'll see we're thinking along similar lines. 
EDIT: There are several sections of Guy's Unsolved Problems In Number Theory that discuss problems not exactly what you want but not a million miles removed, either, and some of the references given there may be useful. Problem C8 is sets with distinct sums of subsets, C11 is three-subsets with distinct sums, C14 is maximal sum-free sets, C16 is nonaveraging sets. 
A: Take $x_j=2^{i-1}$. I claim that if $\sum_{j=1}^n c_j 2^{j-1} = \sum_{j=1}^n 2^{j-1}$ with $\sum_{j=1}^n c_j\leq n$, then $c_j=1$ for all $j$. The case $n=1$ is easy. In general note that $c_1$ is odd. We substract 1 on both sides of the equation and divide by 2, replace $c_2$ by $c_2+\frac{c_1-1}{2}$, and finally shift all indices by 1. Then we obtain an equation of the same form as before for a smaller value of $n$, and are done by induction. The same argument shows that $\{1, 2, 4, 8, \ldots\}$ is $i$-sum avoiding for every $i$, however, for larger $i$ there should be more efficient choices.
