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 3×3 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 (15)

  1. Sid says:

    1 8 7

    4 5 2

    —–

    6 3 9

    Mostly by trial and error 😉

  2. Korn1699 says:

    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.

  3. Stuart Dootson says:

    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?

  4. JC says:

    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.

  5. David Srbecky says:

    129

    438

    567

  6. Bill Mill says:

    Simple enough. A generator for all solutions:

    def n(a, b, c):

       #turn 1,2,3 into 123

       return (100*a) + (10*b) + 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:])

  7. Arjuna says:

    hmmm…. 336 solutions. Did you do it by hand?

  8. serge says:

    254

    637

    891

  9. kaley says:

    so what IS the answer? I couldnt solve it!

  10. David Srbecky says:

    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 🙂

  11. v says:

    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. ]

  12. mihailik says:

    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.

  13. PsA says:

    317

    628

    945

  14. David Gustafson says:

    Is this what you meant?

    127

    +368

    495

    This took me about 60 seconds.

  15. Here are answers + commentary to the number puzzle I posted yesterday, which was, fill in the digits: