Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer 1

up vote 6 down vote accepted

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").

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.