being in 'information technology' industry has a lot of drawbacks. biggest of them all is you start thinking in terms of loops and variables.
as soon as someone tell you to find a solution for a math puzzle, i would say, easy - do this do that and you have the solution. but actually coming up with a valid reason for the solution mathematically is way tougher then the program.
i read a puzzle (http://blogs.msdn.com/jmstall/default.aspx)
ABC
+DEF
----
GHI
Where each letter represents a unique digit between 1 and 9, such that all digits are used exactly once.
Now for once you can write a program which will solve this
iterate through two loop for x and y from 1 to 999
number x and y should not have common digits
find x and y whos sum(s) is another 3 digit number
number x, y and s should not have common digits
x,y,s is a solution
if you can write a program; can you explain the mathematic logic?
i have a detailed explanation on the blog by a person named DAVID
Explanation
Let x = A+B+C+D+E+F and y = G+H+I
Note that x + y = 1+2+3+4+5+6+7+8+9 = 45
Hence x + y = 45 and y = 45 - x
If there is no overflow then x = y, so x = 45 - x => x = 22.5 => impossible
If there is one overflow then x - 10 + 1 = y (10 lost on one digit, 1 gained on other digit), that is x = y + 9
Therefore x = y + 9 = 45 - x + 9 = 54 - x => 2x = 54 => x = 27 => eventually possible
If there are two overflows then by same argument x = y + 2*9 => ... => impossible
Hence there is exactly one overflow
Now note that we can without loss of generality assume that:
A < D
B < E
C < F
A + D < 10
B + E < 10
C + F > 10 (overflows)
Hence if we have one solution, we can produce 16 other by swapping pars A-D, B-E, C-F and by moving the first column to the back - that is:
BCA
EFD
HIG
Also observe that under these constraints:
G = A + D
H = B + E + 1
I = C + F - 10
Now, consider possible triplets (C,F,I): (under the constraint C < F and C + F > 10)
2 9 1;
3 9 2; 3 8 1
4 9 3; 4 8 2; 4 7 1
5 9 4; 5 8 3; 5 7 2; 5 6 1
6 9 5; 6 8 4; 6 7 3
7 9 6; 7 8 5
8 9 7;
Consider triplet (2,9,1):
Numbers 1,2,9 are taken so 3,4,5,6,7,8 is left for A,D,G, B,E,H which are related by
G = A + D
H = B + E + 1
Thus G + H = A + B + D + E + 1
left hand side <= 7 + 8
left hand side <= 15
right hand side >= 3 + 4 + 5 + 6 + 1
right hand side >= 19
so there can not be equality and there can not be solution for triple (2,9,1)
Similarly we eliminate triples (3,9,2) and (3,8,1).
Other tripes have a solution. For example consider (4,9,3):
Numbers 4,9,3 are taken. Numbers 1,2,5,6,7,8 are left.
G = A + D
H = B + E + 1
7 = 1 + 6
8 = 2 + 5 + 1
(or
7 = 2 + 5
8 = 1 + 6 + 1
)
So this yields solutions:
124
659
783
and
214
569
783
In conclusion, we have 13 possible triplets for (C,F,I), each should yields at least one solution and each solution can be permutated 16 times. Thus, we have at least 208 solutions.
lesson leart
start reasoning and minimize solving
