Radio-playing sequence

Question

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$?

Answer 1

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.

Answer 2

Although we have by now a precise answer, I'd like to keep the summer mood of the question and play a little more with it by an elementary arithmetic approach.

The solution I wish to sell is good for any $n$, and (just in case your favorite classic radio station entrusts you with the organization of the schedule of the year, which I think would be a finest choice) includes the issues: what piece $f(t)$ will be played at time $t$, and conversely, at what time $h(x,y)$ the piece $x$ is to be played and followed by piece $y$.

Consider the functions $(f,g):\mathbb{N}\to\mathbb N\times\mathbb N$ and $h:\mathbb N\times\mathbb{N}\to\mathbb N$ defind by $$ f(t):=\cases{ \frac{t-\lfloor\sqrt t\rfloor^2}2 &if $\; t-\lfloor\sqrt t\rfloor^2$ is even\\ \\ \lfloor\sqrt t\rfloor &if $ \;t-\lfloor\sqrt t\rfloor^2$ is odd}\qquad\qquad g(t):=f(t+1),$$ and $$h(x,y):=\cases{x^2+2x&if $\;y=0 ,$\\\\y^2+2x&if $\;0\le x <y,$\\\\ x^2+2y-1&if $\;0< y \le x $.}$$

Needless to say, $(f,g)$ and $h$ are bijective, in fact inverses of each other, which is elementary (and quite exciting) to check. Moreover (keeping your ordinal notation), they subordinate a bijection $n^2\to n\times n$ for any $n\in\mathbb N$: in other words, $n^2\ni t\mapsto (f(t),f(t+1))\in n\times n$ is injective, which exactly means "$f:n^2+1\to n$ is radio-playing", and realizes the maximum cardinality $A_n=n^2+1$ wrto $n$ (there can not be an injective function $m\to n\times n$ for $m>n^2$, as you observed).