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$ .

a, b, ab, bab, 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.

Page

Toolbox

Search

2011 USAJMO Problems/Problem 4

Problem

Solution