Answer to Number puzzle

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

   ABC
+DEF
GHI

 

OR prove it's impossible.

 

I originally moderated the answers but have now gone back and published them all. My conclusion is that the folks who read this blog are way smarter than I am.

So it is indeed possible, and the general consensus from comments is that there are 336 solutions. 

 

Solutions generally fell into 3 categories:

1. Adhoc.
   Brute force manually experiment to find a success case. I only had a baby-scribble pad available at the time, which works for scribbling a few numbers, but is impractical for writing more complex mathematical rigorous stuff. Hence I pursued an adhoc solution and found (218+439=657). For the record, I had a solution before I posted the question :). Lots of folks posted other random adhoc solutions.
2. Mathematical rigor.
   Use more fancy math + number theory to get results. David Srbecky had a great demonstration of this in his comment.
3. Computer searches.
   This sort of question screams for an automated search. I believe you only need to check (9 pick 6 = 60480)  possible inputs, which is a very easily searched space. A few folks posted code snippets to do the search.  Folks posted C# (1, 2), Python, Haskell solutions.  It's easy enough that the C# snippet ran within seconds, and they weren't even optimized.

 

 

Proving it's impossible?

One interesting catch is that you need a carry bit (2 digits that add to over 10). In my case, (218+439 = 657), that was the 8+9=17. You can easily prove that you need a carry-bit with simple number theory (such as by inspecting even + odds). There are 5 odd numbers in 1...9 and 4 even numbers. The carry bit gives you an extra odd number (a one) in the mix. (See Korn1699's comment for further explanation). Once I noticed that, I used it to prune the search space in my adhoc search.  

This sort of thing is another cute example of "impossible" vs. "insufficiently clever". If you forget about carry bits and just look at the numbers straight up, you can easily come up with a flawed proof that this is impossible.

Comments

• Anonymous
  June 13, 2007
  PingBack from http://blogs.msdn.com/jmstall/archive/2007/06/12/number-puzzle.aspx

• Anonymous
  June 13, 2007
  The comment has been removed

• Anonymous
  June 13, 2007
  This was my verbose solution:    class Program    {        static void Main(string[] args)        {            for (int one = 123; one <= 987; one++)                for (int two = 123; two <= 987; two++)                {                    int three = one + two;                    if (three > 987)                        continue;                    for (int digit = 1; digit <= 9; digit++)                        if (!HasDigit(one, digit) && !HasDigit(two, digit) && !HasDigit(three, digit))                            goto keep_checking;                    Answer(one, two, three);                keep_checking:;                }        }        static bool HasDigit(int value, int digit)        {            if (value % 10 == digit) return true;            if ((value % 100 - value % 10) / 10 == digit) return true;            if ((value % 1000 - value % 100) / 100 == digit) return true;            return false;        }        static void Answer(int one, int two, int three)        {            Console.WriteLine(" {0}n+{1}n-----n {2}n", one, two, three);        }    }

• Anonymous
  June 19, 2007
  Here a similar example program in the funtional/logic language Mercury. http://www.cs.mu.oz.au/research/mercury/tutorial/book/book.pdf  Page 19