An alphabet consists of letters. What is the maximal length of a word if we know that any two consecutive letters of the word are different and that the word cannot be reduced to a word of the kind with by removing letters.
Solution
1. Base Case:
For , consider the alphabet . The word "aba" has length 3, and it cannot be reduced to a word of the form by removing letters. Thus, the maximal length for is .
2. Induction Hypothesis:
Assume that for an alphabet of letters, the maximal length of a word satisfying the given conditions is .
3. Induction Step:
We need to show that for , the maximal length of a word is .
- Assume that each letter in the word appears at least 3 times. Then, we can extract a subword using only the first letters (i.e., letters) that satisfies the condition. This subword would have a length of at least , which is greater than because . This contradicts the induction hypothesis that the maximal length for letters is .
- Therefore, there must be a letter that appears at most twice. If we disregard from our word, we are left with a word using only letters that satisfies the condition. By the induction hypothesis, this word has a length of at most .
- Adding back the letter (which appears at most twice), the total length of the word is at most .
4. Constructive Example:
To show that the length is attainable, consider the word . This word has length and satisfies the condition that no two consecutive letters are the same and it cannot be reduced to a word of the form by removing letters.
Conclusion:
By induction, we have shown that the maximal length of a word for an alphabet of letters, where no two consecutive letters are the same and the word cannot be reduced to a word of the form by removing letters, is .
The final answer is .