Puzzle to Find a 10 Digit Number

Date: 10/10/2004 at 11:58:56
From: Ravi
Subject: A Very Special Mystery Number

I have to find a 10 digit number which uses each of the digits 0-9 
and has ALL the following properties:

1) The first digit from the left(the billions digit) is divisible by 1.

2) The number formed by the first 2 digits from the left is divisible 
by 2.

3) The number formed by the first 3 digits from the left is divisible 
by 3.

4) The number formed by the first 4 digits from the left is divisible 
by 4.

5) The number formed by the first 5 digits from the left is divisible 
by 5.

6) The number formed by the first 6 digits from the left is divisible 
by 6.

7) The number formed by the first 7 digits from the left is divisible 
by 7.

8) The number formed by the first 8 didgits from the left is divisible 
by 8.

9) The number formed by the first 9 digits from the left is divisible 
by 9.

10) The number itself is divisible by 10.

I figured out the answer, but it took me nearly two weeks.  The first
thing I found out was that the number ended in a 0 and that the fifth
digit was a 5.  I also knew that the second, fourth, and eighth digits
were all even.  From that I figured out that the first, third, and
seventh digits would have to be odd.  From there I just did guess and
check.

I was wondering if there is a better method than guess and check?
Could you explain it to me step-by-step?  Thanks a lot.

Date: 10/16/2004 at 12:44:53
From: Doctor Ian
Subject: Re: A Very Special Mystery Number


Hi Ravi,

>I have to find a 10 digit number which uses each of the digits 0-9 
>and has ALL the folowing properties:
>
>1)The first digit from the left(the billions digit)is divisible by 1.

This clue doesn't tell us anything at all, since _every_ digit will be
divisible by 1. 

>2)The number formed by the first 2 digits from the left is divisible 
>by 2.
>
>3)The number formed by the first 3 digits fromt he left is divisible 
>by 3.
>
>4)The number formed by the first 4 digits from the left is divisible 
>by 4.
>
>5)The number formed by the first 5 digits from the left is divisible 
>by 5.

This tells you that the 5th digit has to be a zero or a 5.  So we have

  _ _ _ _ [05] _ _ _ _ _

That's not much, but it's a start. 

>6)The number formed by the first 6 digits from the left is divisible 
>by 6.
>
>7)The number formed by the first 7 digits from the left is divisible 
>by 7.
>
>8)The number formed by the first 8 didgits from the left is divisible 
>by 8.
>
>9)The number formed by the first 9 digits from the left is divisible 
>by 9.
>
>10)The number itself is divisible by 10.

This tells you that the final digit has to be a 0, which means the 5th
digit can't be zero.  So we have

  _ _ _ _ 5 _ _ _ _ 0


Clue 2 tells us that the second digit is even, but we already know it
can't be 0:

  _ [2468] _ _ 5 _ _ _ _ 0

Clue 4 tells us that the 4th digit is also even, and it can't be the
same digit as digit 2.  At this point, we have to start considering
dependencies.  That is, we make a tentative choice for the second
digit, and it leads to tentative choices for the fourth digit:

  - 2 - 4 5 - - - - 0
  - 2 - 6 5 - - - - 0
  - 2 - 8 5 - - - - 0
  - 4 - 2 5 - - - - 0
  - 4 - 6 5 - - - - 0
  - 4 - 8 5 - - - - 0
  - 6 - 2 5 - - - - 0
  - 6 - 4 5 - - - - 0
  - 6 - 8 5 - - - - 0
  - 8 - 2 5 - - - - 0
  - 8 - 4 5 - - - - 0
  - 8 - 6 5 - - - - 0

The 9th clue isn't much help, either:  If we add up the digits other
than zero, 

  1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

the sum is divisible by 9.  So _any_ arrangement of those digits will
be divisible by 9.  

So let's recap:

              Clues
  Used:       2, 4, 5, 10
  Useless:    1, 9
  Unused:     3, 6, 7, 8

Let's look at clue 8.  As before, the 8th digit has to be even, and it
can't be any of the other digits.  So we can expand our possibilities
again:

  - 2 - 4 5 - - 6 - 0
  - 2 - 4 5 - - 8 - 0
  - 2 - 6 5 - - 4 - 0
  - 2 - 6 5 - - 8 - 0
  - 2 - 8 5 - - 4 - 0
  - 2 - 8 5 - - 6 - 0
  - 4 - 2 5 - - 6 - 0
  - 4 - 2 5 - - 8 - 0
  - 4 - 6 5 - - 2 - 0
  - 4 - 6 5 - - 8 - 0
  - 4 - 8 5 - - 2 - 0
  - 4 - 8 5 - - 6 - 0
  - 6 - 2 5 - - 4 - 0
  - 6 - 2 5 - - 8 - 0
  - 6 - 4 5 - - 2 - 0
  - 6 - 4 5 - - 8 - 0
  - 6 - 8 5 - - 2 - 0
  - 6 - 8 5 - - 4 - 0
  - 8 - 2 5 - - 4 - 0
  - 8 - 2 5 - - 6 - 0
  - 8 - 4 5 - - 2 - 0
  - 8 - 4 5 - - 6 - 0
  - 8 - 6 5 - - 2 - 0
  - 8 - 6 5 - - 4 - 0

