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
Interesting, I actually talked with @queker a little about mod 5 since I had an exam question in my mind about mod5 that I could not solve back then: Why is for every x element N x4 mod 5 = 1 or x4 mod 5 = 0
Consider.
gcd(N, p) = 1 ⇒ NΦ(p) mod p = 1 by Euler's theorem
gcd(N, p) ≠ 1, N = pb ∙ a, pb ≡ 0 mod p ⇒ NΦ(p) mod p = 0
Hope this helps
I have another approach.
The numbers 1,5,9,11,21,25 are all odd. Odd + Odd is Even and Odd + Even is Odd. Adding three odd numbers is an odd sum.
Fifty is even so any subset of three numbers from that list can never be even or 50.
This actually mod 2 number theory. We call even numbers 0 and odd numbers one. Thats why 1+1+1 is 1 (mod 2)
Posted via D.Buzz