3. For an integer $n \geq 3$, we say that $A=\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ is an $n$-list if every $a_{k}$ is an integer in the range $1 \leq a_{k} \leq n$. For each $k=1, \ldots, n-1$, let $M_{k}$ be the minimal possible non-zero value of $\left|\frac{a_{1}+\ldots+a_{k+1}}{k+1}-\frac{a_{1}+\ldots+a_{k}}{k}\right|$, across all $n$-lists. We say that an $n$-list $A$ is ideal if
$$
\left|\frac{a_{1}+\ldots+a_{k+1}}{k+1}-\frac{a_{1}+\ldots+a_{k}}{k}\right|=M_{k}
$$
for each $k=1, \ldots, n-1$.
Find the number of ideal $n$-lists.
SolUtion
We observe that $M_{k}=\frac{1}{k(k+1)}$; it is certainly of the form $\frac{n}{k(k+1)}$ for some integer $n$, and the sequence $2,1,1,1,1, \ldots$ shows $n=1$ can be attained.

Next we observe that the first two terms of an ideal sequence must be consecutive integers.
If the first three terms of an ideal sequence are $a, a+1, x$ or $a+1, a, x$ then $\frac{2 a+1+x}{3}-\frac{2 a+1}{2}= \pm \frac{1}{6}$ so $2 x=2 a+1 \pm 1$ so $x=a$ or $a+1$.
Changing notation slightly, if we call the third term in an ideal sequence, $c$ then we know that the first two terms sum to $2 c+\varepsilon$ for $\varepsilon \in\{-1,+1\}$. We now claim that all terms from the third onward are equal to $c$. For the base of the induction there is nothing to prove, so we assume that the terms 3 to $k$ are all equal to $c$ and denote term $k+1$ by $x$.
We have $\frac{k c+\varepsilon+x}{k+1}-\frac{k c+\varepsilon}{k}= \pm \frac{1}{k(k+1)}$
that is $k(k c+\varepsilon+x)-(k+1)(k c+\varepsilon)= \pm 1$ or $k x=k c+\varepsilon \pm 1$.
The only way that $\varepsilon \pm 1$ can be a multiple of $k$ is if it is zero, so $x=c$ as claimed.
To finish the problem we must count the sequences. We choose a consecutive pair of integers ( $n-1$ ways), choose whether the first two terms of the sequence will be increasing or decreasing (2 ways), and finally choose whether the third term will equal the smaller or the larger of the first two (2 ways). Thus there are $4(n-1)$ possible sequences.