Number puzzle

Here's a little number puzzle quiz.

Fill in the digits:

   ABC
+DEF
GHI

Where each letter represents a unique digit between 1 and 9, such that all digits are used exactly once.

OR (and this is where it gets interesting...) prove that it's impossible to fill in such digits. (And, "it's too hard" is not a proof that it's impossible)

I came up with this morning while teaching my 2 year old daughter her digits 1 through 9. (No, she didn't solve it). I was writing the digits 1,2,3,4,5,6,7,8,9 in a 3x3 matrix for her and thought it would be cute if the first row plus the second row added to the third row.

I'll leave comments moderated here to prevent folks from giving away the answer. [Update:] I'm getting lots of great responses here and I'm itching to unmoderate the comments. soon...  [Update:] I've published the comments and written a followup post.

Comments

• Anonymous
  June 12, 2007
  1 8 7 4 5 2

6 3 9 Mostly by trial and error ;)

• Anonymous
  June 12, 2007
  That problem is impossible with the numbers 1 though 9 because that set includes 5 odd numbers and 4 even numbers.  The only possible combinations are: E    E    O E    O    O

• OR - OR -   (Where O is odd and E is even) E    O    E Since ALL the numbers must be used and only once, there is no solution that could exist with using exactly 5 odd numbers.

• Anonymous
  June 12, 2007
  Well...this just cries out for a little program. In Haskell: perms [] = [[]] perms xs = [ x : ps | x <- xs , ps <- perms ( xs[x]) ] get3 :: String -> (Int, Int, Int) get3 s = (read a :: Int, read b :: Int, read c :: Int)   where      a = take 3 s      b = take 3 (drop 3 s)      c = take 3 (drop 6 s) get3 :: String -> Bool isSum s = a+b == c   where      (a,b,c) = get3 s uniqueSums :: String -> [String] uniqueSums = filter isSum (perms "123456789") Evaluate 'uniqueSums "123456789"' to get the list of solution strings. There's loads of solutions (336, to be precise). Just to make sure I haven't got the wrong end of the stick, here's an example: "546273819" => 546 + 273 = 819 Uses each digit once, the third triple is the sum of the first two?

• Anonymous
  June 12, 2007

1. A+D = G
2. B+E = H
3. C+F = I A+D+G+B+E+H+C+F+I = 1+2+3+...+9 = 45 Applying 1,2,3) 2G+2H+2I = 45 G+H+I = 45/2 = 22.5 This cannot be because G,H,I are integers, therefore its sum have to be an integer.

• Anonymous
  June 12, 2007
  129 438 567

• Anonymous
  June 12, 2007
  Simple enough. A generator for all solutions: def n(a, b, c):    #turn 1,2,3 into 123    return (100a) + (10b) + c def is_solution(perm):    if n(*perm[:3]) + n(*perm[3:6]) == n(*perm[6:]): return True    return False #requires probstat http://probstat.sourceforge.net/ from probstat import Permutation for perm in Permutation(range(1,10)):    if is_solution(perm):        print n(*perm[:3]), n(*perm[3:6]), n(*perm[6:])

• Anonymous
  June 12, 2007
  hmmm.... 336 solutions. Did you do it by hand?

• Anonymous
  June 12, 2007
  254 637 891

• Anonymous
  June 12, 2007
  so what IS the answer? I couldnt solve it!

• Anonymous
  June 12, 2007
  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.  Whoever approached this by brute force, let me know the exact number. David PS:  This is what you get for asking a nice math question just after the exams. :-) PPS:  In other news, over the summer I will be working on MonoDevelop debugger as we as SharpDevelop debugger.  (Part of GsoC)  How cool is that :-)

• Anonymous
  June 12, 2007
  I'm too lazy for math analysis, so this small code will generate all results (1728 - I hope those are all and only all...): for (int x = 0; x < 1000; x++) {    for (int y = 0; y < 1000; y++) {        // sum numbers        int z = x + y;        string v = String.Format("{0:000}{1:000}{2:000}", x, y, z);        // check if each digit is different        if (v.Length != 9) { continue; }        bool[] vFound = new bool[10];        bool found = true;        foreach (char vChar in v) {            int num = Convert.ToInt32(vChar) - 48;            if (vFound[num]) {                found = false;                break;            }            vFound[num] = true;        }        if (found) { Console.WriteLine(v); }    } }
  [Mike: this includes the 0 digit (only 1...9 allowed), which is why you're probably getting 1728 instead of only 36. ]

• Anonymous
  June 12, 2007
  int totalCount = 0; for( int i = 111; i < 999; i++ ) { for( int j = 111; j < 999; j++ ) { int m = i + j; if( m > 999 || m<111 ) continue; char[] allDigitsArray = string.Concat(i,j,m).ToCharArray(); Array.Sort(allDigitsArray); string requiredDigits = "123456789"; string allDigits = new string(allDigitsArray); if( requiredDigits==allDigits ) { totalCount++; Console.WriteLine(i + " + " + j + " = " + m); } } } Console.WriteLine("Total " + totalCount + " found."); Total 336 found.

• Anonymous
  June 12, 2007
  317 628

945

• Anonymous
  June 13, 2007
  Is this what you meant? 127 +368

495 This took me about 60 seconds.

• Anonymous
  June 13, 2007
  Here are answers + commentary to the number puzzle I posted yesterday, which was, fill in the digits: