Let $A$ be a set of six positive integers each of which is less
than $15$. Show that there must be two distinct subsets of $A$ whose elements when added up give the same sum.
This is what I've tried so far.
There are $2 ^ 6 = 64$ subsets of $A$. We can also calculate the largest possible sum of a subset to be $14+13+12+11+10+9 = 69$. The smallest possible sum for a subset is $0$. Thus, there are $70$ possible sums, but only $63$ possible subsets $($assuming we exclude the empty set$)$. Is there something I am missing so that I can apply the pigeonhole principle?
Best Answer
You're on the right track, but are indeed missing a few small things.
First, note that you can only get that highest possible sum of $69$ if $A =\{ 9,10,11,12,13,14 \}$. But any non-empty subset of that set has a sum of at least $9$, meaning that for any non-empty subset of this particular set, the sum of its members is at least $9$, and at most $69$, meaning that there are only $61$ possible sums for this subset, rather than $69$. Hence, the pigeonhole principle can be applied to this particular set.
OK, but how can we be sure the pigeonhole principle can be applied to any set $A$?
Well, note that the key observation we made regarding the specific set above was that the difference between the highest sum and lowest sum of non-empty subsets was $60$, and that was because that set contained the numbers $10$ through $14$. And now note that for any set, this difference between the highest and lowest set can never be greater than that, and is for most sets smaller than that.
So, we can say that for any set $A$, there are at most $61$ possible sums for the non-empty subsets of $A$, but there are $63$ non-empty subsets of $A$. So yes, the pigeonhole principle can be applied to any set $A$ to show that there must always be two subsets with the same sum.