Maths Olympiad Prep

Library / /234 of 520

Combinatorics Difficulty 6.8 National olympiad Find the answer

An alphabet consists of nn letters. What is the maximal length of a word if we know that any two consecutive letters a,ba,b of the word are different and that the word cannot be reduced to a word of the kind abababab with aba\neq b by removing letters.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

1. Base Case:
For n=2 n = 2 , consider the alphabet {a,b}\{a, b\}. The word "aba" has length 3, and it cannot be reduced to a word of the form abababab by removing letters. Thus, the maximal length for n=2 n = 2 is 221=3 2 \cdot 2 - 1 = 3 .

2. Induction Hypothesis:
Assume that for an alphabet of k k letters, the maximal length of a word satisfying the given conditions is 2k1 2k - 1 .

3. Induction Step:
We need to show that for n=k+1 n = k + 1 , the maximal length of a word is 2(k+1)1=2k+1 2(k + 1) - 1 = 2k + 1 .

- Assume that each letter in the word appears at least 3 times. Then, we can extract a subword using only the first n1 n-1 letters (i.e., k k letters) that satisfies the condition. This subword would have a length of at least 3(k) 3(k) , which is greater than 2k+1 2k + 1 because k>2 k > 2 . This contradicts the induction hypothesis that the maximal length for k k letters is 2k1 2k - 1 .

- Therefore, there must be a letter a a that appears at most twice. If we disregard a a from our word, we are left with a word using only k k letters that satisfies the condition. By the induction hypothesis, this word has a length of at most 2k1 2k - 1 .

- Adding back the letter a a (which appears at most twice), the total length of the word is at most 2k1+2=2k+1 2k - 1 + 2 = 2k + 1 .

4. Constructive Example:
To show that the length 2n1 2n - 1 is attainable, consider the word a1,a2,,an,an1,,a1 a_1, a_2, \ldots, a_n, a_{n-1}, \ldots, a_1 . This word has length 2n1 2n - 1 and satisfies the condition that no two consecutive letters are the same and it cannot be reduced to a word of the form abab abab by removing letters.

Conclusion:
By induction, we have shown that the maximal length of a word for an alphabet of n n letters, where no two consecutive letters are the same and the word cannot be reduced to a word of the form abab abab by removing letters, is 2n1 2n - 1 .

The final answer is 2n1 \boxed{ 2n - 1 } .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.