On Binary Island, the locals have only two letters in their alphabet:
A and B. Sequences of these letters are called strings. The number of
letters in a string is called its length. If a string has length n, then we
call it an n-string. For example, ABAABABAABAA is a 12-string.
A block of consecutive letters in a string is called a substring. A substring
may appear more than once. For example, ABAABABAABAA contains
the substring AA three times, the substrings AB and BA four times each,
but does not contain the substring BB.
A string that reads the same forwards and backwards is called palindromic. Every 3-string starting with A has exactly three different palindromic substrings, as shown in this table.
3-string palindromic substrings
AAA -> A, AA, AAA
AAB -> A, B, AA
ABA -> A, B, ABA
ABB -> A, B, BB
a) Explain why it follows from the table above that every 3-string starting with B has exactly 3 palindromic substrings.
b) Show that every 4-string starting with A has exactly 4 palindromic
substrings.
c) Show that every 5-string has exactly 5 palindromic substrings.
It is also true that every 6-string has exactly 6 palindromic substrings,
and every 7-string has exactly 7 palindromic substrings. However, this
pattern does not continue.
d) Find an 8-string that starts with AABBA and has only 7 palindromic
substrings.
a) From the table above, we can observe that for every 3-string starting with A, there are exactly three different palindromic substrings. This means that regardless of the third letter, the number of palindromic substrings remains the same. Therefore, every 3-string starting with B will also have exactly three palindromic substrings.
b) To show that every 4-string starting with A has exactly four palindromic substrings, we can consider the possible combinations of the last two letters. Let's denote the first two letters as X and Y, where X and Y can be either A or B.
If X = A and Y = A, the 4-string would be AAAA. In this case, the palindromic substrings are A, A, AA, and AAA, giving us four palindromic substrings.
If X = A and Y = B, the 4-string would be AAB. In this case, the palindromic substrings are A, B, AA, and ABA, giving us four palindromic substrings.
If X = B and Y = A, the 4-string would be ABAA. In this case, the palindromic substrings are A, B, AA, and ABA, giving us four palindromic substrings.
If X = B and Y = B, the 4-string would be ABAB. In this case, the palindromic substrings are A, B, ABA, and ABABA, giving us four palindromic substrings.
Therefore, for every 4-string starting with A, there are exactly four palindromic substrings.
c) To show that every 5-string has exactly five palindromic substrings, we can again consider the possible combinations of the last two letters. Let's denote the first three letters as X, Y, and Z, where X, Y, and Z can be either A or B.
If X = A, Y = A, and Z = A, the 5-string would be AAAAA. In this case, the palindromic substrings are A, A, AA, AAA, and AAAA, giving us five palindromic substrings.
If X = A and one of Y and Z is B, the 5-string would be AAB or ABA. In both cases, the palindromic substrings are A, B, AA, ABA, and ABAA (or ABABA), giving us five palindromic substrings.
If X = B and Y = A or Z = A, the 5-string would be ABAA or AABA. In both cases, the palindromic substrings are A, B, AA, ABA, and ABAA (or ABABA), giving us five palindromic substrings.
If X = B and Y = B and Z = B, the 5-string would be ABBB. In this case, the palindromic substrings are A, B, AA, BB, and ABBBA, giving us five palindromic substrings.
Therefore, every 5-string has exactly five palindromic substrings.
d) To find an 8-string that starts with AABBA and has only 7 palindromic substrings, we can consider the combinations of the last three letters. Let's denote the first five letters as A, A, B, B, and A, respectively.
If the last three letters are A, A, and A, the 8-string would be AABAAAABA. In this case, the palindromic substrings are A, B, AA, BB, AAA, ABA, and AABAAAABA, giving us seven palindromic substrings.
Therefore, AABAAAABA is an example of an 8-string that starts with AABBA and has only 7 palindromic substrings.
a) From the table above, we can observe that every 3-string starting with A has three different palindromic substrings, regardless of the specific combination of other letters in the string. Therefore, we can deduce that every 3-string starting with B will also have exactly three palindromic substrings, as the pattern remains consistent.
b) To show that every 4-string starting with A has exactly four palindromic substrings, we can list all possible palindromic substrings for each of the four different 4-strings:
- AAAA -> A, AA, AAA, AAAA
- AAAB -> A, B, AA, ABA
- AABA -> A, B, AA, ABA
- AABB -> A, B, BB, ABB
As we can see, every 4-string starting with A has exactly four palindromic substrings.
c) To show that every 5-string has exactly five palindromic substrings, we can use a similar approach:
- AAAAA -> A, AA, AAA, AAAA, AAAAA
- AAAAB -> A, B, AA, AAA, ABA
- AAABA -> A, B, AA, ABA, AABA
- AAABB -> A, B, BB, ABB, ABBA
- AABB -> A, B, BB, ABB, BB
By listing the palindromic substrings for each possible 5-string, we can see that every 5-string has exactly five palindromic substrings.
d) To find an 8-string that starts with AABBA and has exactly seven palindromic substrings, we need to construct a string that has some repeated palindromic substrings. Let's consider the string "AABBAABB":
- AABBAABB -> A, B, AA, BB, ABA, ABB, AABBAA
This 8-string has seven palindromic substrings: A, B, AA, BB, ABA, ABB, and AABBAA.