I got this problem from the book Mathematical Puzzles, A Connoisseurs Collection and thought about it in the shower.
Prove that given any 10 distinct numbers between 1 and 100 it is always possible to find two different non-overlapping subsets that have the same sum.
Here is my solution.
The least a subset can add up to is 0 and the greatest is 91 + 92 +... +100 = 955. The pair of subsets we want to prove exist can't have these values but that doesn't matter.
Imagine we have 956 buckets labelled 0 - 955.
0 1 2 ... 955 🪣 🪣 🪣 ... 🪣
Form each of the possible subsets of our 10 numbers, work out its sum, then put that subset in the bucket labelled with the corresponding number. For example the subset {1, 2} goes in the bucket labelled 3.
How may possible subsets are there? For any subset of our 10 numbers a given number is either in that subset or not, so we have 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 210 = 1024 possible subsets.
But 1024 is bigger than the number of buckets, which is only 996. Therefore at least on bucket contains two or more subsets, which must have the same sum.
This pair of subsets are different but might overlap, if so remove the numbers they have in common. This cannot empty either or both of the sets because if it did it would mean they were the same, or had different sums, and neither of those things is true.
Hence we have proved a pair of subsets with equals sums must always exist.
Maths Problem - Sums of Subsets
I got this problem from the book Mathematical Puzzles, A Connoisseurs Collection and thought about it in the shower.
Prove that given any 10 distinct numbers between 1 and 100 it is always possible to find two different non-overlapping subsets that have the same sum.
Here is my solution.
The least a subset can add up to is 0 and the greatest is 91 + 92 +... +100 = 955. The pair of subsets we want to prove exist can't have these values but that doesn't matter.
Imagine we have 956 buckets labelled 0 - 955.
0 1 2 ... 955
🪣 🪣 🪣 ... 🪣
Form each of the possible subsets of our 10 numbers, work out its sum, then put that subset in the bucket labelled with the corresponding number. For example the subset {1, 2} goes in the bucket labelled 3.
How may possible subsets are there? For any subset of our 10 numbers a given number is either in that subset or not, so we have 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 = 210 = 1024 possible subsets.
But 1024 is bigger than the number of buckets, which is only 996. Therefore at least on bucket contains two or more subsets, which must have the same sum.
This pair of subsets are different but might overlap, if so remove the numbers they have in common. This cannot empty either or both of the sets because if it did it would mean they were the same, or had different sums, and neither of those things is true.
Hence we have proved a pair of subsets with equals sums must always exist.