Extraordinary Social Security Number

Date: 12/05/2001 at 21:13:02
From: Elle
Subject: Combinations

Dear Sir or Ma'am,

My name is Elle Woods, and I am a 20 year old college student.  I 
have been given a math problem that I feel is possible to solve, but 
may take more time than I have been given.  Could you help me with my 
math problem?

Problem:

Dee finds that she has an extraordinary social security number.  Its
nine digits contain all the digits from 1 to 9.  They also form a
number with the following characteristics:

a. When read from left to right the first two digits form a
   number divisible by two.
b. The first three digits form a number divisible by three.
c. The first four digits a number divisible by four, and so on,
   until the complete number is divisible by 9.

What is Dee's social security number?

If I use the method I am currently using, I will not have enough time
to solve the problem.  Could you please help me?

Date: 12/06/2001 at 16:02:31
From: Doctor Greenie
Subject: Re: Combinations

Hello, Elle -

This page in the Dr. Math archives shows an answer where this problem 
is solved:

   Divisibility Word Problem
   http://mathforum.org/library/drmath/view/56742.html   

Actually, the problem on that page uses digits 0-9 to form a 10-digit 
number; the only difference from your problem is that the 10-digit 
number in the problem in the archives has final digit "0" (because the 
10-digit number must be divisible by 10); the first 9 digits of the 
10-digit number are the same as the 9-digit number in your problem.

I remembered seeing this problem in the archives a couple of years 
ago; but I thought I would also have a go at it myself.  Following is 
my solution; the result is of course the same, but the path to the 
solution, while it has many similarities to the solution in the 
referenced problem, is different.


Let's start by using divisibility rules to list the restrictions 
imposed by the conditions of the problem....

The number formed by the first digit is divisible by 1

  (there are no restrictions imposed by this condition since every 
   1-digit number is divisible by 1)

The number formed by the first two digits is divisible by 2

   (1) digit 2 must be even

The number formed by the first three digits must be divisible by 3

   (2) the sum of digits 1-3 must be divisible by 3

The number formed by the first four digits must be divisible by 4

   (3) digit 4 must be even
   (4) the number formed by digits 3-4 must be divisible by 4

The number formed by the first five digits must be divisible by 5

   (5) digit 5 must be 5

The number formed by the first six digits must be divisible by 6

   (6) digit 6 must be even
   (7) the sum of digits 1-6 must be divisible by 3

The number formed by the first seven digits must be divisible by 7

  (rules for divisibility by 7 are clumsy - let's not try to impose
   any restrictions on the digits here...)

The number formed by the first eight digits must be divisible by 8

   (8) digit 8 must be even
   (9) the number formed by digits 6-8 must be divisible by 8

The number formed by the first nine digits must be divisible by 9

  (10) the sum of digits 1-9 must be divisible by 3


Now let's start combining these restrictions logically to try to 
determine some of the digits.

From (1), (3), (6), and (8) above, digits 2, 4, 6, and 8 are even; so

   (11) digits 1, 3, 7, and 9 are odd (we already know digit 5 is odd)

From (2), (7), and (10) above, the sum of digits 1-3, the sum of 
digits 1-6, and the sum of digits 1-9 are all divisible by 3; from 
this, we can conclude that

   (12) the sum of digits 4-6 is divisible by 3
   (13) the sum of digits 7-9 is divisible by 3

From (1) and (11) above, digits 1-3 are odd, even, and odd; their sum 
is therefore even. From (2), this sum is divisible by 3. Therefore

   (14) the sum of digits 1-3 is an even multiple of 3 (6, 12, 18, 
        or 24)

From (3), (5), and (6) above, digits 4-6 are even, odd, and even; 
their sum is therefore odd. From (12), this sum is divisible by 3.  
Therefore

   (15) the sum of digits 4-6 is an odd multiple of 3 (9, 15, or 21)

From (8) and (11) above, digits 7-9 are odd, even, and odd; their sum 
is therefore even. From (13), this sum is divisible by 3. Therefore

   (16) the sum of digits 7-9 is an even multiple of 3 (6, 12, 18, 
        or 24)

From (15), the sum of digits 4-6 is either 9, 15, or 21; and from (5) 
we know digit 5 is 5. From (3) and (6), digits 4 and 6 are different 
even numbers. These facts together give us only a small number of 
possible combinations for digits 4-6:

   (17) the only possibilities for digits 4-6 are 258, 852, 456, 
        and 654

From (4) and (11), digits 3-4 form a 2-digit number with first digit 
odd that is a multiple of 4. With digit 3 odd, we then know

   (18) the only possibilities for digit 4 are 2 and 6

Combining (17) and (18), we now have

   (19) the only possibilities for digits 4-6 are 258 and 654

From (8), (9), and (11), digits 6-8 form a 3-digit number, divisible 
by 8, with middle digit odd.  We can combine this with (19) to 
determine

   (20) if digits 4-6 are 258, then digit 8 must be 6, making digit 2 
        equal to 4
   (21) if digits 4-6 are 654, then digit 8 must be 2, making digit 2 
        equal to 8

From (1), (11), and (14), digits 1-3 are odd, even, and odd, and the 
sum of those digits is an even multiple of 3. Here is a complete list 
of the possibilities for these digits:

   (sum =  6)  123  321
   (sum = 12)  129  921  327  723  147  741  183  381
   (sum = 18)  729  927  369  963  189  981  387  783
   (sum = 24)  789  987

From (20), we know that if digits 4-6 are 258, then digit 8 must be 6, 
making digit 2 equal to 4. In the list of possible combinations for 
digits 1-3, there are only two combinations with digit 2 equal to 4 
(147 and 741); so we now know that

   (22) if digits 4-6 are 258, then the possible solutions to the  
        problem are

   147 258 369  or  147 258 963
   741 258 369  or  741 258 963

With these possible solutions, digits 6-8 are either 836 or 896; 
condition (9) eliminates the two possible solutions with digits 6-8 
equal to 836.  Then, the requirement that the number formed from 
digits 1-7 be divisible by 7 eliminates the two possible solutions 
with digits 6-8 equal to 896.  So there are no solutions with digits 
4-6 equal to 258.

From (21), we know that if digits 4-6 are 654, then digit 8 must be 2, 
making digit 2 equal to 8. In the list of possible combinations for 
digits 1-3, there are eight combinations with digit 2 equal to 8; this 
tells us that

   (23) if digits 4-6 are 654, then the possible solutions to the 
        problem are

   183 654 729  or  183 654 927
   381 654 729  or  381 654 927

   189 654 327  or  189 654 723
   981 654 327  or  981 654 723

   387 654 129  or  387 654 921
   783 654 129  or  783 654 921

   789 654 123  or  789 654 321
   987 654 123  or  987 654 321

With these possible solutions, digits 6-8 are either 412, 432, 472, 
or 492; condition (9) eliminates the possible solutions with digits 
6-8 equal to either 412 or 492.  The remaining possible solutions are

   183 654 729
   381 654 729

   189 654 327
   981 654 327

   189 654 723
   981 654 723

   789 654 321
   897 654 321

Only one of these satisfies the condition that the number formed by 
digits 1-7 be divisible by 7.

The single solution to the problem is

    381654729


This is a great problem.  I hope my response and the referenced 
problem in the Dr. Math archives have helped give you an idea of 
possible ways to go about solving problems like this.

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