Amount of numbers $n \in \{1,\ldots,9999\}$ such that there aren't $2$ consecutive odd digits

Question

I want to find out the amount of numbers $n \in \{1,\ldots,9999\}$ such that there aren't $2$ consecutive odd digits. I want to use the principle of inclusion and exclusion.

There are 9999 numbers in $\{1,\ldots,9999\}$.

$n=ABCD$

$A_1:=\{n\in \mathbb N:n<10000,\ A,B \mathrm\ {odd}\}$

$A_2:=\{n\in \mathbb N:n<10000,\ B,C \mathrm\ {odd}\}$

$A_3:=\{n\in \mathbb N:n<10000,\ C,D \mathrm\ {odd}\}$

I don't really know how to deal with the fact that $n$ could have less than $4$ digits.

$|A_1|=5\cdot5\cdot10\cdot10$

$|A_2|=10\cdot5\cdot5\cdot10+5\cdot5\cdot10$ (the second summand because $n$ in $A_2$ could have $3$ digits instead of $4$, but I don't know if this is correct)

$|A_3|=10\cdot10\cdot5\cdot5+10\cdot5\cdot5+5\cdot5$ (4 digits, 3 digits or 2 digits)

$|A_1\cap A_2|=5\cdot5\cdot5\cdot10$

$|A_1\cap A_3|=5\cdot5\cdot5\cdot5$

$|A_2\cap A_3|=10\cdot5\cdot5\cdot5+5\cdot5\cdot5$

$|A_1\cap A_2\cap A_3|=5\cdot5\cdot5\cdot5$

Are my calculations correct?

Answer 1

Thanks to N.F.Taussig for suggesting that my answer should be self-contained. I have edited my answer. Also, thanks to N.F. Taussig for indicating an analytical error that I made. I have corrected the answer.

---

You can assume that the numbers run from $0$ through $9999$, to ease the calculations. Then, at the end, you can adjust for $0$ being considered.

Further, since what is being enumerated is two consecutive odd digits, it is harmless to adopt the simplification that all numbers are zero filled on the left.

---

Re my two comments, following the question, this is how I would employ Inclusion-Exclusion:

My approach will be to enumerate all possible occurrences of at least two consecutive odd digits. Then, I will deduct this from $(9999)$.

Edit
The foundation of Inclusion-Exclusion, is that by counting - deducting - adding back, each pertinent occurrence (in this case of having at least one pair of consecutive odd integers) ends up being counted once.

So, in this particular problem, I made a mistake in not analyzing closely, how many times various intersections are counted in my enumerations of $T_1, T_2, T_3$, as discussed below. I have added discussion.

In the discussion below, I will use
o-o-e-e
(for example) to indicate that (reading from the left), the first two digits are odd and the second two digits are even.

Similarly, I will use
o-o-o-e
to indicate that the first three digits are odd and the last digit is event.

---

Number of ways first two digits odd (reading the digits from left to right):
$5^2 \times 10^2.$
Multiply the above by $3$, since you are also enumerating digits $2,3$ odd and digits $3,4$ odd.
$T_1 = 3 \times 5^2 \times 10^2 = 7500.$

In determining how many collections of $4$ digits to deduct, re intersections, consider the following intersections, which are inherent in my enumeration of $T_1$:

o-o-e-e $~:~$ counted once.
e-o-o-e $~:~$ counted once.
e-e-o-o $~:~$ counted once.
o-o-o-e $~:~$ counted twice.
e-o-o-o $~:~$ counted twice.

o-o-o-o $~:~$ counted three times.
This was my oversight.

---

Deduct number of ways that digits $1,2,3$ are odd, or that digits $2,3,4$ are odd:
$T_2 = 2 \times 5^3 \times 10 = 2500.$

Edit
Re my oversight, I must also consider having at least two pairs of odd integers, where the pairs are represented by $(1,2)$ and $(3,4)$.

So, the corrected computation of $T_2$ is:
$T_2 = \left[2 \times 5^3 \times 10\right] + 5^4 = 3125.$

o-o-o-e $~:~$ deducted once.
e-o-o-o $~:~$ deducted once.
o-o-o-o $~:~$ deducted three times.

At this point, everything is all square, with all pertinent intersections having been counted exactly once, except that (now), o-o-o-o has been counted three times and deducted three times.

---

Add back number of ways that all 4 digits are odd.
$T_3 = 5^4 = 625.$

Final computation:

$$T_1 - T_2 + T_3 = 7500 - 3125 + 625 = 5000.$$

Edit
Confess: after reading N.F. Taussig's comments following my answer, I sanity checked with a Java program.

---

Since you are actually interested in computation where there aren't two consecutive odd digits, you actually want:

$$9999 - 5000 = 4999.$$

Answer 2

Method 1: We will work with positive integers. To do so, we must consider the cases of one-digit, two-digit, three-digit, and four-digit positive integers separately and take into account the fact that the leading digit cannot be zero.

Let's consider the case of four-digit positive integers. We will subtract the number of positive integers with a pair of consecutive odd digits from the total number of four-digit positive integers.

Since the thousands digit cannot equal zero, there are nine ways to fill the thousands digit. Since there are no such restrictions on the remaining digits, they can each be filled in $10$ ways. Hence, there are $$N = 9 \cdot 10 \cdot 10 \cdot 10 = 9000$$ four-digit positive integers.

Any four-digit positive integer has the form $n = 1000a + 100b + 10c + d$, where $a \neq 0$. Let's define \begin{align*} A_1 & = \{n \mid a, b~\text{are odd}\}\\ A_2 & = \{n \mid b, c~\text{are odd}\}\\ A_3 & = \{n \mid c, d~\text{are odd}\} \end{align*}

$|A_1|$: Since the first two digits must be odd, there are five choices for the thousands digit and five choices for the hundreds digit. Since there are no restrictions on the remaining digits, there are ten choices for the tens digit and ten choices for the units digit. Hence, $$|A_1| = 5 \cdot 10 \cdot 10 \cdot 10$$

$|A_2|$: Since the leading digit cannot equal zero, there are nine choices for the thousands digit. Since the second and third digits must be odd, there are five choices for the hundreds digit and five choices for the tens digit. Since there are no restrictions on the units digit, there are ten choices for the units digit. Hence, $$|A_1| = 9 \cdot 5 \cdot 5 \cdot 10$$

$|A_3|$: Since the leading digit cannot equal zero, there are nine choices for the thousands digit. Since there are no restrictions on the hundreds digit, there are ten choices for the hundreds digit. Since the tens and units digits are odd, there are five choices for the tens digit and five choices for the units digit. Hence, $$|A_3| = 9 \cdot 10 \cdot 5 \cdot 5$$

$|A_1 \cap A_2|$: Since the first and second digits must be odd and the second and third digits must be odd, the first three digits must be odd. Hence, there are five choices for the thousands digit, five choices for the hundreds digit, and five choices for the tens digit. Since there are no restrictions on the units digit, there are ten choices for the units digit. Hence, $$|A_1 \cap A_2| = 5 \cdot 5 \cdot 5 \cdot 10$$

$|A_1 \cap A_3|$: Since the first and second digits must be odd and the third and fourth digits must be odd, all four digits must be odd. Thus, there are five choices for each of the four digits. Hence, $$|A_1 \cap A_3| = 5 \cdot 5 \cdot 5 \cdot 5$$

$|A_2 \cap A_3|$: Since the leading digit cannot equal zero, there are nine choices for the thousands digit. Since the second and third digits must be odd and the third and fourth digits must be odd, the last three digits must be odd. Thus, there are five choices for the hundreds digit, five choices for the tens digit, and five choices for the units digit. Hence, $$|A_2 \cap A_3| = 9 \cdot 5 \cdot 5 \cdot 5$$

$|A_1 \cap A_2 \cap A_3|$: Since the first and second digits must be odd, second and third digits must be odd, and third and fourth digits must be odd, all four digits must be odd. Thus, there are five choices for each of the four digits. Hence, $$|A_1 \cap A_2 \cap A_3| = 5 \cdot 5 \cdot 5 \cdot 5$$

Thus, by the Inclusion-Exclusion Principle, the number of four-digit positive integers in which no two consecutive digits are odd is \begin{align*} N - |A_1 \cup A_2 \cup A_3| & = N\\ & \quad - (|A_1| + |A_2| + |A_3|\\ & \qquad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3|\\ & \quad\qquad + |A_1 \cap A_2 \cap A_3|)\\ & = N\\ & \quad - |A_1| - |A_2| - |A_3|\\ & \qquad + |A_1 \cap A_2| + |A_1 \cap A_3| + |A_2 \cap A_3|\\ & \quad\qquad - |A_1 \cap A_2 \cap A_3|\\ & = 9 \cdot 10 \cdot 10 \cdot 10\\ & \quad - 5 \cdot 5 \cdot 10 \cdot 10 - 9 \cdot 5 \cdot 5 \cdot 10 - 9 \cdot 10 \cdot 5 \cdot 5\\ & \qquad + 5 \cdot 5 \cdot 5 \cdot 10 + 5 \cdot 5 \cdot 5 \cdot 5 + 9 \cdot 5 \cdot 5 \cdot 5\\ & \quad\qquad - 5 \cdot 5 \cdot 5 \cdot 5\\ & = 4375 \end{align*} I will leave it to you to handle the cases of one-digit, two-digit, and three-digit positive integers.

Method 2: As user2661923 astutely pointed out, by appending leading zeros as needed, each nonnegative integer with up to four digits can be represented as a four-digit decimal string. For instance, $17$ can be represented as $0017$. Moreover, since $0$ is even, appending leading zeros does not introduce any additional numbers with two consecutive odd digits.

We will subtract the number of four-digit decimal strings with at least two consecutive odd digits from the total number of four-digit decimal strings to find the number of nonnegative integers with up to four digits which do not have at least two consecutive odd digits. Since the string $0000$ does not contain at least two consecutive odd digits and represents the number $0$, we will have to subtract $1$ from our answer since we want to find the number of positive integers with up to four digits which do not have at least two consecutive odd digits.

There are $$N = 10 \cdot 10 \cdot 10 \cdot 10$$ four-digit decimal strings.

If the decimal string has the form $n = abcd$, where $a, b, c, d$ are decimal digits, let's define \begin{align*} A_1 & = \{n \mid a, b~\text{are odd}\}\\ A_2 & = \{n \mid b, c~\text{are odd}\}\\ A_3 & = \{n \mid c, d~\text{are odd}\} \end{align*}

$|A_1|$: Since the first two digits must be odd, there are five choices for each of the first two digits. Since there are no such restrictions on the last two digits, there are ten choices for each of the remaining digits. Hence, $$|A_1| = 10 \cdot 10 \cdot 5 \cdot 5$$

By symmetry, $$|A_1| = |A_2| = |A_3|$$

$|A_1 \cap A_2|$: If the first and second digits must be odd and the second and third digits must be odd, then the first three digits must be odd. Thus, there are five choices for each of those digits. Since there is no restriction on the fourth digit, there are ten choices for the fourth digit. Hence, $$|A_1 \cap A_2| = 5 \cdot 5 \cdot 5 \cdot 10$$ By symmetry, $$|A_1 \cap A_2| = |A_2 \cap A_3|$$

$|A_1 \cap A_3|$: Since the first and second digits must be odd and the third and fourth digits must be odd, all four digits must be odd. Hence, there are five choices for each digit, so $$|A_1 \cap A_3| = 5^4$$

$|A_1 \cap A_2 \cap A_3|$: Since the first and second digits must be odd, second and third digits must be odd, and third and fourth digits must be odd, all four digits must be odd. Thus, there are five choices for each digit. Hence, $$|A_1 \cap A_2 \cap A_3| = 5^4$$

By the Inclusion-Exclusion Principle, the number of nonnegative integers with up to four digits which have no consecutive odd digits is
\begin{align*} N - |A_1 \cup A_2 \cup A_3| & = N\\ & \quad - (|A_1| + |A_2| + |A_3|\\ & \qquad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3|\\ & \quad\qquad + |A_1 \cap A_2 \cap A_3|)\\ & = N\\ & \quad - |A_1| - |A_2| - |A_3|\\ & \qquad + |A_1 \cap A_2| + |A_1 \cap A_3| + |A_2 \cap A_3|\\ & \quad\qquad - |A_1 \cap A_2 \cap A_3|\\ & = 10 \cdot 10 \cdot 10 \cdot 10\\ & \quad - 5 \cdot 5 \cdot 10 \cdot 10 - 10 \cdot 5 \cdot 5 \cdot 10 - 10 \cdot 10 \cdot 5 \cdot 5\\ & \qquad + 5 \cdot 5 \cdot 5 \cdot 10 + 5 \cdot 5 \cdot 5 \cdot 5 + 10 \cdot 5 \cdot 5 \cdot 5\\ & \quad\qquad - 5 \cdot 5 \cdot 5 \cdot 5\\ & = 5000 \end{align*} Since one of these nonnegative integers with at most four digits which have no consecutive odd digits is $0$, we must subtract $1$ to obtain $$5000 - 1 = 4999$$ positive integers with at most four digits which have no consecutive odd digits.

Answer 3

An answer of almost half the numbers appears suspicious to me, so here is a direct count using another method:

If we consider the number string $0000\;\; thru\;\; 9999$, and finally exclude $0000,$ there are eight types of number strings that satisfy the criteria, viz

$\displaylines{o-e-e-e\\ o-e-o-e\\o-e-e-o\\e-o-e-e\\ e-e-o-e\\e-e-e-o\\ e-o-e-o\\ e-e-e-e}$

Thus total valid numbers are $8\cdot5^4 - 1 = 4999$

which confirms the answers using inclusion-exclusion