Simple words
Source: Brazilian preparation to IMO 2004
September 28, 2004
floor functioninductioncombinatorics unsolvedcombinatorics
Problem Statement
A word is a sequence of n letters of the alphabet {a, b, c, d}. A word is said to be complicated if it contains two consecutive groups of identic letters. The words caab, baba and cababdc, for example, are complicated words, while bacba and dcbdc are not. A word that is not complicated is a simple word. Prove that the numbers of simple words with n letters is greater than , if n is a positive integer.