Sum of random numbers is divisible by $10$

Suppose that $15$ three-digit numbers have been randomly chosen and we are about to add them. What is the probability that the sum would be divisible by $10$?

If there were only two or three random numbers we could enumerate the cases in which last digit comes out to be $0$ and hence calculate probability but for $15$ numbers that seems messy so is there a smart way to do it

Edit:

I have tried another approach which finds the possible sums of $15$ three-digit numbers and then find the sums divisible by $10$ in the same range. So I get:

Number of Sums divisible by $10$ in $[1500,14985]=1349$
Total Number of Sums in $[1500,14985]=13486$
And then $P=\frac{1349}{13486}$, but as a comment suggests that this approach does not cater for the fact that a sum may be reached in a multiple of ways. So how can we cater for this fact?

I am guessing may be multinomial can be of help ?

• I'd guess $1$ in $10$. When you add random numbers, you get random numbers. – JMCF125 Mar 8 '14 at 13:31
• That may be true but I don't know for sure, can you give a proof ? – Wajahat Mar 8 '14 at 13:44
• Why not consider only the last digit? – evil999man Mar 8 '14 at 14:46
• @Wajahat I am still working on adding natural numbers with restriction <10. See my answer here for what I am trying to do. math.stackexchange.com/questions/689975/… – evil999man Mar 8 '14 at 14:51
• AS you study computer science you can always know the answer upto a few decimal places by making a program :D – evil999man Mar 8 '14 at 15:51

Add up the first 14 numbers. Then, whatever the remainder of the result modulo $10$, adding the 15th number will give each of the possible remainders with equal probability. So the answer is $0.1$.

• Excellent...Btw I computed by a $really$ long method...LOL – evil999man Mar 8 '14 at 17:11
• Why will adding the 15th number give each remainder with equal probability ? – Wajahat Mar 8 '14 at 17:17
• Suppose the unit's digit is x. Now all equal probabilities are x,x+1,x+2...x+9 (all are modulus 10 for last digit). Hence, all are distinct. – evil999man Mar 8 '14 at 17:21
• @Wajahat: If the sum of the first $14$ numbers leaves some remainder $x$ modulo $10$ (i.e., in base $10$ the last digit of the sum of the first $14$ numbers is $x$), then, as the last ($15$th) number (call it $c_{15}$) can take on all the values $0, 1, 2,\dots, 9$ with equal probability, the remainder of the sum of all $15$ numbers on dividing by $10$ is the same (mod $10$) as $x + c_{15}$, which takes on all $10$ values $x, x+1, x+2, \dots, x+9$ with equal probability. Thus all $10$ remainders are equally probable, and remainder $0$ is one of them, so it has probability $\dfrac1{10}$ exactly. – ShreevatsaR Mar 9 '14 at 3:49

