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

combinatoricsdiscrete mathematicsinclusion-exclusion

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?

Best Answer

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.

Related Question