I'm trying to understand the solution to this problem in my text:
There are $14$ $3$-digit numbers in a list. Can you conclude that there are two distinct subsets of the $14$ numbers that have the same sum?
I actually didn't know how to approach this from scratch, so I had to look up the solution:
Yes. There are $2^{14}$ = $16384$ subsets. Since each number lies in the range from $0$ through $999$ and there are at most $14$ numbers in a subset, the sum of any subset of the numbers will be in the range from $0$ through $14·1000$. Thus, there are at most $14001$ possible values for the sum of a subset of the numbers. Since $16384$ > $14001$, if each subset is mapped to the value of its sum, then there must be at least two different subsets that are mapped on to the same value. Therefore, there are at least two different subsets whose numbers sum to the same value.
Okay, so I understand the premise: by the pigeonhole principle, this will be true if the number of possible subsets is larger than the number of possible sums, as that would guarantee that your function mapping subsets to sums is not one-to-one and that at least two of them have the same sum.
Here's what I don't quite understand, and I'd really appreciate a clear breakdown:
Since each number lies in the range from $0$ through $999$
So far so good.
and there are at most $14$ numbers in a subset
Okay, makes sense: you could take a subset to be all the numbers.
the sum of any subset of the numbers will be in the range from $0$ through $14·1000$
And here's where they lost me. If I understand why this is true, I will understand the solution. But at the moment, it's not entirely clear to me why we can deduce that the sums will range from $0$ through $14•1000$.
(Aside: I don't know if there's any policy on this site for submitting lots of questions within a single day…but I really do appreciate the help.)
Best Answer
If each number is at most $999$ the sum of $14$ of them is at most $14 \cdot 999$. Since the numbers are different, the maximum sum is a bit lower, but this is good enough. Similarly, one subset has no members and has its sum zero. Any subset that has at least one member sums to at least $100$, but again we don't need the fact that the sum cannot be in the range $1-99$