Motivation. (Please skip if you are not in the mood for "chitchat".) Last night I listening to a classical radio station, and for the umpteenth time, they played Mendelssohn's Psalm 42, a composition that I like very much. Luckily, a week ago, when they played it, it was followed by a different piece (Rodeo by Copland) than yesterday (Bach d-minor piano concerto). I wondered how long they can proceed so that piece $X$ is never immediately followed by piece $Y$ two separate times. Which led to the following little problem.
Formalization. We regard any positive integer $n$ as the set of its predecessors, so $n = \{0,\ldots,n-1\}$. For positive integers $m, n\in \mathbb{N}$ we say that a map $f : m\to n$ is a radio-playing function if whenever $a,b \in m-1$ with $a\ne b$ and $f(a) = f(b)$, then $f(a+1) \neq f(b+1)$.
Using the pigeonhole principle, it is easy to see that if $m > n^2$ there cannot be a radio-playing function $f : m\to n$. So, given $n\in \mathbb{N}\setminus \{0\}$, let $A_n$ be the largest integer such that there is a radio-playing function $f: A_n \to n$.
What is the value of $A_n$ in terms of $n$?
Best Answer
I think you're just asking for a de Bruijn sequence of order $2$ on $n$ symbols, in which case the answer is $n^2$ because the non-simple digraph on $n$ vertices where $u \to v$ for every $u, v$ (including $u=v$) and the edges $u \to v$ and $v \to u$ are considered distinct unless $u=v$ is Eulerian.