Find the number of numbers with 5 digits that don't have the sequence 17 within them

79 Views Asked by At

This is simillar to another question that was asked on here but with 4 digits instead, I have already seen that question and used the same method, but for some reason I am still getting this question wrong.

Here is my thinking

XXXXX 5 spots

$9*10^4$ total numbers

17XXX

X17XX

XX17X

XXX17

$(10^3+9*10^2+9^2*10+9^3)$ = total number of numbers with 17 in them.

But since we counted some numbers twice

$(10^3+9*10^2+9^2*10+9^3 - 29)$

$9*10^4 - (10^3+9*10^2+9^2*10+9^3 - 29) = 86590$ using calculator

It says my answer is wrong, but I can't figure out what I have failed to take into account.

1

There are 1 best solutions below

3
On

As TonyK pointed out in the comments, you overlooked the fact that while the leading digit cannot be equal to zero, the remaining digits can be equal to zero.

Let $A_i$, $1 \leq i \leq 4$, be the set of five-digit positive integers in which the sequence $17$ appears beginning in the $i$th position.

Since there are $9 \cdot 10^4$ positive integers with five digits, the number of five-digit positive integers in which the sequence $17$ does not appear is $$9 \cdot 10^4 - |A_1 \cup A_2 \cup A_3 \cup A_4|$$ By the Inclusion-Exclusion Principle, \begin{align*} |A_1 \cup A_2 \cup A_3 \cup A_4| & = \sum_{i = 1}^{4} |A_i| - \sum_{1 \leq i < j \leq 4} |A_i \cap A_j|\\ & \qquad + \sum_{1 \leq i < j < k \leq 4} |A_i \cap A_j \cap A_k| - |A_1 \cap A_2 \cap A_3 \cap A_4\\ & = |A_1| + |A_2| + |A_3| + |A_4|\\ & \quad - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_1 \cap A_4| - |A_2 \cap A_3| - |A_2 \cap A_4| - |A_3 \cap A_4|\\ & \qquad + |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_1 \cap A_3 \cap A_4| + |A_2 \cap A_3 \cap A_4|\\ & \quad\qquad - |A_1 \cap A_2 \cap A_3 \cap A_4| \end{align*}

$|A_1|$: Since the sequence $17$ appears in the first two positions, there are $10$ choices for each of the remaining digits. Hence, $|A_1| = 10^3$.

$|A_2|$: Since the sequence $17$ appears in the second and third positions, there are nine choices for the leading digit and $10$ choices for each of the remaining digits. Hence, $|A_2| = 9 \cdot 10^2$.

By symmetry, $|A_2| = |A_3| = |A_4|$.

$|A_1 \cap A_2|$: This means that the sequence $17$ appears in both the first two positions and the second and third positions, which is impossible since the second digit would have to be both $1$ and $7$. Hence, $|A_1 \cap A_2| = 0$.

By symmetry, $|A_1 \cap A_2| = |A_2 \cap A_3| = |A_3 \cap A_4|$.

$|A_1 \cap A_3|$: This means that the sequence $17$ appears in both the first and second positions and third and fourth positions. There are $10$ choices for the fifth position. Hence, $|A_1 \cap A_3| = 10$.

By symmetry, $|A_1 \cap A_3| = |A_1 \cap A_4|$.

$|A_2 \cap A_4|$: This means that the sequence $17$ appears in both the second and third positions and in the fourth and fifth positions. There are $9$ choices for the leading digit. Hence, $|A_2 \cap A_4| = 9$.

Since there cannot be more than two appearances of the sequence $17$ in a five-digit positive integer, each of the remaining terms is equal to zero.

Hence, $$|A_1 \cup A_2 \cup A_3 \cup A_4| = 10^3 + 3 \cdot 9 \cdot 10^2 - 2 \cdot 10 - 9$$ Therefore, the number of five-digit positive integers that do not contain the sequence $17$ is $$9 \cdot 10^4 - 10^3 - 3 \cdot 9 \cdot 10^2 + 2 \cdot 10 + 9 = 86,329$$