Problem:
Find the largest integer such that any string of letters consisting only of 's and 's contains a palindromic substring of length or longer. A palindromic substring is a string of consecutive letters which reads the same backwards as forwards.
Solution
Solution:
We claim that the largest integer is . We first prove that all strings of letters contain a palindromic substring of length or longer, which implies that . Then we shall provide a construction to show that cannot be or more.
We first begin by proving . Let be the letter substring of with the first and last letter removed.
Case 1: contains a letter that is repeated or more times in a row.
This repeating letter (e.g. ) is a palindromic substring of length or more, so we are done.
Case 2: contains a letter that is repeated times in a row, and no more.
Without loss of generality, assume this repeated letter is . As it repeats only times in a row, the letters immediately to the left and right of the substring must be , therefore contains the substring , which is palindromic with length .
Case 3: contains a letter that is repeated times in a row, and no more.
Without loss of generality, assume this repeated letter is . As it repeats only times in a row, the letters immediately to the left and right of the substring must be , therefore contains the substring , which is palindromic with length .
Case 4: does not contain a letter that is repeated in a row.
As no letter repeats, must alternate between and . Therefore it contains the substring , which is palindromic with length .
This proves that .
We now provide a construction that does not contain palindromic substrings of length or more. Consider the following sequence of length built from repeating the letters .
AABABB AABABB AABABB...
There are only possible five letter substrings as the sequence repeats every letters, none of these substrings are palindromic.
AABAB, ABABB, BABBA, ABBAA, BBAAB, BAABA
Similarly the six letter substrings are all not palindromic either.
AABABB, ABABBA, BABBAA, ABBAAB, BBAABA, BAABAB
Any longer palindromic substring of odd length must contain a palindromic substring with letters, and any longer palindromic substring of even length must contain a palindromic substring with letters. As we proved earlier there are no such substrings, there also cannot be palindromic substrings of length or longer in our constructed sequence.