4
$\begingroup$

I have a set of integers $S = \{a_1,a_2,\ldots,a_n\}$. Let $K = a_1+a_2+\ldots+a_n$.

Consider the space of all $n$-tuples whose values are taken from the set $S$. For example $(a_1,a_2,\ldots,a_n)$ is one $n$-tuple and its sum is $K$, $(a_1,a_1,a_2,a_2,\ldots,a_k)$ is another. I need $S$ such that the only $n$-tuple that sums to $K$ among the space of all $n$-tuples is $(a_1,a_2,\ldots,a_n)$.

An example that wont work is, if $S = \{1,4,7\}$, $K = 12 (= 1+4+7)$. $\{1,4,7\}$ and $\{4,4,4\}$ both sum to $12$. Similarly if we take $S = \{1,2,3,4,5,6,7\}$, I can think of 2 $7$-tuples that add to $28$.

I tried the set $S = \{1, 2, 4, 8, \ldots, 2^n\}$ and it seems to work. Can anyone give me an example that is polynomial instead of exponential in $n$. Would the set $S = \{1, 4, 9, 16, \ldots, n^2\}$ or $\{1, 8, 27,\ldots,n^3\}$ work? Thanks for the comments and suggestions.

$\endgroup$
  • $\begingroup$ I didn't understand the question $\endgroup$ – Amr Dec 29 '13 at 22:37
  • $\begingroup$ @Amr More formally: Does there exist a polynomial $f\in\mathbb Z[X]$ such that for all finite sequences $(a_i)_{i=1}^n$ with $a_i\in\mathbb N_0$ and $\sum_{i=1}^n a_i=n$ and $\sum_{i=1}^n a_if(i)=\sum_{i=1}^n f(i)$, it follows that $a_1=\ldots=a_n=1$? $\endgroup$ – Hagen von Eitzen Dec 29 '13 at 22:48
  • $\begingroup$ Instead of $n$-tuple you probably mean multiset. For $n>1$, reordering an $n$-tuple gives a different $n$-tuple with the same sum! $\endgroup$ – Hagen von Eitzen Dec 29 '13 at 22:49
  • $\begingroup$ I don't understand why $S = \{1,2,4,\dots,2^n\}$ has the desired property. Why is $(1,...,1)$ of length $2^{n+1}-1$ not a counter-example as it has sum $K$? $\endgroup$ – benh Dec 29 '13 at 22:50
  • 1
    $\begingroup$ @benh You are required to take exactly $n$ summands. $\endgroup$ – Hagen von Eitzen Dec 29 '13 at 23:14
3
$\begingroup$

The set of squares will not work in general. Any notrivial solution to $a^2+b^2=c^2+d^2$ allows us to drop $a^2$ and $b^2$ and instead have $c^2$ and $d^2$ twice. And such solutions are easy to find since the equation is equivalent to $(a-d)(a+d)=a^2-d^2=c^2-b^2=(c-b)(c+b)$. For example $1\cdot 15 = 3\cdot 5$, which leads to $a=8, b=1, c=4, d=7$. Indeed, $8^2+1^2=65=4^2+7^2$. There is also the smaller solution $5^2+5^2=1^2+7^2$. Thus already $S=\{1,4,9,16,25,36,49\}$ does not have the desired property. And this reminds us of Ramanujan and Hardy's taxi: $1729 = 10^3+9^3=12^3+1^3$. So the set $S=\{1,8,27,\ldots, 12^3\}$ of cubes won't work either.

Here's why exponential growth is necessary: Let $S=\{a_1,\ldots, a_n\}$. There are $2^n$ subsets of $\{1,\ldots, n\}$ be a "good" set. If $A,B\subseteq\{1,\ldots, n\}$ are distict subsets of the same size $k$ and with $\sum_{i\in A}a_i=\sum_{i\in B}a_i$, the set $S$ is "bad" as this allows us to replace summands coming from $A$ in $a_1+\ldots +a_n$ with summands coming from $B$. Since $\sum_{i\in A}a_i$ is between $0$ and $ka_n$ and there are $n\choose k$ subsets of size $k$, we conclude that $ka_n\ge {n\choose k}$. If we pick $k=\lfloor n/2\rfloor$, then using Stirling's approximation we see that ${n\choose k}\approx\frac{2^n\sqrt {2}}{\sqrt{\pi n}}$ and obtain $$ a_n\gtrsim\frac{2^{n+1}\sqrt 2}{n\sqrt{\pi n}}.$$

$\endgroup$
  • $\begingroup$ took me a while to figure out the last step where you conclude that K*An >= (n k), but i think in understand. thanks a lot! $\endgroup$ – abe Dec 31 '13 at 17:51
  • $\begingroup$ took me a while to figure out the last step where you conclude that KAn >= nCk, but i think in understand. correct me if i am wrong but if KAn < nCk, by the pigeonhole principle, there exist atleast 2 sets of size K with the same sum, which is bad. So as long as K*An >= nCk we are guaranteed a good set. did i get this right? thanks a lot! $\endgroup$ – abe Dec 31 '13 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.