Test your observation!
Probability
Level
4
Given a set S , how many sub-sets of S are there such that the sum of the numbers within the sub-set is less than or equal to 76? (An empty sub-set counts as one).
The answer is 65536.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Note that the sum of all of the numbers in the set is 2 1 7 ( 1 7 + 1 ) = 1 7 × 9 = 1 5 3 . Then 1 5 3 − 7 6 = 7 7 , so for any set, exactly it or its complement has sum less than or equal to 76. Hence, exactly half of the subsets have sum less than or equal to 76.
Since, for any subset, either each number is in the set or out of the set, there are 2 1 7 possible subsets. Half of that is 2 1 6 = 6 5 5 3 6