0

How many distinct subsets of the set $S=\{1,8,9,39,52,91\}$ have three-digit sums?

I know we have $64$ total subsets, but I don't think that helps us in this question ... does it?

Gerry Myerson
  • 179,216
WolverineA03
  • 277
  • 1
    You can calculate the number of subsets with sum less than 100 (i.e. not three digit sum) and subtract from 64. – Rishi Apr 23 '18 at 12:13
  • Since there are only 64 cases to check, it's doable on pen and paper. But if there were much more numbers, the problem becomes more interesting! – Matti P. Apr 23 '18 at 12:17
  • 1
    There are 32 subsets containing 91, and they all work, with three exceptions. Subsets not containing 91 must contain both 52 and 39, and then you can work out the possibilities for the other elements to make the sum have 3 digits. – Gerry Myerson Apr 23 '18 at 12:58

1 Answers1

0

The rationale behind the selection is ${91,52,39,9,(8,1)} = {a1,a2,a3,a4,a5}$ The way I have grouped from the second element to the last element (i.e from a2 to a5) when added alone or a combination thereof will have a distinct set with sum >=100. The number of ways are $4\left({3\choose1}+{3\choose2}+{3\choose3}\right)+1 = 29$. Further${(52,39),9,(8,1)} = {b1,b2,b3}$. The way I have grouped the second element to the last element(i.e from b2 to b3) when added alone or a combination thereof will have a distinct set with sum >=100. The number of such sets is $2\left({2\choose1}\right)+1=5$. Thus the total number of distinct sets where the sum of their elements is a three digit = $34$

Satish Ramanathan
  • 11,984