MathDB
Palindromes out of two letters and coprime integers

Source: 5th German TST 2005, problem 1, not from the shortlist

May 12, 2005
inductionLaTeXcombinatorics proposedcombinatorics

Problem Statement

In the following, a word will mean a finite sequence of letters "aa" and "bb". The length of a word will mean the number of the letters of the word. For instance, abaababaab is a word of length 55. There exists exactly one word of length 00, namely the empty word. A word ww of length ℓ\ell consisting of the letters x1x_1, x2x_2, ..., xℓx_{\ell} in this order is called a palindrome if and only if xj=xℓ+1−jx_j=x_{\ell+1-j} holds for every jj such that 1≤j≤ℓ1\leq j\leq\ell. For instance, baaabbaaab is a palindrome; so is the empty word. For two words w1w_1 and w2w_2, let w1w2w_1w_2 denote the word formed by writing the word w2w_2 directly after the word w1w_1. For instance, if w1=baaw_1=baa and w2=bbw_2=bb, then w1w2=baabbw_1w_2=baabb. Let rr, ss, tt be nonnegative integers satisfying r+s=t+2r + s = t + 2. Prove that there exist palindromes AA, BB, CC with lengths rr, ss, tt, respectively, such that AB=CabAB=Cab, if and only if the integers r+2r + 2 and s−2s - 2 are coprime.
Back to ProblemsView on AoPS