Problem

Source: IMO LongList 1959-1966 Problem 45

Tags: combinatorics, maximization, Extremal combinatorics, Combinatorics of words, IMO Shortlist, IMO Longlist



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