Problem Statement: How many 4-digit positive integers are there for which there are no repeated digits, or for which there may be repeated digits, but all are odd?
My original understanding of the problem was that all repeated digits must be odd. I later came to think that the author actually meant to say all digits (not just the repeated ones) must be odd.
This is my solution for my initial understanding:
For the first part, there are $9 \cdot 9 \cdot 8 \cdot 7$ $4$-digit integers that don't contain any repeated digits. (We start with $9$ because we can't place $0$ in the first position.)
And now the second part. For the sake of symmetry, let's assume $0$ is allowed as the first digit. This means that there are $10^4 – (9 \cdot 9 \cdot 8 \cdot 7)$ $4$-digit integers with at least one repeated digit. We chose to allow $0$ as the first digit, so that we can have an equal number of $4$-digit integers with odd digits repeated as $4$-digit integers with even digits repeated. We know we are only allowed odd repeated digits so we must divide $10^4 – (9 \cdot 9 \cdot 8 \cdot 7)$ by $2$. In addition, we also have to notice that there are some $4$-digit integers that contain both odd repeated digits and even repeated digits. Those integers have this form: "aabb", "abba", "abab", "baba". To be consistent, we'll allow these integers to start with $0$ as well, but this is not a problem since we'll ignore the integers that contain repeated even digits. Each "a" can be one of $5$ odd digits and each "b" can be one of $5$ even digits. This means we have an extra $(5 \cdot 5) \cdot 4$, $4$-digit integers with even digits repeated. We've already removed half of them (when we divided by $2$) so we only need to remove another half.
So the final result is $$9 \cdot 9 \cdot 8 \cdot 7 – \frac{10^4 – 9 \cdot 9 \cdot 8 \cdot 7}{2} – \frac{5 \cdot 5 \cdot 4}{2} = 7218$$
My first question is: Given my potentially flawed assumption, is this solution correct? And if it is correct, can you think of an easier way to go about it?
The solution for what I think the author actually asked (If the integers contain repeated digits all the digits in the integer must be odd):
There are $9 \cdot 9 \cdot 8 \cdot 7$ $4$-digit integers that don't contain any repeated digits.
We have $5^4$ $4$-digit integers that can have odd digits repeated.
There is a set that intersects the previously mentioned sets. That is the set formed by all the $4$-digit integers with odd digits that don't repeat.
So the final result is: $9 \cdot 9 \cdot 8 \cdot 7 + 5^4 – 5 \cdot 4 \cdot 3 \cdot 2 = 5041$.
As for my second question: Is this solution correct and is this what you understood from the problem statement as well?
Mention: This problem comes from The Book of Proof (Section 3.5 problem 2)
Best Answer
Since this problem appears in a section on the Inclusion-Exclusion Principle, your first interpretation is almost certainly not what the author intended.
As N. Shales pointed out, one interpretation could be:
As you correctly calculated, the number of four-digit positive integers with no repeated digits is $9 \cdot 9 \cdot 8 \cdot 7 = 4536$. The number of odd four-digit integers is $9 \cdot 10 \cdot 10 \cdot 5 = 4500$ since there are five choices for the units digit (which must be odd), nine choices for the thousands digit (since zero is excluded), and ten choices each for the hundreds and tens digits. The number of odd numbers with no repeated digits is $8 \cdot 8 \cdot 7 \cdot 5 = 2240$ since we have five choices for the units digit, eight choices for the thousands digit (which can be neither zero nor equal to the units digit), eight choices for the hundreds digit (which cannot be equal to the thousands digit or the units digit), and seven choices for the tens digit (which cannot be equal to the thousands digit, hundreds digit, or units digit). By the Inclusion-Exclusion Principle, there are $$9 \cdot 9 \cdot 8 \cdot 7 + 9 \cdot 10 \cdot 10 \cdot 5 - 8 \cdot 8 \cdot 7 \cdot 5 = 4536 + 4500 - 2240 = 6796$$ four-digit positive integers in which no digit is repeated or are odd numbers that contain repeated digits.
This is your second interpretation. You correctly calculated that there are $$9 \cdot 8 \cdot 7 \cdot 6 + 5^4 - 5 \cdot 4 \cdot 3 \cdot 2 = 4536 + 625 - 120 = 5041$$ such numbers. We can confirm this by calculating the number of four-digit positive integers consisting of only odd digits that contain a repeated digit. This is a bit messy. We consider cases:
Exactly one digit is used in all four positions: There are $5$ such numbers since there are $5$ odd digits.
Exactly two digits are used, with one used three times and the other once: There are $5$ choices for the repeated digit, $4$ choices for the remaining digit, and $4$ choices for the placement of the digit that is used exactly once, so there are $$5 \cdot 4 \cdot 4 = 80$$ such numbers.
Exactly two digits are used, with each used twice: There are $\binom{5}{2}$ ways of choosing the two odd digits and $\binom{4}{2}$ ways to select the positions occupied by the larger of these two digits. Hence, there are $$\binom{5}{2}\binom{4}{2} = 60$$ such numbers.
Exactly three digits are used, with one number used twice: There are five ways of selecting the repeated digit, $\binom{4}{2}$ ways of selecting the positions occupied by these digits, four ways of filling the leftmost open position, and three ways of filling the remaining position. Hence, there are $$5 \cdot \binom{4}{2} \cdot 4 \cdot 3 = 360$$ such numbers.
Thus, in total, there are $$5 + 80 + 60 + 360 = 505$$ four-digit integers consisting of only odd digits that contain repeated digits. Adding this to the $4536$ four-digit integers that do not contain repeated digits yields the $$4536 + 505 = 5041$$ numbers you found more easily by using the Inclusion-Exclusion Principle.
This is your first interpretation. You calculated this incorrectly. Before I explain why, let's calculate the number of four-digit positive integers in which the only repeated digits are odd numbers.
Exactly one odd digit is used in all four positions: As explained above, there are $5$ such numbers.
Exactly two digits are used, with an odd digit used in three of the four positions: We have to consider cases, depending on whether the thousands place is occupied by the repeated digit.
If the thousands place is not occupied by the repeated digit, there are eight choices for the thousands place (since it cannot be zero or the repeated digit) and five choices for the repeated digit. Hence, there are $8 \cdot 5 = 40$ such numbers.
If the thousands place is occupied by the repeated digit, there are $\binom{3}{2}$ ways of selecting the other two positions of that digit, five ways of choosing the digit, and $9$ ways of filling the remaining position. Hence, there are $$\binom{3}{2} \cdot 5 \cdot 9 = 135$$ such numbers.
In total, there are $40 + 135 = 175$ four-digit positive integers in which exactly two digits are used and one odd digit is used in three of the four positions.
Exactly two digits are used, with two odd digits each filling two of the four positions: There are $\binom{5}{2}$ ways of selecting two of the five odd digits and $\binom{4}{2}$ ways of choosing which two of the four positions will be filled by the larger of them. Hence, there are $$\binom{5}{2}\binom{4}{2} = 60$$ such numbers.
Exactly three digits are used, with one odd digit used twice: We have to consider cases, depending on whether the repeated digit is used in the thousands place.
If the thousands place is not occupied by the repeated digit, there are eight ways to fill the thousands place (since it cannot be zero or the repeated digit). There are five choices for the repeated digit, $\binom{3}{2}$ ways of selecting which two of the remaining three positions it will fill, and eight choices for the remaining digit (since it cannot be the repeated digit or the thousands digit). Hence, there are $$8 \cdot 5 \cdot \binom{3}{2} \cdot 8 = 960$$ such numbers.
If the thousands place is occupied by the repeated digit, there are five ways to fill the thousands place (since it must be odd), three ways to select the other digit occupied by the repeated digit, nine ways to fill the leftmost open position, and eight ways to fill the remaining open position. Hence, there are $$5 \cdot 3 \cdot 9 \cdot 8 = 1080$$ such numbers.
In total, there are $960 + 1080 = 2040$ four-digit positive integers using exactly three digits in which one odd digit is repeated.
Total: Adding these cases yields $$5 + 175 + 60 + 2040 = 2280$$ four-digit positive integers containing repeated digits in which the only digits that are repeated are odd digits.
Your tried to use the Inclusion-Exclusion Principle to do this. Let's see what went wrong.
As you noted, there are $10^4$ four-digit strings. However, the number of such strings with no repeated digits is $10 \cdot 9 \cdot 8 \cdot 7 = 5040$. Hence, there are $$10^4 - 10 \cdot 9 \cot 8 \cdot 7 = 1000 - 5040 = 4960$$ such strings with repeated digits. You attempted to use symmetry to eliminate those that contain repeated even digits by dividing by $2$. Doing so yields $2480$. As you realized, we are still counting strings with two even and two odd digits. There are actually $$5 \cdot 5 \cdot \binom{4}{2} = 150$$ such strings since there are five choices of even digit, five choices of odd digit, and $\binom{4}{2}$ ways of selecting the positions of the even digit. Half of these were eliminated when we divided by $2$, leaving $75$ more to be eliminated. This leaves us with $$2480 - 75 = 2405$$ four-digit strings which contain only repeated odd digits. However, not all these strings are four-digit positive integers since the first digit may be zero. We must eliminate these.
Three-digit positive integers in which a single odd digit is used in all three positions: There are $5$ such numbers since there are five odd digits.
Three-digit odd positive integers in which exactly two digits are used and an odd digit is repeated: Notice that we have already eliminated numbers in which a zero appears since it would be a repeated even digit (as zero also occupies the thousands place). There are five ways of choosing the repeated digit, $\binom{3}{2}$ ways of selecting two of the three locations for that digit, and eight ways to fill the remaining digit. Hence, there are $$5 \cdot \binom{3}{2} \cdot 8 = 120$$ such numbers.
Hence, there are $$\frac{10^4 - 10 \cdot 9 \cdot 8 \cdot 7}{2} - \frac{5 \cdot 5 \cdot \binom{4}{2}}{2} - 5 - 5 \cdot \binom{3}{2} \cdot 8 = 2480 - 75 - 5 - 120 = 2280$$ four-digit positive integers in which the only repeated digits are odd, which agrees with the result we obtained above.
Thus, there are a total of
$$4536 + 2280 = 6816$$ four-digit positive integers in which no digit is repeated or the only digits that are repeated are odd numbers.