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

Question

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

Answer 1

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$.

Answer 2

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$

Answer 3

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 (k³log(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*}