S be a set of 6 positive integers whose max is most at 14. How to show that all subset of S cannot be distinct?

Question

ı can show that by pigeonhole princible but ım confused.Is it true for 5 integers? what numbers are these? 1 to 14

Answer 1

Not a full solution, but hints for how to think about the problem:

If the maximal number you could choose were 16, every subset sum could be distinct for 5 numbers. But, with the max 14, only with four numbers or less will you find every subset sum is distinct.

In general, to maximize the number of subset sums, you will want powers of 2. This is because $2^n -1 = \sum_{k=0}^{n-1} 2^k$. There is no way to use single copies of a lesser power of 2 to add to a greater power of 2, so powers of 2 are optimal for avoiding duplicate sums.

If the max is 14, a set of 4 positive integers producing all distinct subset sums would be $\{1,2,4,8\}$ (this is not the only one, of course). But notice that 1,2,4,8 can be used to create every subset sum from 0 to 15. There is no number that is "missing". So, suppose we remove one of these numbers to create missing subset sums (the goal being we want to remove one number and add two). Can you show that is not possible?

You can represent your five chosen numbers as $\{a,a+b_1,a+b_2,a+b_3,a+b_4\}$ with $b_1,b_2,b_3,b_4$ a set of four positive integers. Since 1,2,4,8 maximize the number of subset sums, we have $\{a,a+1,a+2,a+4,a+8\}$. We can have $a$ be any number from 1 to 6. If there were a solution with five positive integers, this is my guess at a configuration.

$$\{6,7,8,10,14\}$$

$6+8=14$

$$\{5,6,7,9,13\}$$

$6+7=13$

$$\{4,5,6,8,12\}$$

$4+8=12$

$$\{3,4,5,7,11\}$$

$4+7=11$

$$\{2,3,4,6,10\}$$

$4+6=10$

$$\{1,2,3,5,9\}$$

$1+2=3$

So, I highly doubt there is a set of five positive integers that would satisfy this problem.