Note that in each case, there is just one even digit left, and that
will have to go in the 6th place, since the first 6 digits are
divisible by 6, which means they're divisible by 2, which means the
6th digit is even.  So we can enumerate those possibilities:

  - 2 - 4 5 8 - 6 - 0
  - 2 - 4 5 6 - 8 - 0
  - 2 - 6 5 8 - 4 - 0
  - 2 - 6 5 4 - 8 - 0
  - 2 - 8 5 6 - 4 - 0
  - 2 - 8 5 4 - 6 - 0
  - 4 - 2 5 8 - 6 - 0
  - 4 - 2 5 6 - 8 - 0
  - 4 - 6 5 8 - 2 - 0
  - 4 - 6 5 2 - 8 - 0
  - 4 - 8 5 6 - 2 - 0
  - 4 - 8 5 2 - 6 - 0
  - 6 - 2 5 8 - 4 - 0
  - 6 - 2 5 4 - 8 - 0
  - 6 - 4 5 8 - 2 - 0
  - 6 - 4 5 2 - 8 - 0
  - 6 - 8 5 4 - 2 - 0
  - 6 - 8 5 2 - 4 - 0
  - 8 - 2 5 6 - 4 - 0
  - 8 - 2 5 4 - 6 - 0
  - 8 - 4 5 6 - 2 - 0
  - 8 - 4 5 2 - 6 - 0
  - 8 - 6 5 4 - 2 - 0
  - 8 - 6 5 2 - 4 - 0

We can use clues 3 and 6 together at this point.  The sum of the first
3 digits, and the sum of the first 6 digits, have to be divisible by
3.  So that means the first 3 digits have to add up to something
divisible by 3; and so do the first 6 digits. 

But this means that the _second_ 3 digits have to add up to something
divisible by 3 as well!  (Do you see why?)  So we can rule out any
possibilities where this isn't the case, e.g., 

  - 2 - 4 5 8 - 6 - 0         4 + 5 + 8 = 17      No.

So we can run through our table and get rid of the entries where the
second 3 digits don't add up to a multiple of 3:

  - 2 - 4 5 8 - 6 - 0         4 + 5 + 8 = 17      No.
  - 2 - 4 5 6 - 8 - 0         4 + 5 + 6 = 15      Yes.
  - 2 - 6 5 8 - 4 - 0         6 + 5 + 8 = 19      No.
  - 2 - 6 5 4 - 8 - 0         6 + 5 + 4 = 15      Yes.
  - 2 - 8 5 6 - 4 - 0         8 + 5 + 6 = 19      No.
  - 2 - 8 5 4 - 6 - 0         8 + 5 + 4 = 17      No.
  - 4 - 2 5 8 - 6 - 0         2 + 5 + 8 = 15      Yes.
  - 4 - 2 5 6 - 8 - 0         2 + 5 + 6 = 13      No.
  - 4 - 6 5 8 - 2 - 0         
  - 4 - 6 5 2 - 8 - 0         and
  - 4 - 8 5 6 - 2 - 0         so
  - 4 - 8 5 2 - 6 - 0         on
  - 6 - 2 5 8 - 4 - 0
  - 6 - 2 5 4 - 8 - 0
  - 6 - 4 5 8 - 2 - 0
  - 6 - 4 5 2 - 8 - 0
  - 6 - 8 5 4 - 2 - 0
  - 6 - 8 5 2 - 4 - 0
  - 8 - 2 5 6 - 4 - 0
  - 8 - 2 5 4 - 6 - 0
  - 8 - 4 5 6 - 2 - 0
  - 8 - 4 5 2 - 6 - 0
  - 8 - 6 5 4 - 2 - 0
  - 8 - 6 5 2 - 4 - 0

What next?  Well, we can use clue 8 again.  Why?  Because 1000 is
divisible by 8; so if a number is divisible by 8, the final three
digits must be divisible by 8.  For example, if we know that 

  - 2 - 4 5 6 - 8 - 0         

is divisible by 8, then 

            6 - 8

must be divisible by 8.  In this case, 600 is divisible by 8, so 

              - 8

has to be divisible by 8, and the '-' will have to be an odd digit. 
There are just a few cases, so we can check them:

  18, 38, 58, 78, 98
   n   n   n   n   n

None of them are divisible by 8, so we can remove this entry from our
table.  What about something like this?

  - 4 - 2 5 8 - 6 - 0

Again, 800 is divisible by 8, so we need to check

  16, 36, 56, 76, 96
   y   n   y   n   y

Three of these are divisible by 8, so this expands to 

  - 4 - 2 5 8 1 6 - 0
  - 4 - 2 5 8 5 6 - 0
  - 4 - 2 5 8 9 6 - 0

If you do that for the remaining possibilities, you'll end up with
only three digits left to be deduced.  Actually, just two, since _any_
digit can go in the 9th place and satisfy clue 9.  

Now, that still leaves you with some guessing and checking to do; but
not an overwhelming amount. 

Does this help? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/