10 digit number

Aquafina · #1 $Old$ November 2nd, 2009, 07:06 AM

A 10 digit number is made up of only 5s and 0s. It's also divisible by 9. How many possibilities are there for the number?

Working backwards, I cam e to the conclusion that it cannot end in a 0, as that would been there was a remainder of 9 from the previous number. Then if it ends in a 5, that means a remainder of 4 was there from the previous. Now that could mean the 2nd last digit is either 0 or 5. But I'm lost after that, don't think I can apply this reasoning till the first digit.

Media_Man · #2 $Old$ November 2nd, 2009, 08:09 AM

So you are solving $\sum_{n=0}^9 a_n10^n\equiv 0 (\bmod 9)$ , where each $a_n\in\{0,5\}$ . Since $10^n\equiv 1 (\bmod 9)$ for all n, all you have is $9|\sum_{n=0}^9 a_n$ . Since $a_n$ is either 0 or 5, you really have $9|5k$ for some k, which can only be 0 or 9. So you either have all zeroes, no fives, or 9 fives, 1 zero. There is one solution for the first option, and $_{10}P_1=10$ solutions for the second option, so your answer is 11.

Aquafina · #3 $Old$ November 2nd, 2009, 08:28 AM

Hi Media Man.

Sorry I didn't follow what you did on:

Quote:

Originally Posted by Media_Man $View Post$

Since $10^n\equiv 1 (\bmod 9)$ for all n, all you have is $9|\sum_{n=0}^9 a_n$ . Since $a_n$ is either 0 or 5, you really have $9|5k$ for some k, which can only be 0 or 9.

So you divided the coefficients of each power of 10 by 9, and since each 10 leaves a remainder of 1, that equals 9 so they can be ignored. OK

Then how do you the next bit with the 5k?

Media_Man · #4 $Old$ November 2nd, 2009, 08:35 AM

The jump to "so 9|5k" just means you are looking for a 10 digit number consisting of k 5's in any order whatsoever. In other words, the power of 10 for which they are coefficients is irrelevant. So 505=550=055 (mod 9), for example.

Bingk · #5 $Old$ November 2nd, 2009, 03:40 PM

$a_9 \cdot 10^9 + a_8 \cdot 10^8 + a_7 \cdot 10^7 + ... + a_3 \cdot 10^3 + a_2 \cdot 10^2 + a_1 \cdot 10^1 + a_0 \cdot 10^0 \equiv 0 \ (\bmod \ 9)$

Since $10^n\equiv 1 \ (\bmod \ 9)$

$a_9 \cdot 1 + a_8 \cdot 1 + a_7 \cdot 1 + ... + a_3 \cdot 1 + a_2 \cdot 1 + a_1 \cdot 1 + a_0 \cdot 1 \equiv 0 \ (\bmod \ 9)$

Since the a's are either 0 or 5, when you add them, it's basically a multiple of 5, right? (if there are x a's that are equal to 5, then the sum of the digits will be 5x)

That's how Media_Man got: $5k \equiv 0 \ (\bmod \ 9)$ i.e. $9|5k$ , where $0 \leq k \leq 10$

You can think of it this way, do you know how to tell if a number is divisible by 9? (The sum of the digits should be divisible by 9, we kind of have a modified proof here for a 10 digit number) So, how many 5's should the number have so that when you sum up all the 5's, it should be divisible by 9?

I think the answer is actually 9 ... since 0 isn't a 10 digit number and 0555555555 isn't a 10 digit number either ... I guess it depends though ...

You can also check those 9 numbers by dividing them by 9 ... it's only 9 numbers

Plato · #6 $Old$ November 2nd, 2009, 03:51 PM

There is a really simple way to solve this.
If an integer is divisible by nine the sum of the digits is multiple of nine.
To have a ten digit number then the string must begin with a 5 followed by eight 5’s and one 0 in any order.
So the answer is 9.