# How many five-digit numbers do not have three consecutive digits the same?

How many five-digit numbers do not have three consecutive digits the same? Also, the initial digits might be $0$, but I'm not sure how that changes the answer.

This is the formula I've come up with for solving this problem. Total number of numbers - $A - B - C + A \cap B + B \cap C + A \cap C - A \cap B \cap C$ $$10^5 - (10^3 \cdot 3) + (10^2 \cdot 2) - 10$$

So I have set $A$, positions 1 2 3 are filled; set $B$, positions 2 3 4 are filled; set $C$, positions 3 4 5 are filled; so each set will have $10 \cdot 10 \cdot 10$ subsets of numbers that have $3$ consecutive numbers.

I know that their should be double counting because having consecutive numbers in positions 1 2 3 4 and 2 3 4 5 should be added back, and consecutive numbers 1 2 3 4 5 will need to be subtracted.

So, I get $$10^5 - (10^3 \cdot 3) + (10^2 \cdot 2) - 10 = 100000 - 3000 + 200 - 10 = 97190$$

However, this is not the correct answer. What is the correct procedure to solve this problem? Or what way am I to look at counting up the sets?

Thanks

• To subtract the numbers with at least three consecutive digits the same, notice that at most one of 0,1,...,9 can repeat thus. Fix this digit, it can occur 5 times, or exactly 4 times consecutively or exactly 3 times consecutively. – Aravind Oct 17 '15 at 6:58
• Please read this tutorial on how to typeset mathematics on this site. – N. F. Taussig Oct 17 '15 at 8:47

There's one mistake and one possible misinterpretation.

The mistake is that you only substracted $10^2$ twice for $|A\cap B|$ and $|B\cap C|$, but $|A\cap C|$ is missing. This is actually the same as $|A\cap B\cap C|$, since in both cases all five digits have to be equal; so those two cancel and the correct total would be $10^5-3\cdot10^3+2\cdot10^2+10^1-10^1=97200$.

The potential misinterpretation is that the problem may have meant only "proper" five-digit numbers that don't start with a $0$.

• I edited the question for addressing the issue with initial 0. Thanks for pointing that out. So I'm assuming that I'm supposed to count 00000 as a number. – WP0987 Oct 17 '15 at 7:45
• @joriki: Your final result has a typo which should be 97200, a 5-digit number. – P Vanchinathan Oct 17 '15 at 7:58
• @PVanchinathan: Thanks, fixed. – joriki Oct 17 '15 at 8:23
• @WP0987: Yes (which doesn't correspond to the usual meaning of the word "number"). Does the result match the answer you were given? – joriki Oct 17 '15 at 8:26
• Am I misinterpreting the question ? – true blue anil Oct 17 '15 at 10:57

I would do simple subtraction, viz.

all "numbers" - [all 5 digits same + 4 consecutive digits same + 3 consecutive digits same]

e,g, with consecutive 0's, the patterns can be: 00000 , x0000, 0000x, 000xx , x000x and xx000

$10^5 - [ 10 + 2\cdot10\cdot9 + 10\cdot9^2 + 2\cdot 10\cdot9\cdot10 ] = 97200$

• In the last line, the signs are correct; in the second line they're wrong. – joriki Oct 17 '15 at 12:08
• @joriki:Thanks, I think I need coffee ! – true blue anil Oct 17 '15 at 12:11
• @trueblueanil yes 97200 is the correct answer. However, I having trouble understanding the math. 10^5 (all 5 digit numbers) minus [ 10 (all 5 digits same) plus 2⋅10⋅9+10⋅9^2 +2⋅10⋅9⋅10 ]. I'm confused about how the rest of the numbers are derived. – WP0987 Oct 17 '15 at 16:40
• Two patterns with 5 same, oooox and xoooo , 10 choices for the string of o's, but only 9 choices for the x, so $2\cdot10\cdot9$. Three patterns with 3 same, xooox $(10\cdot9^2)$ but in the remaining 2 patterns, xxooo & oooxx the extreme x's have 10 choices. You should be able to figure it out now. – true blue anil Oct 17 '15 at 16:58

This problem can be broken down into two cases-

1. When no consecutive digits are same
2. When two consecutive digits are same

The answer would be the sum of the number of ways of the two indvidual cases.

If f(n) be the answer to the above problem having n number of digits. Then,
f(n) = 9*(f(n-1)+f(n-2))
The equation can be represented in matrix from as, $$\begin{equation*} \begin{bmatrix} f(n) \\ f(n-1) \\ \end{bmatrix} = \begin{bmatrix} 9 & 9 \\ 1 & 0 \\ \end{bmatrix}*\begin{bmatrix} f(n-1) \\ f(n-2) \\ \end{bmatrix} \end{equation*}$$

Solving the recurrence, we get,

$$\begin{equation*} \begin{bmatrix} f(n) \\ f(n-1) \\ \end{bmatrix} = \begin{bmatrix} 9 & 9 \\ 1 & 0 \\ \end{bmatrix}^{n-2}*\begin{bmatrix} f(2) \\ f(1) \\ \end{bmatrix} \end{equation*}$$

Clearly, the base cases are f(1) = 10 and f(2) = 100.
This can now be solved using matrix exponentiation having computation complexity of (k3log(n)) where k=2 (size of the square matrix).

Now, considering the above asked question, plugging n=5 into the recurrence gives,

$$\begin{equation*} \begin{bmatrix} f(5) \\ f(4) \\ \end{bmatrix} = \begin{bmatrix} 9 & 9 \\ 1 & 0 \\ \end{bmatrix}^{3}*\begin{bmatrix} 100 \\ 10 \\ \end{bmatrix} \end{equation*}$$

i.e.,

$$\begin{equation*} \begin{bmatrix} f(5) \\ f(4) \\ \end{bmatrix} = \begin{bmatrix} 891 & 810 \\ 90 & 81 \\ \end{bmatrix}*\begin{bmatrix} 100 \\ 10 \\ \end{bmatrix} \end{equation*}$$

Therefore, $$\begin{equation*} f(5)=891*100+810*10=97200\end{equation*}$$