What is the probability that the digit sum of a randomly chosen integer between 0000 and 9999 is divisible by 5?

Solution 1:

Hint: Pick the first three digits randomly first, and then focus on the last one.

It's similar to how the probability of getting the sum $7$ when throwing two dice can be seen to be $\frac16$ by noting that no matter what the first die shows, the result on the second die can make the sum $7$ in exactly one way.

Solution 2:

20%, or 1 in 5. I just counted them all in Excel. Consider that in each decade there will be 2 numbers divisible by 5. The first being 0000 and 0005. Then 0014 and 0019. And so on until 0091 and 0096. Then each century will be similar to the first except for a shift like we get with each decade, 0104 & 0109... 0190 & 0195. Likewise with the millennia. Consequently, the odds remain the same, 1 in 5.

Solution 3:

Take the sum of the first 3 digits, and divide it by 5. You have either 0, 1, 2, 3, 4, with probabilities p_0, p_1, p_2, p_3, p_4. You could likely prove that p_i = 0.2 for all i, but there is no need. All you need is that sum(p_i) = 1

for any given i, there are two numbers that the last digit could be. For example, if i = 1, the last digit could be 4 or 9. Since 2 digits out of 10 possibles is 20%, for any given sum of the first 3 digits, there is a 20% chance that the total sum is divisible by 5

So you have: 0.2*p_0 + 0.2*p_1 + 0.2*p_2 + 0.2*p_3 + 0.2*p_4 = 0.2*(p_0+p_1+p_2+p_3+p_4) = 0.2*1 = 0.2

so 20% chance

Solution 4:

In this case we had it easy since the base 10 is a multiple of the divisor 5. What happens if we have $n$ digits in base $B$ and are interested in divisor $d$?

Let $\omega \neq 1$ be a $d$th root of unity, and consider $$ P(\omega) = \left(\frac{1 + \omega + \omega^2 + \cdots + \omega^{B-1}}{B}\right)^n = \left(\frac{1-\omega^B}{B(1-\omega)}\right)^n. $$ The coefficient of $\omega^r$ is the probability that the remainder is $r$. We can extract the probability of a zero remainder by going over all roots of unity (using $P(1) = 1$): $$ \Pr[r=0] = \frac{1}{d} + \frac{1}{d} \sum_{t=1}^{d-1} \left(\frac{1-\omega^{tB}}{B(1-\omega^t)}\right)^n. $$ It is not immediately clear why this expression is real. The reason is that the terms for $t$ and $d-t$ are complex conjugates (since $\omega^{d-t} = \overline{\omega^t}$).

Perron-Frobenius theory tells us that the norm of the eigenvalues $\frac{1-\omega^{tB}}{B(1-\omega^t)}$ is strictly less than 1, and so the convergence to $1/d$ is exponentially fast.