Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2011 USAJMO Problems/Problem 4"
Line 1: Line 1:
 +
== 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 <math>W_0</math>, <math>W_1</math>, <math>W_2</math>, <math>\dots</math> be defined as follows: <math>W_0 = a</math>, <math>W_1 = b</math>, and for <math>n \ge 2</math>, <math>W_n</math> is the word formed by writing <math>W_{n - 2}</math> followed by <math>W_{n - 1}</math>.  Prove that for any <math>n \ge 1</math>, the word formed by writing <math>W_1</math>, <math>W_2</math>, <math>\dots</math>, <math>W_n</math> in succession is a palindrome.
 
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 <math>W_0</math>, <math>W_1</math>, <math>W_2</math>, <math>\dots</math> be defined as follows: <math>W_0 = a</math>, <math>W_1 = b</math>, and for <math>n \ge 2</math>, <math>W_n</math> is the word formed by writing <math>W_{n - 2}</math> followed by <math>W_{n - 1}</math>.  Prove that for any <math>n \ge 1</math>, the word formed by writing <math>W_1</math>, <math>W_2</math>, <math>\dots</math>, <math>W_n</math> in succession is a palindrome.
 +
 +
== Solution ==
 +
 +
Let <math>r</math> be the reflection function on the set of words, namely <math>r(a_1\dots a_n) = a_n \dots a_1</math> for all words <math>a_1 \dots \a_n</math>, <math>n\ge 1</math>. Then the following property is evident (e.g. by mathematical induction):
 +
 +
<math> r(w_1 \dots w_k) = r(w_k) \dots r(w_1)</math>, for any words <math>w_1, \dots, w_k</math>, <math>k \ge 1</math>.
 +
 +
a, b, ab, bab,
 +
We use mathematical induction to prove the statement of the problem. First, <math>W_1 = b</math>, <math>W_1W_2 = bab</math>, <math>W_3 = babbab</math>  are palindromes. Second, suppose <math>n\ge 3</math>, and that the words <math>W_1 W_2 \dots W_k</math>  (<math>k = 1</math>, <math>2</math>, <math>\dots</math>, <math>n</math>) are all palindromes, i.e. <math>r(W_1W_2\dots W_k) = W_1W_2\dots W_k</math>. Now, consider the word <math>W_1 W_2 \dots W_{n+1}</math>:
 +
 +
<cmath>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)</cmath>
 +
 +
<cmath>= r(W_{n-1}W_n) W_1 W_2 \dots W_{n-2} W_{n-1} W_n</cmath>
 +
 +
<cmath>= r(W_{n-1}W_n) r(W_1 W_2 \dots W_{n-2}) W_{n+1}</cmath>
 +
 +
<cmath>= r(W_1 W_2 \dots W_{n-2} W_{n-1}W_n) W_{n+1}</cmath>
 +
 +
<cmath>= W_1W_2\dots W_n W_{n+1}.</cmath>
 +
 +
By the principle of mathematical induction, the statement of the problem is proved.

Revision as of 21:53, 1 April 2012

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$ (Error compiling LaTeX. Unknown error_msg), $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_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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2011_USAJMO_Problems/Problem_4&oldid=45850"