Elemental Subset Sum Problem

Math Problem: Use 3 numbers to sum to 50: 1,5,9,11,21,25.

You could try every possible unordered pair and check whether that and one of the remaining numbers sums to 50. That methodology requires you to get 15 pairs and try them all.

My approach is this: Take various small prime numbers as a modulous and reformulate the values as residues.

For example, take the modulus of the numbers of 5. The addends are 1, 0, 4, 1, 0 (mod 5). In order to Sum to zero with three of these numbers. You must take one that is 4,1,0. So your solution set has to be a subset of the triples {(1,9,5), (11,9,5), (1,9,25), (11,9,25)}. This set is really small and it is easy to see there is no solution.

However if you use mod 2, you can see addends are all odd. And you can not add to an even number. They all have a modulus of 1. And because 1+1+1 = 1 (mod 2) and 50 = 0 (mod 2), there cannot be a solution. The subset of the previous mentioned set is the empty set.

QED.

Had it been a much larger set of numbers, perhaps combining various moduloses might be a good way to determine quickly the solution set. I looked around breifly on the Internet for this particular solution and I just didn't find it. That's not to say someone never did. It is possible I just got lucky and this methodology is unlikely to bear a solution.

Posted using STEMGeeks