Associated Topics || Dr. Math Home || Search Dr. Math

### 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
```

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

Hello, Elle -

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search