What is the largest size of a subset $A$ of the integers $\{1,\dots,n\}$ such that no two non-identical subsets of $A$ have the same sum?

You can always take the integer powers of $2$ (1,2,4,8, etc.) giving $|A| = \lfloor \log_2{n} \rfloor + 1$. Can you do much better?


1 Answer 1


A simple pigeonhole principle argument shows that you can't do much better than $|A|=\log_2(n)$.

A set $A$ of cardinality $k$ has $2^k$ subsets whose sums all lie in a range between $1$ and $kn$. Thus, if $2^k > kn$ then there are 2 subsets with an equal sum. In particular, if $k\geq \log_2(n) + \log_2(\log_2(n)) + 1$ then $$ 2^k = 2 n \log_2(n) > (\log_2(n) + \log_2(\log_2(n)) + 1)n = kn . $$

However, you can do a little better. For example, the set $\{3,5,6,7\} \subseteq [7]$ has the desired property, and it has $4$ elements, more than $3=\lfloor\log_2(7)\rfloor+1$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .