2011 USAJMO Problems/Problem 4

Problem

A word is defined as any finite string of letters. A word is a palindrome if it reads the same backwards as forwards. Let a sequence of words $W_0$, $W_1$, $W_2$, $\dots$ be defined as follows: $W_0 = a$, $W_1 = b$, and for $n \ge 2$, $W_n$ is the word formed by writing $W_{n - 2}$ followed by $W_{n - 1}$. Prove that for any $n \ge 1$, the word formed by writing $W_1$, $W_2$, $\dots$, $W_n$ in succession is a palindrome.

Solution

Let $r$ be the reflection function on the set of words, namely $r(a_1\dots a_n) = a_n \dots a_1$ for all words $a_1 \dots a_n$, $n\ge 1$. Then the following property is evident (e.g. by mathematical induction):

$r(w_1 \dots w_k) = r(w_k) \dots r(w_1)$, for any words $w_1, \dots, w_k$, $k \ge 1$.

We use mathematical induction to prove the statement of the problem. First, $W_1 = b$, $W_1W_2 = bab$, $W_1W_2W_3 = babbab$ are palindromes. Second, suppose $n\ge 3$, and that the words $W_1 W_2 \dots W_k$ ($k = 1$, $2$, $\dots$, $n$) are all palindromes, i.e. $r(W_1W_2\dots W_k) = W_1W_2\dots W_k$. Now, consider the word $W_1 W_2 \dots W_{n+1}$:

\[r(W_1 W_2 \dots W_{n+1}) = r(W_{n+1}) r(W_1 W_2 \dots W_{n-2}W_{n-1}W_n)\]

\[= r(W_{n-1}W_n) W_1 W_2 \dots W_{n-2} W_{n-1} W_n\]

\[= r(W_{n-1}W_n) r(W_1 W_2 \dots W_{n-2}) W_{n+1}\]

\[= r(W_1 W_2 \dots W_{n-2} W_{n-1}W_n) W_{n+1}\]

\[= W_1W_2\dots W_n W_{n+1}.\]

By the principle of mathematical induction, the statement of the problem is proved. Lightest 21:54, 1 April 2012 (EDT) The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Solution 2