Say $x_i, i=1,\ldots,15$ are 15 3-digit numbers. The probability that 10 divides their sum is equal to the probability that $$\sum_{i=1}^{15} x_i=0 \pmod{10}$$ But this corresponds to choosing 15 1-digit numbers (zero's and repeats allowed).

For each $x_i$ the probability that $x_i=z_j \pmod{10}$ (for some $z_j\in\{0,\ldots,9\}$) is $\frac{1}{10}$. Then you have to compute the probability that $10$ divides $\sum_{i=1}^{15}x_i\pmod{10}=\sum_{i=1}^{15}z_i$.

The sum of 15 1-digit numbers ranges from $0$ to $9\times 15=135$. Within this range there are 14 numbers which give you zero modulo 10. Those numbers are $\{0,10,\ldots,130\}$. If you find how many ways are there to choose 15 1-digit numbers such that their sum equals one of these numbers, you're done.

• well that answer sure does simplify the problem a little bit, can u give a pointer on how can we find the number of ways to get a specific sum? – Wajahat Mar 8 '14 at 15:15
• @Wajahat I have to leave right now. I can expand my answer later, if you still don't have the solution by then. But I think Awesome answers to that question. – frabala Mar 8 '14 at 15:37

The important fact is that in your population, all remainders on division by $10$ are equally probable-there are $150$ with each ones digit. If you choose the first two and add them, you define what the ones digit of the last needs to be. It will be that with probability $\frac 1{10}$. This is really a restating of frabala's answer without the language of modulo arithmetic.

Consider only last digit (frabala explains it and it is pretty obvious too):

$a_1+a_2...a_{15}=0,10,20...130$

$1$ solution for $0$

Note that $0\leqslant a_i \leqslant 9$

Number of solutions for e.g. $10$

Coefficient of $x^{10}$ in $(1+x^1+x^2...x^9)^{15}$

$Explanation$ : What happens when while opening that messy ^15 you multiply x^somethings and get x^15 ? This corresponds to a way of adding 15 whole numbers to a total of 15(see 1 as x^0). So number of time this happens the coefficient gets added by 1 (coefficient ++ in your language).

Use formula for GP inside and use taylor expansion for denominator and add using properties of binomial coefficients. Add all cases.I have to go now and will complete when I get time. //Google for taylor series if you don't know them.

Let me go ahead as far as time allows...

$(\frac{x^{10}-1}{x-1} )^{15} = (1-x^{10})^{15}(1+^{15}C_1x+^{16}C_2x^2...)$

Find coefficient of $x^{10}$ and 20,30... in this expression and add them. Use wolfram alpha if you get bored in middle. I have to go now... I am leaving this as an exercise

https://www.wolframalpha.com/input/?i=expand+%281%2Bx%2Bx%5E2%2Bx%5E3%2Bx%5E4%2Bx%5E5%2Bx%5E6%2Bx%5E7%2Bx%5E8%2Bx%5E9%29%5E15+

Guess what does the sum come out? 10^14...LOL HAHAHAHAHAH.....:( //All hail wolfram alpha

Total cases = $10^{15}$ //this one's elementary, right?

$Answer=\frac{sum}{10^{15}}$ Hence answer is exactly $0.1$....

• Totally did not get your answer – Wajahat Mar 8 '14 at 15:00
• @Wajahat Oh...will update the answer – evil999man Mar 8 '14 at 15:37
• @Wajahat Get it now??? My method is same as as frabala. Give it a try yourself and tell me if you don't get it. – evil999man Mar 8 '14 at 15:47
• What you don't understand? – evil999man Mar 8 '14 at 16:31
• I understand now – Wajahat Mar 8 '14 at 16:44

Well, the smallest sum is $100+101+102+...+114 = 100\cdot 15+\frac{14\cdot 15}{2} = 1605$, while the greatest sum is $999+998+997+..+985 = 1000\cdot 15-\frac{15\cdot 16}{2} = 14880$, so all the possible sums are $14880-1605+1 = 13276$, while the sums divisible by ten are $\left\lfloor\frac{14880}{10}\right\rfloor-\left\lfloor\frac{1605}{10}\right\rfloor=1488-160=1328$. Now, I know it is not the correct answer ( there might be more than 1 way to obtain a certain sum $\to$ you'd have to multiply the sum with the number of times it can be reached ), but I'm sure you can approximate the probability with $\approx \frac{1328}{13276}\approx\frac{1}{10}$

• Why do you assume the numbers don't repeat? – JMCF125 Mar 8 '14 at 14:24
• JMCF125's approximation was better – evil999man Mar 8 '14 at 14:25
• Actually, I have used the same approach without assuming numbers are unique and I have got 1349/13486 which is also nearly equal to 0.1 – Wajahat Mar 8 '14 at 14:27
• @Wajahat, I was thinking about that, but I thought as it is in this answer «Now, I know it is not the correct answer ( there might be more than 1 way to obtain a certain sum → you'd have to multiply the sum with the number of times it can be reached )». Also, I think you should have included that try in your question. Because the deepness of this question is in the amount of times a value can be reached. – JMCF125 Mar 8 '14 at 14:36
• @JMCF125 oh yes you are right, this is more complex. But how do we solve that ? – Wajahat Mar 8 '14 at 14:37

The sum of any two random numbers is a random number. Furthermore, that sum, being random, added to another random number is still a random number. However, the first digit of the three digit number is not truly random since it can not be a 0, since that would cause the number to not be a three digit number. But the value of the first and second digit of any of the fifteen random three digit numbers can not affect the third digit, i.e., the units digit. Therefore we can ignore them and the problem becomes "What is the probability that the sum of 15 single digit numbers between 0 and nine ends in 0. Once again, when you add two random numbers you get a random number. And, as above the units digit will be a random number between 0 and 9 inclusive. If the numbers are truly random, then the units digit of the sum will be truly random. Therefor the probably is that the units digit of the sum will any of the ten values is the same as any other. And since there are ten possibilities, then the probability of it being a zero is 1/10. Giving that the probability of the sum of ten three-digit numbers is evenly divisible by ten is 1/10.

however