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 , , , be defined as follows: , , and for , is the word formed by writing followed by . Prove that for any , the word formed by writing , , , in succession is a palindrome.
Solution
Let be the reflection function on the set of words, namely for all words , . Then the following property is evident (e.g. by mathematical induction):
, for any words , .
We use mathematical induction to prove the statement of the problem. First, , , are palindromes. Second, suppose , and that the words (, , , ) are all palindromes, i.e. . Now, consider the word :
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.