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

Question

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 ?

Answer 1

Let's say that $a_n$ represents the number of numbers with n digits, which are divisible by 5 and have no 2 consecutive digits identical.

Now, consider the case ($n>2$) where the 2nd digit is nonzero and equal to $p$. Thus, the first digit can anything except $p$ (so as to have non-identical consecutive digits) and $0$ (so that it remains a $n$ digit number). As a result, we have 8 options for the first digit and in each case, the remaining $n-1$ digits is a number of length $n-1$ which also satisfies the required conditions (non-identical and divisible by 5). So, the number of this entire case is possible is in $8\times a_{n-1}$

Next comes the other case, that is where the 2nd digit is $0$. The first digit can be anything but 0 in this case and hence has $9$ options whereas the rest of the number (3rd digit onwards) is a number of length $n-2$ satisfying the required conditions. This entire case is, thus, possible in $9\times a_{n-2}$

Combining these two, we get $$a_n = 8a_{n-1} + 9a_{n-2}$$

Along with $a_1 = 1$ (only 5) and $a_2 = 17$ this linear homogeneous recurrence relation can be solved using Generating Functions or otherwise.

Putting in the ansatz, $a_n = r^n$ we get $$r^n = 8r^{n-1} + 9r^{n-2}$$ which yields on simplifying the characteristic equation $$r^2 -8r -9 = 0$$ which has roots at $-1$ and $9$.

The general solution is $$a_n = \alpha 9^n + \beta (-1)^n$$ Putting in $a_1$ and $a_2$ we arrive at the following formula:

$$a_n = \frac{9^n + 4(-1)^n}{5} $$

For $5$ digit numbers we put $n=5$ to get $$a_5 = \frac{9^5-4}{5} = 11809$$ as required.

The probability is computed by dividing by the total $9\cdot 10^4$ cases.

Answer 2

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.

Answer 3

Revisiting this question after more than two years, I wondered if a more elementary (yet non-tedious) approach for counting the number of possibilities could be found.

Allowing leading zeroes, $\;\bullet\bullet\bullet\bullet 0\;$ and $\;\bullet\bullet\bullet\bullet 5\;$ both yield a count of $\;9^4\;$ counting backwards.
From this, we need to subtract configurations with leading zeroes.

Working in from both extremities, we have configurations $\;(0)\;9\cdot A\cdot9\; (0)\;$ and $\;(0)\cdot9\cdot B\cdot9\; (5)$

If the digits flanking the middle digit are identical, the middle digit will have $9$ choices,
and if non-identical, it will have $8$ choices.

A:$\;$ Of the $81$ pairings, $9$ identical will yield $9$ while the remaining $72$ will yield $8$, thus subtract $9\cdot9 +72\cdot8 = 657$

B: $\; (1 - 9)$ are available left of centre, while $(0,1-4, 6-9)$ are available right of centre. $5$ from left has $9$ non-identical partners, while the $8$ others each have one identical and 8 non-identical partners, yielding $[\;8\cdot 9 + 8(9 + 8\cdot8)\;] = 656$ to be subtracted

Final count $= ( 9^4 -657 ) + ( 9^4- 656 ) = 11809$

---

$\boxed { Merry\; Christmas\; and\; happy\; new\; year\; to\; all\; !}$