How many strings of five decimal digits must be starting or ending with an odd number?

Question

How many strings of five decimal digits must be starting or ending with an odd number?

Everywhere, I looked over the internet they used this method:

Thus, number of ways $=5 \cdot 10 \cdot 10 \cdot 10 \cdot 10=50000$ ways.

Thus, number of ways $=10 \cdot 10 \cdot 10 \cdot 10 \cdot 5=50000$ ways.

Therefore, the strings of five decimal digits that start with an odd number or end with an odd number $= 50000+50000=100000$.

My instructor says that this is wrong and that the inclusion-exclusion principle is used: $A+B- (A~\text{and}~B)$.

I am confused which one is true now. Does inclusion-exclusion rule really apply here?

Answer 1

You are starting off correctly: there are, indeed,

• $5 \cdot 10^4$ ways of choosing a $5$-digit number with an initial odd digit, and
• $10^4 \cdot 5$ ways of choosing a $5$-digit number with a trailing odd digit.

However, you have double counted a lot of numbers. For example, $51237$ is a $5$-digit number which both starts and ends with an odd number. Thus it was counted both in the first group and in the second group. In general, any number which both begins and ends with an odd number has been counted twice, so we need to subtract off a term corresponding to the double counting. There are

• $5 \cdot 10^3 \cdot 5$ numbers which have been double counted,

so subtract off this number. Therefore the total number of five digit numbers with either a leading or trailing odd digit is

\begin{align} &\underbrace{5\cdot 10 \cdot 10 \cdot 10 \cdot 10}_{\text{odd first digit}} + \underbrace{10 \cdot 10 \cdot 10 \cdot 10 \cdot 5}_{\text{odd last digit}} - \underbrace{5\cdot 10 \cdot 10 \cdot 10 \cdot 5}_{\text{odd first and last digit}}\\ &\qquad\qquad = 50000 + 50000 - 25000 \\ &\qquad\qquad = 75000. \end{align}

Note that I have not explicitly used the Inclusion-Exclusion Principle here. Rather, I have carefully argued about which terms are double counted and why this has been done. This is a nice exercise for motivating (or perhaps justifying) Inclusion-Exclusion, rather than for directly applying it. However, the entire structure of the argument could be more succinctly written by appealing directly to Inclusion-Exclusion.

Answer 2

Method 1: We do a direct count.

There are three possibilities:

• The first digit of the string is odd and the last digit of the string is even.
• The first digit of the string is even and the last digit of the string is odd.
• Both the first and last digits of the string are odd.

In each case, there are five choices for the first and last digits and ten choices for each of the middle three digits. Since these three cases are mutually exclusive and exhaustive, there are $$3 \cdot 5 \cdot 10 \cdot 10 \cdot 10 \cdot 5 = 75,000$$ five-digit decimal strings in which the first digit or last digit is odd.

Method 2: We correct your attempt.

You first calculated the number of five-digit decimal strings in which the first digit is odd, then calculated the number of five-digit decimal strings in which the last digit is odd, then added the two results. However, in doing so, you counted the five-digit decimal strings in which both the first and last digits are odd twice, once when you counted the strings in which the first digit is odd and once when you counted the strings in which the last digit is odd. We only want to count such strings once, so we must subtract them from the total.

If we let $A$ be the set of five-digit decimal strings in which the first digit is odd and $B$ be the set of five-digit decimal strings in which the last digit is odd, then the number of five-digit decimal strings in which the first digit or last digit is odd is $|A \cup B|$. By the Inclusion-Exclusion Principle, $$|A \cup B| = |A| + |B| - |A \cap B|$$

$|A|$: There are $5 \cdot 10 \cdot 10 \cdot 10 \cdot 10$ five-digit decimal strings in which the first digit is odd.

$|B|$: There are $10 \cdot 10 \cdot 10 \cdot 10 \cdot 5$ five-digit decimal strings in which the last digit is odd.

$|A \cap B|$: There are $5 \cdot 10 \cdot 10 \cdot 10 \cdot 5$ five-digit decimal strings in which both the first and last digits are odd.

Hence, by the Inclusion-Exclusion Principle, the number of five digit decimal strings in which the first or last digit is odd is \begin{align*} |A \cup B| & = |A| + |B| - |A \cap B|\\ & = 5 \cdot 10 \cdot 10 \cdot 10 \cdot 10 + 10 \cdot 10 \cdot 10 \cdot 10 \cdot 5 - 5 \cdot 10 \cdot 10 \cdot 10 \cdot 5\\ & = 75,000 \end{align*} Observe that correcting your count does require the use of the Inclusion-Exclusion Principle.

Method 3: We use the Complement Principle.

The only strings which do not have an odd number in the first or last positions are those which have an even number in both the first and last positions.

There are $10^5$ five-digit decimal strings.

There are $5 \cdot 10 \cdot 10 \cdot 10 \cdot 5$ five-digit decimal strings with an even number in both the first and last positions.

Hence, there are $$10^5 - 5 \cdot 10 \cdot 10 \cdot 10 \cdot 5 = 75,000$$ five-digit decimal strings in which the first digit or last digit is odd.

This is the method that @paw88789 used in his/her answer.

Answer 3

Another approach (that doesn't use inclusion-exclusion): Count the failures and subtract. (Where a success is having at least one of the first and last digits being odd.)

A failure has even first digit and even last digit. So the number of failures is $5\cdot 10\cdot 10\cdot 10\cdot 5=25000$.

So the number of successes is $100000-25000=75000$.