Solution: 2022 Winter Final - 4

Method to Solve Problem

The problem asks to find the number of strings of length 70 that can be formed using the characters $ {a, b, c, d, e} $, where each character can be repeated that have at least 10 ‘a’s. The use of “at least” in the problem statement suggests that we can use the complement principle to simplify the counting process.

Total Number of Strings

Each character in the string can be chosen from the set $ {a, b, c, d, e} $ (5 choices per character). Therefore, the total number of possible strings of length 70 is: $5^{70}$

Strings with Fewer than 10 ‘a’s

We can use the complement principle. Instead of directly counting strings with at least 10 ‘a’s, we count the strings with fewer than 10 ‘a’s (0 to 9 ‘a’s) and subtract from the total.

To count strings with exactly $ i $ occurrences of ‘a’ (where $ i = 0, 1, \ldots, 9 $):

• Choose $ i $ positions for ‘a’: $ \binom{70}{i} $
• Fill the remaining $ 70 - i $ positions with the other 4 characters (b, c, d, e): $ 4^{70-i} $

Using the binomial theorem, the total number of strings with fewer than 10 ‘a’s is: $\sum_{i=0}^{9} \binom{70}{i} \cdot 4^{70-i}$

3. Apply the Complement Principle

The number of strings with at least 10 ‘a’s is: $ 5^{70} - \sum_{i=0}^{9} \binom{70}{i} \cdot 4^{70-i}$