[Soln] Counting 7-digit Numbers

How many seven digit numbers have AT LEAST one 3 AND AT LEAST one 7?

This is essentially the same problem as “Counting 4-digit Numbers“, except we are now trying to count 7-digit numbers instead of 4-digit ones. How big is this problem? It doesn’t take much experimentation to figure out that we can’t really proceed by listing out all possible cases like we did for the 4-digit case. There are simply too many cases!

What’s one to do when the number of cases is too many? One can try to reduce the problem to a slightly simpler version. We know that we can figure out the answer when looking at just 4 digits. Could we use that to figure out the answer when looking at 5 digits? Then 6, and then 7?

This gives us the idea of trying to set up a recurrence relation. Can we find a relationship between the number of n-digit numbers with at least one 3 and one 7, and the number of (n-1)-digit numbers with at least one 3 and one 7? In other words, if we define

a_n := \text{number of n-digit numbers with at least one 3 and one 7},

then we are trying to find a relationship between a_n and a_{n-1}.

We can do this by considering the first n-1 digits as one block X and the last digit, Y:

counting_7_digits_01

If X already contains a 3 and a 7, then Y can be any digit. If X contains a 3 but no 7, then Y must be 7. Similarly, if X contains a 7 but no 3, then Y must be 3. If X does not have any 3s and 7s, then there is no way for the number to contain both a 3 and a 7. Hence, if we define

b_n := \text{number of n-digit numbers with at least one 3 but no 7},
c_n := \text{number of n-digit numbers with at least one 7 but no 3}, and
d_n := \text{number of n-digit numbers with no 3s and 7s},

then we have the recurrence relation

a_n = 10 a_{n-1} + b_{n-1} + c_{n-1}. \hspace{1em} -(1)

We have a relation between a_n and a_{n-1}, but we have introduced 2 auxiliary sequences (b_n) and (c_n). Won’t this cause problems with using (1) to calculate a_n?

After some thought, we may realise that we can use the same method as above to set up a recurrence relation for the 2 auxiliary sequences! For example, consider the calculation for b_n:

  • If X has 3s and 7s already, then the number cannot count toward b_n.
  • If X has 3s but no 7, then Y can be any digit except 7.
  • If X has 7s but no 3, then the number cannot count toward b_n.
  • If X has no 3s and 7s, then Y must be the number 3.

Hence, we have the recurrence relation

b_n = 9 b_{n-1} + d_{n-1}. \hspace{1em} -(2)

Similarly, we have

c_n = 9c_{n-1} + d_{n-1}. \hspace{1em} - (3)

How about d_n? There is a relationship as well:

\begin{aligned} a_n + b_n + c_n + d_n &= \text{number of n-digit numbers}, \\  d_n &= 9 \times 10^{n-1} - a_n - b_n - c_n. \hspace{1em} -(4). \end{aligned}

Awesome! Now we can use relations (1) to (4) to calculate the values of the sequences. First, we test out the small cases to make sure that our relations are correct:

counting_7_digits_02

(* Why is d_1 = 7 and not d_1 = 8?)

It’s easy to check by hand that the values for a_n in the table are correct. This gives us greater confidence in our recurrence relations! We can fill up the whole table:

counting_7_digits_03

Therefore, there are 2,331,952 7-digit numbers with at least one 3 and at least one 7.

Advertisements
This entry was posted in Random and tagged . Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s