Problem

Source: Danube 2014 junior p2

Tags: palindromes, combinatorics



We call word a sequence of letters $\overline {l_1l_2...l_n}, n\ge 1$ . A word $\overline {l_1l_2...l_n}, n\ge 1$ is called palindrome if $l_k=l_{n-k+1}$ , for any $k, 1 \le k \le n$. Consider a word $X=\overline {l_1l_2...l_{2014}}$ in which $ l_k\in\{A,B\}$ , for any $k, 1\le k \le 2014$. Prove that there are at least $806$ palindrome words to ''stick" together to get word $X$.