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.)

  • $\begingroup$ I dont think there is such a policy. Ask as much as you want. Also consider this: I have three numbers between 0 and 10. What is the biggest sum i can make? What is the smallest? $\endgroup$ – Jonathan Davidson Jul 9 '17 at 22:30
  • $\begingroup$ If the subset has no element then the minimum sum is $0$. The other extreme is the set having all the fourteen members in it $\{a_1,a_2, \ldots, a_{14}\}$, in which case each $a_i \leq 999 < 1000$, so the sum $\sum_{i=1}^{14} a_i < 14(1000)$. $\endgroup$ – Anurag A Jul 9 '17 at 22:31
  • $\begingroup$ Technically the upper limit for the sum will be $14\times 999 = 13986$, if that makes it any clearer. $\endgroup$ – Joffan Jul 9 '17 at 22:31
  • $\begingroup$ @AnuragA But since a subset contains unique entries, wouldn't $a_1$ through $a_{14}$ be different and not all necessarily $999$? Hope my question makes sense. $\endgroup$ – AleksandrH Jul 9 '17 at 22:35
  • $\begingroup$ MathJax hint: to get the multiply dot, you can use \cdot, so 14 \cdot 999 gives $14 \cdot 999$ $\endgroup$ – Ross Millikan Jul 9 '17 at 22:37

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$

  • $\begingroup$ So would the literal upper limit be 986 + 987 + 988 + 989 + 990 + 991 + 992 + 993 + 994 + 995 + 996 + 997 + 998 + 999 instead of $14 • 999$? I'm still slightly confused. $\endgroup$ – AleksandrH Jul 9 '17 at 22:34
  • $\begingroup$ That is correct. If those are the numbers, $\{986,999\}$ and $\{987,998\}$ have the same sum (along with other subsets) $\endgroup$ – Ross Millikan Jul 9 '17 at 22:35
  • $\begingroup$ Ah, okay. Is there anything that guarantees that the estimate of $14⋅999$ is a "safe" estimate--that is, that it will literally be greater than however many elements we're mapping to the set of sums? $\endgroup$ – AleksandrH Jul 9 '17 at 22:37
  • $\begingroup$ It is safe in being large enough because the sum can't get any larger. It is safe in being small enough for the argument to work because it is less than $16384$. $\endgroup$ – Ross Millikan Jul 9 '17 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.