Thursday, January 17, 2008

How about a math puzzle?

Number PuzzleIt has been awhile since I've posted any non-NPR puzzles. Here's one to make you think:
Q: A nine-digit number ABCDEFGHI is such that its digits are all distinct and non-zero. It has the following properties:
The two-digit number AB is divisible by 2,
the three-digit number ABC is divisible by 3,
the four-digit number ABCD is divisible by 4,
and so on until finally,
the nine-digit number ABCDEFGHI is divisible by 9.

What is this special nine-digit number?

2 comments:

  1. I couldn't figure out a shortcut to determining the number, so I ended up making a computer program to do the work for me.

    Though crudely written, it did find the answer for me.

    The number is 381654729

    ReplyDelete
  2. Indeed, your answer solves the puzzle:

    2 x 19 = 38
    3 x 127 = 381
    4 x 954 = 3816
    5 x 7633 = 38165
    6 x 63609 = 381654
    7 x 545221 = 3816547
    8 x 4770684 = 38165472
    9 x 42406081 = 381654729

    However, you can get there with logic rather than a brute force program:

    We know that ABCDE must be a multiple of 5, so E must be 5.

    AB, ABCD, ABCDEF, ABCDEFGH are multiples of 2, 4, 6 and 8 respectively. Thus their last digits (B, D, F and H) must be even. That leaves 1, 3, 7 and 9 for A, C, G and I.

    ABCD is a multiple of 4, so CD must be a multiple of 4. Given that C is odd, the possible values are {12, 16, 32, 36, 72, 76, 92 and 96}. That means D must be 2 or 6.

    Similarly ABCDEFGH is a multiple of 8 (and therefore 4). Using similar logic, GH will be in {12, 16, 32, 36, 72, 76, 92 and 96}. Therefore H must be 2 or 6.

    Because 2 and 6 are accounted for, B and F must be 4 and 8. That means FGH will be {412, 416, 432, 436, 472, 476, 492, 496, 812, 816, 832, 836, 872, 876, 892 or 896}.

    But FGH needs to be a multiple of 8 as well as a multiple of 4. The only multiples of 8 are {416, 472, 496, 816, 872 or 896}

    ABC is a multiple of 3 so its digits must add to be a multiple of 3. Possible choices are {147, 183, 189, 381, 387, 741, 783, 789, 981, 987}

    ABCDEF is a multiple of 6 and therefore also a multiple of 3. Given that ABC already adds to a multiple of 3, we only need to check DEF. E is 5. Possible choices for DEF are {258, 654}

    Putting things together we have a couple possible patterns:
    A-4-C-2-5-8-G-6-I
    or
    A-8-C-6-5-4-G-2-I

    That reduces the set of choices for FGH to {472, 816, 896}

    So the 3 possible patterns are now:
    A-4-C-2-5-8-1-6-I
    A-4-C-2-5-8-9-6-I
    A-8-C-6-5-4-7-2-I

    Looking at our set of possible values for ABC we have {147, 183, 189, 381, 387, 741, 783, 789, 981, 987}. If B = 4, then ABC is either {147 or 741}. That eliminates the first string. If B = 8, all the values using 7 are eliminated.

    So now we have:

    {147 or 741}
    1-4-7-2-5-8-9-6-I
    7-4-1-2-5-8-9-6-I

    {183, 189, 381, 981}
    1-8-3-6-5-4-7-2-I
    1-8-9-6-5-4-7-2-I
    3-8-1-6-5-4-7-2-I
    9-8-1-6-5-4-7-2-I

    Okay there are 6 sequences to check to see if ABCDEFG is a multiple of 7.
    1472589 / 7 = 210369.857142...
    7412589 / 7 = 1058941.285714...
    1836547 / 7 = 262363.857142...
    1896547 / 7 = 270935.285714...
    3816547 / 7 = 545221
    9816547 / 7 = 1402363.857142...

    As you can see only one is evenly divisable by 7.
    3816547

    That's part of this pattern:
    3-8-1-6-5-4-7-2-I

    The final digit is 9. Obviously the nine digits add up to 45, so the full number will be a multiple of nine regardless.

    Answer:
    381654729

    ReplyDelete