Maths Olympiad Prep

Library / /33 of 41

Combinatorics Difficulty 6.3 National Olympiad Prove it New Zealand

Problem:
Find the largest integer kk such that any string of 20252025 letters consisting only of AA's and BB's contains a palindromic substring of length kk 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 44. We first prove that all strings SS of 20252025 letters contain a palindromic substring of length 44 or longer, which implies that k4k \geq 4. Then we shall provide a construction to show that kk cannot be 55 or more.

We first begin by proving k4k \geq 4. Let RR be the 20232023 letter substring of SS with the first and last letter removed.

Case 1: RR contains a letter that is repeated 44 or more times in a row.
This repeating letter (e.g. AAAAAAAA) is a palindromic substring of length 44 or more, so we are done.

Case 2: RR contains a letter that is repeated 33 times in a row, and no more.
Without loss of generality, assume this repeated letter is AA. As it repeats only 33 times in a row, the letters immediately to the left and right of the substring AAAAAA must be BB, therefore SS contains the substring BAAABBAAAB, which is palindromic with length 5>45 > 4.

Case 3: RR contains a letter that is repeated 22 times in a row, and no more.
Without loss of generality, assume this repeated letter is AA. As it repeats only 22 times in a row, the letters immediately to the left and right of the substring AAAA must be BB, therefore SS contains the substring BAABBAAB, which is palindromic with length 44.

Case 4: RR does not contain a letter that is repeated in a row.
As no letter repeats, RR must alternate between AA and BB. Therefore it contains the substring ABABAABABA, which is palindromic with length 5>45 > 4.

This proves that k4k \geq 4.

We now provide a construction that does not contain palindromic substrings of length 55 or more. Consider the following sequence of length 20252025 built from repeating the 66 letters AABABBAABABB.

AABABB AABABB AABABB...

There are only 66 possible five letter substrings as the sequence repeats every 66 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 55 letters, and any longer palindromic substring of even length must contain a palindromic substring with 66 letters. As we proved earlier there are no such substrings, there also cannot be palindromic substrings of length 77 or longer in our constructed sequence.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.