In this problem, a ‘word’ is a string of letters, each of which is A, B, or C.
A word is ‘interesting’ if every letter A must be followed by a B unless the A is
the last letter of the word. Note that there do not have to be any As, however.
For example, the following words are interesting:
BCBC, BCA, CABBCCAB, ABBBA, A
The following words are not interesting:
AAB, AC, ABABAA, ACBA
To make sure this is clear, you should check that there are 7 interesting words
of length 2.
How many interesting words are there of length 10?
One way of doing this is to create a recursively defined sequence. However, you can do this a different way if you prefer.
To count the number of interesting words of length 10, we can use a dynamic programming approach. Let's define a recursive function, `countInterestingWords(n)`, that returns the count of interesting words of length `n`.
To calculate `countInterestingWords(n)`, we will consider two cases:
Case 1: The last letter of the word is not 'A'.
In this case, we can append any of the letters (A, B, or C) to the end of any interesting word of length `n-1` to form an interesting word of length `n`. Therefore, the count of interesting words of length `n` in this case is `3 * countInterestingWords(n-1)`.
Case 2: The last letter of the word is 'A'.
In this case, we need to find interesting words of length `n-2` that end with 'BA'. The count of interesting words of length `n` in this case is the same as the count of interesting words of length `n-2`.
Finally, we need to consider the base cases:
- `countInterestingWords(0)` is 1, as there is only one empty word (the word with no letters).
- `countInterestingWords(1)` is 3, as there are three single-letter words (A, B, or C).
Using these definitions, we can write the following Python code to solve the problem:
```python
def countInterestingWords(n):
if n == 0:
return 1
if n == 1:
return 3
return 3 * countInterestingWords(n-1) - countInterestingWords(n-2)
# Calculate the count of interesting words of length 10
count = countInterestingWords(10)
print(count)
```
Running this code will give us the count of interesting words of length 10.
To find the number of interesting words of length 10, we can use a recursive approach.
Let's define a function, countInteresting(n), which returns the number of interesting words of length n.
For n = 1, there are only two possibilities: 'A' and 'B'. Since every letter A must be followed by a B, 'B' is the only interesting word of length 1. Therefore, countInteresting(1) = 1.
For n > 1, we can build interesting words of length n by appending a letter A, B, or C to interesting words of length (n-1). However, if the last letter of the interesting word is an A, then the next letter must be a B. So, countInteresting(n) can be calculated as follows:
countInteresting(n) = 2 * countInteresting(n-1) - countInteresting(n-2)
Let's calculate countInteresting(2) and countInteresting(3) to understand the pattern:
countInteresting(2) = 2 * countInteresting(1) - countInteresting(0) = 2 * 1 - 0 = 2
For length 2, there are two interesting words: 'AB' and 'B'.
countInteresting(3) = 2 * countInteresting(2) - countInteresting(1) = 2 * 2 - 1 = 3
For length 3, there are three interesting words: 'ABA', 'AB', and 'B'.
Using this recursive formula, we can calculate countInteresting(10):
countInteresting(10) = 2 * countInteresting(9) - countInteresting(8)
countInteresting(9) = 2 * countInteresting(8) - countInteresting(7)
...
countInteresting(3) = 2 * countInteresting(2) - countInteresting(1)
countInteresting(2) = 2 * countInteresting(1) - countInteresting(0)
countInteresting(1) = 1
Now, let's fill in the values bottom-up and calculate countInteresting(10) using the recursive formula:
countInteresting(0) = 0
countInteresting(1) = 1
countInteresting(2) = 2
countInteresting(3) = 3
countInteresting(4) = 2 * countInteresting(3) - countInteresting(2) = 2 * 3 - 2 = 4
countInteresting(5) = 2 * countInteresting(4) - countInteresting(3) = 2 * 4 - 3 = 5
countInteresting(6) = 2 * countInteresting(5) - countInteresting(4) = 2 * 5 - 4 = 6
countInteresting(7) = 2 * countInteresting(6) - countInteresting(5) = 2 * 6 - 5 = 7
countInteresting(8) = 2 * countInteresting(7) - countInteresting(6) = 2 * 7 - 6 = 8
countInteresting(9) = 2 * countInteresting(8) - countInteresting(7) = 2 * 8 - 7 = 9
countInteresting(10) = 2 * countInteresting(9) - countInteresting(8) = 2 * 9 - 8 = 10
Therefore, there are 10 interesting words of length 10.