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.

1 8 7

4 5 2

—–

6 3 9

Mostly by trial and error ðŸ˜‰

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.

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?

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.

129

438

567

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:])

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

254

637

891

so what IS the answer? I couldnt solve it!

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 ðŸ™‚

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

317

628

—

945

Is this what you meant?

127

+368

—

495

This took me about 60 seconds.

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