# 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