[Math] How many 7-digit ID numbers do not contain three consecutive sixes.

combinatoricsdiscrete mathematics

I have a homework question in a discrete mathematics class that asks me to determine how many 7-digit id numbers do not contain three consecutive sixes.

It seems clear that I should approach this by determining the number that do have three consecutive sixes and subtracting that from $10^7$, the total number of possibilities.

If it were asking simply for the number of values that contain three sixes, it would simply be $10^4$, or $9^4$ for exactly three sixes. But what's got me thinking is the requirement that they appear consecutively. By sketching out this: 

___  ___  ___  ___  ___  ___  ___ 
 x    x    x                           1
      x    x    x                      2
           x    x    x                 3
                x    x    x            4
                     x    x    x       5

I determined that there are five possible placements, so I'm thinking that the number of values with three consecutive sixes is $5 * 10^4$. But because arrangements 1&4, 1&5 and 2&5 can coincide, this overcounts by $3 *10 = 30$, so I get a final total of $5 * 10^4 – 30$ values with three consecutive sixes.

Questions:

  • Is my basic approach here logically sound?
  • Making that sketch felt awfully "hacky" – is there a mathematical technique I could have used instead – particularly when I'm dealing with bigger values?

Best Answer

You started out just fine by counting the following kinds of numbers:

___  ___  ___  ___  ___  ___  ___ 
 6    6    6                           1
      6    6    6                      2
           6    6    6                 3
                6    6    6            4
                     6    6    6       5

And you’re right that you have to adjust for overcounting. Think of it this way, you’ve counted the numbers in the set $S_1$ of numbers $666????$, $S_2$ of numbers $?666???$, and so on. There are $10,000$ in each set. (Let’s assume ID numbers can begin with the digit $0$.)

Some numbers, however, are in more than one set. There are two kinds of these numbers: the numbers with $4$ or more consecutive sixes and the numbers with two separated groups of consecutive sixes. Let’s use X to mean a non-6 digit and count, beginning with those that have $4$, but not $5$, consecutive sixes.

Numbers of the form $6666X??$ are in $S_1$ and $S_2$.

Numbers of the form $X6666X?$ are in $S_2$ and $S_3$.

Numbers of the form $?X6666X$ are in $S_3$ and $S_4$.

Numbers of the form $??X6666$ are in $S_4$ and $S_5$.

There are 900+810+810+900 of these, and they were counted twice, so we need to subtract $3,420$ from your initial count of $50,000$. Now those with $5$, but not $6$ consecutive sixes. (We haven't considered them in the previous calculation.)

Numbers like $66666X?$, $X66666X$, and $?X66666$. Each was counted three times, and there are $90+81+90=261$ of them. So subtract another $522$.

Next, numbers like $X666666$ and $666666X$ were counted four times, and there are $9+9$ of those, so subtract another $3\cdot18$, and $6666666$ was counted five times, so subtract $4$.

Two separated $666$s occur in numbers like $666X666$ and were counted twice, so subtract $9$.

Summarizing, there are $50,000-3,420-522-54-4-9=45,591$ numbers containing $666$, leaving $9,954,009$ 7-digit numbers (possibly starting with one or more zeros) with no string of three sixes.

The mathematical principle (search and you'll find a general way to solve these problems) is called "inclusion-exclusion." Your initial approach is just what you need to get started with it.

Related Question