Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Divisibility Word Problem


Date: 1/27/96 at 0:35:42
From: Anonymous
Subject: HELP

Dear Dr.Math,

Slow as it may sound, I've been trying to solve this problem for a 
year now with nil result. Could you help me?

Here goes the problem:

Arrange the digits 0 to 9 such, that the number formed by the 
first digit is divisible by 1, the number formed by the first two 
digits is divisible by 2, that formed by the first three digits 
divisible by 3, and so forth, thus the number formed by the first 
9 digits will be divisible by 9 and that formed by all 10 digits 
divisible by 10.

Thanks in advance for your help.



Date: 3/4/96 at 19:58:37
From: Doctor Ethan and Doctor Ken
Subject: Re: HELP

Hello.

This is a great problem.

We have ten blanks to fill according to the criteria you listed.

Here is what I would do.

_ _ _ _ _ _ _ _ _ _ 

those are my ten blanks.

Now let's start asking questions.

Since the whole thing has to be divisible by 10, the last number 
must be a zero.

And since the first five digits must be divisible by 5, the fifth 
digit must be a 5 or 0, but we have already used 0 so it must be a 
five.

One last quickie is that the 2nd, 4th, 6th, and 8th and last 
digits must be even, so all the rest are odd

So let's look at we have.  I'll write the digits that could go in a
certain place under where they could go:


_ _ _ _ 5 _ _ _ _ 0
1 2 1 2   2 1 2 1 
3 4 3 4   4 3 4 3
7 6 7 6   6 7 6 7
9 8 9 8   8 9 8 9

     Now things get trickier.

Let's start with the 4th spot.  

Any number is divisible by 4 if the last two digits are divisible 
by 4

So what are the two-digit numbers divisible by 4 that begin with 
an odd number that is not 5?

12 16 32 36 72 76 92 96 

Hey, so the 4th digit is either a 2 or a 6.

Now, let's look at the 8th digit.  If the first 8 digits are
divisible by 8, then they are divisible by 4 also.  So if we apply
the same logic as above, we find that the 8th digit is either a 2 or
a 6.

So spaces 2 and 6 must be 4 or 8.

That narrows it down.  So we have this:

_ _ _ _ 5 _ _ _ _ 0
1 4 1 2   4 1 2 1 
3 8 3 6   8 3 6 3
7   7       7   7
9   9       9   9



Now for my next trick let's recall that every third space must be 
divisible by 3.  So every three numbers must sum to be divisible 
by 3.

In particular spaces 4, 5, and 6 must sum to 3, and we already 
have a five.  So either we have  

2 5 8  or  6 5 4 

in positions 4, 5, and 6.

That is good stuff.  That means we have either this:

_ 4 _ 2 5 8 _ 6 _ 0
1   1       1   1 
3   3       3   3
7   7       7   7
9   9       9   9

    or this:

_ 8 _ 6 5 4 _ 2 _ 0
1   1       1   1 
3   3       3   3
7   7       7   7
9   9       9   9

Let's check each of the four digits we could put in the 8th place.
Since a number is divisible by 8 if its last 3 digits are, we need
number in the 6th, 7th, and 8th places to be divisible by 8.  We see
that 816 and 896 work in the first case, and 432 and 472 work in the
second case.  So we have:

_ 4 _ 2 5 8 _ 6 _ 0
1   1       1   1 
3   3       9   3
7   7           7
9   9           9

    or this:

_ 8 _ 6 5 4 _ 2 _ 0
1   1       3   1 
3   3       7   3
7   7           7
9   9           9


Let's look at the 9th place now.  Recall that 1+2+3+4+5+6+7+8+9 = 45,
so we don't need to worry about the 9th place - it will always work
out.

Let's look at the 1st and 3rd places.  In case 1, only 147 and 741 are
options.  In case 2, we could have 183, 189, 381, 387, 783, 789, 981, or
987.  Note that 387 and 783 don't work, because then we don't have any
digits left for the 7th digit.

So our first case becomes:

_ 4 _ 2 5 8 9 6 3 0
1   1             
7   7

We can just check the two numbers this can give rise to, namely 1472589630
and 7412589630.  Since neither of them are divisible by 7, case one must be
a dead end.  So we have to work with case two if we want a solution:

_ 8 _ 6 5 4 _ 2 _ 0
1   1       3   1 
3   3       7   3
7   7           7
9   9           9

(and the first 3 digits are 183, 189, 381, 789, 981, or 987)

If we look at the 7th, 8th, and 9th digits to see if we can get them to sum
to three, we see that only 321, 327, 723, and 729 are options.

So which of our options for digits 1,2,3 and 7,8,9 can we use together?  In
order to not repeat digits, we could use these:

183 and 729
189 and 327
189 and 723
381 and 729
789 and 321
981 and 327
981 and 723
987 and 321

This means that the only possible solutions to the puzzle are these:

1836547290
1896543270
1896547230
3816547290
7896543210
9816543270
9816547230
9876543210

This is now a small enough number of cases that we can check them by hand.
The first thing we should do is check the first 7 digits for divisibility by
seven.  Here are the results:

1836547/7 = 262363.857142857...
1896543/7 = 270934.714285714...
1896547/7 = 270935.285714286...
3816547/7 = 545221
7896543/7 = 1128077.57142857...
9816543/7 = 1402363.28571429...
9816547/7 = 1402363.85714286...
9876543/7 = 1410934.71428571...


All right, we did it.  You should check all the cases just to make sure.
Good question! Hope this helps you.


- Doctors Ethan and Ken,  for the Math Forum

    
Associated Topics:
High School Puzzles

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/