Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
