A Math Problem

Problem: use ten digits 0, 1, 2, ..., 9 to form a summation expression abc+def=xghi, where each letter represents one digit (an example solution is 876 + 429 = 1305). It is straightforward to figure out x=1, but the rest is still hard for adults. As a problem for third graders, it should really had some digits prefilled.

The following is a strategy for adults:

Let us consider the simplest case without carry:

(1) c+f=i,

(2) b+e=h,

(3) a+d=10+g.

Sum the three equations and obtain:

(4) a+b+c+d+e+f=10+g+h+i.

With a+b+c+d+e+f+g+h+i=0+2+3+4+5+6+7+8+9=44, we obtain

(5) g+h+i = 17.

Zero cannot be a or d (the first digit of a number cannot be zero); zero cannot be c, otherwise f=i ; similarly zero cannot be f, b or e. Zero cannot be i or h (no carry), therefore g=0. The only possible case for the set {g, h} is {8, 9} due the requirement in (5). At this point, it is not hard to find a solution, e.g., 752+346=1098.

Follow the similar strategy, one may consider another scenario with carry:

(6) c+f=10+i,

(7) b+e+1=10+h,

(8) a+d+1=10+g.

By summing them, we obtain

(9) g+h+i=8.

There are only two possibilities for the set {g, h, i}, i.e., either {0, 2, 6} or {0, 3, 5}. It is not hard to find a solution from here. There are 48 solutions in total (ignoring the trivial solutions by swapping abc and def). The following is a piece of Python code for all solutions:

#!/usr/bin/env python
def perm(n, i):
    if i == len(n) - 1:
        yield list(n)
    else:
        for j in range(i, len(n)):
            n[i], n[j] = n[j], n[i]
            for x in perm(n, i + 1):
                yield list(n)
            n[i], n[j] = n[j], n[i] # swap back, for the next loop

for x in perm([9,8,7,6,5,4,3,2,0], 0):
    if x[0]<5 or x[0]==0 or x[3]==0 or x[0]<x[3]:
        continue
    if x[0]*100+x[1]*10+x[2]+x[3]*100+x[4]*10+x[5]==1000+x[6]*100+x[7]*10+x[8]:
        print "%d + %d = %d" % (x[0]*100+x[1]*10+x[2], x[3]*100+x[4]*10+x[5], 1000+x[6]*100+x[7]*10+x[8])