# PIE conflicts with Complementary counting

How many $4$-digit numbers have at least two consecutive digits that are the same?

I solved this problem in two ways, as are shown below:

PIE: We apply the Principle of Inclusion-Exclusion. This principle tells us that the overall number of desirable $4$ digit numbers is $\text{Number with one pair of two consecutive digits}-\text{Number with two pairs of two consecutive digits}+\text{Number with 3 pairs of two consecutive digits}.$

We solve the third case first, as it is the most simple. If three pairs are the same, all the digits are the same. Thus, there are $9$ digits possible, as $0000$ is not a $4$ digit number. Thus, there are $9$ numbers.

Now, we solve the first case. We either have the first two digits the same, or the second or third two. In the first subcase, we have $9$ choices for the first two digits, as the first cannot be a $0$, and $10$ choices for each of the last two digits, as they are unrestricted. Thus, there are $9\cdot10^2$ in the first subcase.

In the second subcase, there are $9$ choices for the first number, then $10$ choices for the digit shared by $2$ of the last $3$ digits. There are then $10$ choices for the last digit, which yields $9\cdot 10^2$ possibilities for each subcase of the subcase, so $18\cdot 10^2$ possibilites overall.

Thus, in the first main case, there are $9\cdot 10^2+18\cdot 10^2$ cases overall, which yields $2700$ cases.

Finally, we attack the second case, where there are two pairs of equal digits. The two subcases are that the two digits are a pair of three in a row, or are separated in a block of four in a row. This is three subcases overall, which is correct because we are choosing $\binom{3}{2}$ from the $3$ possible equal pairs of digits.

In the first subcase, we can have the three digits at the beginning of the $4$ numbers or at the end. If they are at the beginning, they have $9$ possibilities as they cannot be $0$, and the last digit has $10$. If they are at the end, they have $10$ possibilities and the remaining digit has $9$.

In the second subcase, there are $9$ possibilities, for this is simply the same as the three pairs case.

Thus, we get $90+90+9=189$ possibilities overall for the second case.

Summing the three cases, we get $189+2700+9=2898$ possibilities.

Complementary counting:

We use complementary counting and subtract the number of $4$ digit numbers with no digits the same from the total number of $4$ digit numbers. There are $9\cdot 10^3=9000$ 4 digit numbers and there are $9\cdot9\cdot8\cdot7$ 4 digit numbers with no digits the same. Thus, there are $9000-9\cdot9\cdot8\cdot7=4464$ numbers.

Why are these two, supposedly correct, methods giving me different answers? Where did I make my error?

Thank you!

You want to test every number between 1000 and 9999 for the condition that either the first digit equals the second, or the second equals the third, or the third equals the fourth.

Your inclusion exclusion principal strategy is incorrect. If implemented correctly, it would return the number of four digit numbers that either have exactly 1 or 3 pairs, but this is not what we want. You also counted wrong here

You complementary counting method is also incorrect. 1231 is not an acceptable number for your count, but your method will include it. This is why your result is too high.

To correctly use inclusion exclusion:

First we consider all the four digit numbers whose first two digits are the same. Lets call this set of numbers $F_1$. You correctly count the size of this at 900.

Next we consider all the four digit numbers whose second two digits are the same. Lets call this set $F_2$. The middle digits might be 00, 11, ..., or 99 -- all in all 10 possibles. The first digit can be 1-9 and the last digit can be 0-9. 10*9*10 gives us another 900 possibles for this set.

Now we need all the four digit numbers whose third two digits are the same. Lets call this set $F_3$. There are 9*10*10 or 900 numbers in this set as well.

Unfortunately $F_1$, $F_2$ and $F_3$ are not disjoint sets. Therefore we must use the inclusion exclusion formula: $$|F_1 \cup F_2 \cup F_3| = |F_1| + |F_2| + |F_3| - |F_1 \cap F_2| - |F_1 \cap F_3| - |F_2 \cap F_3| + |F_1 \cap F_2 \cap F_3|$$

We have some more counting to do.

For $F_1 \cap F_2$ we have numbers of the form, 111x, 222x, ... 999x. 90 of these.

For $F_1 \cap F_3$ we have numbers of the form XXYY, again 90 of these.

For $F_2 \cap F_3$ we have numbers of the form x000, x111, ... x999. Again, 90 of these.

For $F_1 \cap F_2 \cap F_3$ we have numbers of the form XXXX, so 9 of these.

Plug it all up and we have 900+900+900-90-90-90+9 or 2439.

A tiny Java program to check your work:

public static void main(String[] args) {
int count = 0;
for (int a=1000; a<10000; a++) {
String b = Integer.toString(a);
char[] c = b.toCharArray();

if(c[0]==c[1] || c[1] == c[2] || c[2] == c[3]) {
count++;
}

}

System.out.println(count);
}


We can solve this problem using the Complement Principle.

As you noted, there are $9000$ four digit positive integers. We must subtract the number of four digit numbers in which no two consecutive digits are equal. If no two digits are consecutive, there are nine ways of selecting the thousands digit (since we cannot use $0$), which leaves us nine ways to select the hundreds digit (since it can be any digit other than the thousands digit), nine ways of selecting the tens digit (since it can be any digit other than the hundreds digit), and nine ways of selecting the units digit (since it can be any digit other than the tens digit). Therefore, there are $$9000 - 9^4 = 9000 - 6561 = 2439$$ positive integers with four digits in which at least two consecutive digits are the same.