Library / /14 of 22

, 2014

Combinatorics Difficulty 5.8 AIME, harder Prove it Romania

A succession of letters $\overline{l_1l_2\dots l_n}$ , where $n \ge 1$ , is called a word. A word $\overline{l_1l_2\dots l_n}$ is called a palindrome, if $l_k = l_{n-k+1}$ , for each $k \in \{1, 2, \dots, n\}$ .
Consider a two-letter word $X = \overline{l_1l_2\dots l_{2014}}$ , with letters $A$ and/or $B$ . Prove that $X$ can be obtained by writing one next to another at most 806 palindromes.

Solution

Let us split $X$ into groups of 5 consecutive letters; this way we obtain 402 groups of 5 letters and another incomplete group of 4 letters.

Consider a 5 letter-word $Y$ , written only with $A$ 's and $B$ 's, whose first letter is $A$ . So $Y$ is one of the sixteen words of the form $A * * * *$ . It is easy to check that all of these words either are palindromes or can be formed by joining two palindromes. Switching $A$ with $B$ , a similar observation stands if a 5 letter-word $Y$ starts with $B$ .

Hence, we can concatenate at most $2 \cdot 402 = 804$ palindromes to cover the first 2010 letters of $X$ . For the last 4 letters we need at most two palindromes, so 806 is the maximum number of palindromes we need.

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.