[Math] Probability of getting a five digit number divisible by 5 but with no two consecutive digits identical

divisibilityelementary-number-theoryprobability

A five digit number is written down at random. What is the probability of getting a number that is both divisible by 5 and doesn't have any 2 consecutive digits identical?

I tried to analyse the situation casewise, 1. Last digit is 5 and 2. Last digit is 0, but that did not lead me anywhere because of the added constraint that the first digit can't be 0. I've seen some books where the answer is given as $$\frac{9^3*8*2}{9*10^4}$$ but that isn't the correct answer. There, they have considered that when the last digit is 5, for instance, the third digit is NOT 5. However, the third digit may be 5 in which case, there'll still be 9 options (digits 0 through 9 except 5) to place in the fourth position and so on …

To crosscheck, I wrote a short code to find out the probability, and it came out to be $$\frac{11809}{9*10^4}$$

Is there any way to find the probability without enumeration ?

Best Answer

Let's split the $n$-digit numbers without consecutive identical digits that end in a given digit, with leading zeros allowed, into $a_n$ numbers with identical first and last digits and $b_n$ numbers with different first and last digits. Then we have the recurrences $a_{n+1}=b_n$ and $b_{n+1}=9a_n+8b_n$. Eliminating $b_n$ yields $a_{n+2}=9a_n+8a_{n+1}$. With $a_1=1$ and $a_2=0$, this yields $a_3=9$, $a_4=72$, $a_5=657$, $a_6=5904$ and thus also $b_5=5904$. We want the $a_5$ admissible numbers ending in $5$, and the $8/9$ of the $b_5$ admissible numbers ending in $5$ that don't begin with $0$, and the $b_5$ admissible numbers ending in $0$. So that's

$$ a_5+\frac89b_5+b_5=657+\frac{17}9\cdot5904=11809\;. $$

This we have to divide by the total number $9\cdot10^4$ of $5$-digit numbers without leading zeros to arrive at your computed probability.