2
$\begingroup$

So I'm revising my counting, and I looked at this problem and after a little bit of brainstorming I came up with the following solution.

Number of 8 digit numbers containing both a 5 and a 6
= Number of 8 digit numbers - Number of 8 digit numbers lacking both a 5 and a 6
= 90000000 - $7 * 8^7$
= 75319936

Does this seem right? Can anyone point out an easier way to solve a problem like this.

Thank you

1 Answers 1

6

A number not containing both 5 and 6, either doesn't contain 5 or doesn't contain 6 (or both). For example, the number $5$ doesn't contain both $5$ and $6$. However, it does contain $5$. Always try your ideas on things you can count on your own!

You need to use inclusion-exclusion:

  • Start with all $9\cdot 10^7$ numbers with exactly $8$ digits.
  • Remove all $8\cdot 9^7$ numbers not containing $5$.
  • Remove all $8\cdot 9^7$ numbers not containing $6$.
  • Numbers containing neither $5$ nor $6$ were removed twice, so we add them once to compensate: $7\cdot 8^7$.
  • In total, the result is $ 9\cdot 10^7 - 2\cdot 8\cdot 9^7 + 7\cdot 8^7. $

Now let's check ourselves by seeing what happens for one-digit numbers and two-digit numbers. For one-digit numbers we get $ 9 - 16 + 7 = 0, $ and indeed no single-digit number can contain both $5$ and $6$. For two-digit numbers we get $ 90 - 144 + 56 = 2, $ and the two numbers in question are $56$ and $65$.


A different (more complicated) way to solve this is to enumerate on the possible first locations of $5$ and $6$, calculate explicitly how many numbers there are of this form (easy), and then summing everything up (hard). This is simpler to do if you don't care about "exactly $8$ digits" (put otherwise, it's simpler to calculate the number for "up to $8$ digits" and then subtract the analogous count for "up to $7$ digits").