Find the largest positive integer $k$ so that any binary string of length $2024$ contains a palindromic substring of length at least $k$.
Problem
Source: Philippine Mathematical Olympiad 2024 P5
Tags: combinatorics, string, palindrome
demmy
21.02.2024 16:21
Answer is $4$
Construction part. Consider the binary string $A$, \[A=110100\mid110100\mid \dots \mid 110100 \mid 11\]Notice that $A$ doesn't contains any palindromic substring of length $5$
Bounding part. We will prove that for any binary string always contains palindromic substring of length $4$
Without loss of generality assume that the leftmost digit of binary string $A$ is $1$
Let \[ A = \underbrace{1 \dots 1}_{a_1} \underbrace{0 \dots 0}_{a_2} \dots \underbrace{1 \dots 1}_{a_{2k-1}} \underbrace{0 \dots 0}_{a_{2k}} \dots. \]and define $s_i$ such that $$s_i= a_i+2\min\{a_{i-1},a_{i+1}\}+\dots+2\min\{a_k,a_{2i-k}\}\text{ } \text{if } k\text{ }\text{is the least integer such that }a_k \neq a_{2i-k} $$for example \[A = 1101101 \text{ } \text{then} \text{ } a_1 = 2 , a_2=1 , a_3=2 , a_4=1 , a_5=1 \text{ } \text{and} \text{ } s_1 = 2,s_2=5,s_3=4,s_4=3,s_5=1\]
if there exists no such $k$ then sum until it reached leftmost or rightmost
Notice the longest length of palindromic substring of $A$ with middle of it is in $a_i$ is equal to $s_i$
Suppose that the longest palindromic substring of $A$ is $3$
Since $a_i \geq 1$ for all $i \in [1,k]$ thus $s_i \geq 3$ for all $i \in [2,k-1]$
$\implies$ $a_i=1$ for all $i \in [2,k-1]$ contradiction since we could find $s_i > 3$.