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

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 ?

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.

• Could you help me out with why $b_{n+1}$ equals $9a_n + 8b_n$ ? – Aritra Das Aug 2 '15 at 9:41
• @AritraDas: Starting from a number with identical first and last digits, you can append any of the $9$ other digits to arrive at one with different first and last digits. Starting from one with different first and last digits, you only have $8$ possibilities, since you can choose neither the last (since that would give two consecutive identical digits) nor the first (since that would give identical first and last digits). – joriki Aug 2 '15 at 9:43
• Very nice approach, avoiding painful enumeration. (+1) I wonder whether there is some way to avoid enumeration for this: math.stackexchange.com/questions/1379100/… – true blue anil Aug 3 '15 at 3:42
• @trueblueanil: I added an answer there. It's not very elegant, and it can't be applied manually, but it solves the problem computationally for arbitrarily large sets without enumerating the combinations. – joriki Aug 3 '15 at 5:47
• Thx. I have a feeling that it is a gambling set up. – true blue anil Aug 3 '15 at 8:13

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.

Let the number be written as $$abcde$$.

Case 1:

When $$e=0$$

The first 3 digits $$a,b,c$$ can be filled in $$9\times 9\times 9$$ ways out of which

$$c=0$$ in $$9\times 8\times 1$$ ways in which case $$d$$ has $$9$$ choices and

$$c\neq 0$$ in $$9\times 9\times 9-9\times 8\times 1=657$$ ways in which case $$d$$ has $$8$$ choices.

Therefore, number of numbers ending in $$0$$ and no two consecutive digits being identical $$=9\times 8\times1\times 9+657\times 8=5904$$

Case 2:

When $$e=5$$

If $$c=5$$ then two sub-cases arise

Sub-case 1

If $$a\neq5$$

In which case the first three digits $$a,b,c$$ can be filled in $$8\times 8\times 1=64$$ways.

Sub-case 2

If $$a=5$$

In which case the first three digits $$a,b,c$$ can be filled in $$1\times 9\times 1=9$$ways.

In both the sub-cases $$d$$ has $$9$$ choices.

If $$c\neq 5$$ then the first three digits $$a,b,c$$ can be filled in $$\big(729-64-9=656\big)$$ ways in which case $$d$$ has $$8$$ choices.

Therefore number of numbers ending in$$5$$ and no two consecutive digits being identical$$=(64+9)\times 9+656\times 8=5905$$

Thus total number of $$5$$ digit numbers which are divisible by $$5$$ and no two consecutive digits being identical $$=5904+5905=11809$$

Required probability$$=\frac{11809}{90000}$$

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\; !}$

• Amazing, Happy New Year to you too! – Aritra Das Jan 5 '18 at 18:37