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\neq b \in m-1$ 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$?

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

Motivation. (Please skip if you are not in the mood for "chitchat".) Last night I listening to a classical radio station, and for the umpteeth 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 never piece $X$ is 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\neq b \in m-1$ and $f(a) = f(b)$, then $f(a+1) \neq f(b+1)$.

Using the pidgeonhole 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$?

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\neq b \in m-1$ 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$?