palindromic word
Source: Serbia and Montanagro 2004
August 7, 2005
inductionblogscombinatorics unsolvedcombinatorics
Problem Statement
Ana and Bora are each given a sufficiently long paper strip, one with letter written , and the other with letter . Every minute, one of them (not necessarily one after another) writes either on the left or on the right to the word on his/her strip the word written on the other strip. Prove that the day after, one will be able to cut word on Ana's strip into two words and exchange their places, obtaining a palindromic word.