Solution to Problem 1

Solution by Brian Gregory

The answer would be 381654729 and this is the only one.

I did this two ways, first by working through the equations thennumerically with a program.

First the equations way. Now I found this a bit long and feelthere must be a simpler way.

Let n1 be the first digit, n2 the second ..... n9 the 9th.Let equation 1 be n1, equation 2 be 10*n1 + n2,equation 3 be 100*n1 + 10 * n2 + n3 ...etc

Now look at equation 5, this is divisible by 5. 10,000*n1 + 1,000*n2 + 100*n3 + 10*n4 + n5Each of the first 4 terms is divisible by 5 (as 5|10 ...)Since each is divisible by 5, n5 must also be divisableby 5. The only single digit divisable by 5 is 0 and 5,and 0 is not one of our digits, so n5 = 5.

No looking at equations 2, 4, 6 and 8 each must be divisable by 2 as each is divisable by an even number. Therefore each mustend in an even number. Therefore n2, n4, n6 and n8 must be 2 or 4 or 6 or 8 in some order.Similary each of n1, n3, n7 and n9 must be 1 or 3 or 7 or 9.

Looking at equation 4

1,000*n1 + 100*n2 + 10*n3 + n4
Now the first 2 terms are divisable by 4 as 100 and 1,000 aredivisable by 4. Therefore 10*n3 + n4 is divisible by 4.Now n3 is one of 1, 3, 7, or 9. subing in each of these forn3, n4 is either 2 or 6.

Looking at equation 8

10,000,000*n1 + 1,000,000*n2 + 100,000*n3 + 10,000*n4 +1,000*n5 + 100*n6 + 10*n7 + n8
Now the first 5 terms are divisible by 8.Now since n6 is one of 2, 4, 6, or 8 100*n6 is alsodivisable by 8 so 10*n7 + n8 is divisible by 8.now again n7 is one of 1, 3, 7 or 9so trying each and solving for n8, n8 is 2 or 6.

Now if n4 and n8 are both either 2 or 6 thenn2 and n6 are either 4 or 8.

Look at equation 6

100,000*n1 + 10,000*n2 + 1000*n3 + 100*n4 +10*n5 + n6
now from equation 3 100*n1 + 10*n2 + n3 is divisable by 3so the first 3 terms of equation 6 is divisable by 3,000.Since 6|3,000, the first 3 terms are divisable by 6 and therfore 100*n4 + 10*n5 + n6 is divisable by 6.

Now we have 2 possiblities for n4, Lets try bothTry n4 = 2 and n8 = 6.From equation 6, 100*2 + 10*5 + n6 is divisable by 6so n6 is 2 or 8, but can't be 2 as n4 is 2.So n6 = 8 and n2 = 4

now try n4 = 6 and n8 = 2Again solve for equation 6 toget n6 = 4 and n2 = 8

at this point we have two possible partialsolutions as follows

      n1  n2  n3  n4  n5  n6  n7  n8  n9  #1        4       2   5   8       6#2        8       6   5   4       2
Now we cannot glean anything from equation 1 as all digits are divisable by 1Also we get no information from equation 9as all combinations of the nine digits aredivisable by 9 (clearly :)
So we are left with equation 3 and 7to use to solve for n1, n2, and n3 (n9 is whatever is left over)I did a brute force method here and went throughall the combinations (24 combinations) thatmade sense and found the only one that didnot confilict.

Then I ran the following program which alsogave the answer. 

#include #include int main(int argc, char *argv[]);void Check(CString front, CString end);int main(int argc, char *argv[]){        Check("", "123456789");        return 0;}// CString is a string class in the Microsoft Foundation Classes(MFC)void Check(CString front, CString end){        if (end.GetLength() > 0)        {                CString newFront, newEnd;                for (int i = 0 ; i < end.GetLength(); i++)                {                        newFront = front + end[i];                        newEnd = end.Left(i) + end.Right(end.GetLength()-i-1);                        Check(newFront, newEnd);                }        }        else        {                bool valid = true;                for (int i = 1; i <= front.GetLength() ; i++)                {                        if (atoi(front.Left(i)) % i != 0)                        {                                valid = false;                                break;                        }                }                if (valid)                {                        cout << front << " is a valid combination" << endl;                }        }}
Also solved by Mike Arsenault (mike.arsenault@objectquest.com).
Back to the Problem of the Week page
Back toMathBack to the Math home page