International Mathematical Olympiad

In order to solve this, we will give a complete classification of $n$-sequences.
Let $k=\lfloor n / 2\rfloor$. We will say that an $n$-sequence is large if $a_{i}>k$ for some $i$, and small if no such $i$ exists. For now we will assume that $(a_{i})$ is not the identity sequence (in other words, that $a_{i} \neq i$ for some $i$).

Lemma 1. If $a_{r}=a_{s}$ and $r, s<n$, then $a_{r+1}=a_{s+1}$.
Proof. We have $a_{r+1}=a_{a_{r}+a_{1}}=a_{a_{s}+a_{1}}=a_{s+1}$.

Lemma 2. If $i \leqslant k$, then $a_{i} \leqslant k$.
Proof. We have $i+i \leqslant n$, so $a_{i}+a_{i} \leqslant n$ whence $a_{i} \leqslant k$.

Lemma 3. There exist $r, s$ such that $a_{r}=a_{s}$ and $r \neq s$.
Proof. If $a_{0} \neq 0$ then $a_{2 a_{0}}=a_{0}$. Otherwise, $a_{a_{i}}=a_{i}$ for all $i$, so take $i$ such that $a_{i} \neq i$ (which we can do by our earlier assumption).

Lemma 4. Let $r$ be the smallest index such that $a_{s}=a_{r}$ for some $s>r$, and let $d$ be the minimum positive integer such that $a_{r+d}=a_{r}$. Then
1. The subsequence $(a_{r}, a_{r+1}, \ldots, a_{n})$ is periodic with minimal period $d$. That is, for $u<v$, we have $a_{u}=a_{v}$ if and only if $u, v \geqslant r$ and $d \mid v-u$.
2. $a_{i}=i$ for $i<r$ and $a_{i} \geqslant r$ for $i \geqslant r$.
In this case we say $(a_{i})$ has period $d$ and offset $r$.
Proof. We prove each in turn:
1. The "if" implication is clear from Lemma 1. For the reverse direction, suppose $a_{u}=a_{v}$. Then there are integers $r \leqslant u_{0}, v_{0}<r+d$ such that $d \mid u-u_{0}, v-v_{0}$, so $a_{u_{0}}=a_{u}=a_{v}= a_{v_{0}}$. If $u_{0}<v_{0}$ then $a_{r+d+u_{0}-v_{0}}=a_{r+d}=a_{r}$, contradicting the minimality of $d$. There is a similar contradiction when $u_{0}>v_{0}$. Thus $u_{0}=v_{0}$, so $d \mid u-v$.
2. If $r=0$ there is nothing to prove. Otherwise $a_{0}=a_{2 a_{0}}$ so $2 a_{0}=0$. Then we have $a_{a_{i}}=a_{i}$ for all $i$, so $a_{i}=i$ for $i<r$.

Lemma 5. Either
1. $d \mid a_{i}-i$ for all $i$, or
2. $r=0$ and $d \mid a_{i}-i-d / 2$ for all $i$.
Proof. Note that Lemma 4 tells us that if $a_{u}=a_{v}$ then $d \mid u-v$. Since $a_{a_{i}+a_{0}}=a_{i}$ for all $i$, we have $d \mid a_{i}-i+a_{0}$. For $i=0$, this means that $d \mid 2 a_{0}$. If $d \mid a_{0}$ then that means that $d \mid a_{i}-i$ for all $i$. Otherwise, if $d \nmid a_{0}$, then $d \mid a_{0}-d / 2$ and thus $d \mid a_{i}-i-d / 2$ for all $i$. In addition, part 2 of Lemma 4 says that we must have $r=0$ in this case.

Lemma 6. If $d$ is even and $d \mid a_{0}-d / 2$, then $(a_{i})$ is small. (Note that we must have $r=0$ in this case.)
Proof. Note that if $d \leqslant k+1$, then by Lemma 2, $(a_{0}, \ldots, a_{d-1})$ is a period for the sequence consisting of elements at most $k$, so $(a_{i})$ must be small. Now suppose $d>k+1$. We show that $a_{i} \leqslant k$ for all $i$ by induction. Note that Lemma 2 already establishes this for $i \leqslant k$. We must have $d \mid a_{d / 2}$ and $a_{d / 2} \leqslant k<d$ so $a_{d / 2}=0$. Thus, for $i>k$, if $a_{j} \leqslant k$ for $j<i$, then $a_{i-d / 2} \leqslant k$, so $a_{i}=a_{(i-d / 2)+d / 2}=a_{a_{i-d / 2}} \leqslant k$.

Lemma 7. If $(a_{i})$ is small, then $r+d \leqslant k+1$.
Proof. Since $(a_{i})$ is small, there exists $u, v \leqslant k+1$ such that $u<v$ and $a_{u}=a_{v}$. Thus $u \leqslant r$ and $d \mid v-u$, so $r+d \leqslant v \leqslant k+1$.

Lemma 8. If $(a_{i})$ is large, then $r+d>k+1$ and $a_{i}=i$ for all $0 \leqslant i<r+d$.
Proof. Since $(a_{i})$ is large and has period $d$ and offset $r$, the period $(a_{r}, \ldots, a_{r+d-1})$ must have an element that is larger than $k$, so by Lemma 2 we must have $r+d-1>k$.
We already have $a_{i}=i$ for $i<r$. Now we show that $a_{i}=i$ for $r \leqslant i \leqslant k$. By Lemma 6 we have $d \mid a_{i}-i$ but $r \leqslant i \leqslant k$. Since $k-r+1>d$, this means that $a_{i}=i$ for $i \leqslant k$.
Finally, one can show inductively that $a_{i}=i$ for $k<i<r+d$. Indeed, if $a_{j}=j$ for all $j<i$, then $a_{i} \geqslant i$ (otherwise $a_{i}=a_{j}$ for some $j<i$, but then $r \leqslant j$ and $i<r+d$ means that $d \nmid j-i$.) However, $a_{i}+(n-i)=a_{i}+a_{n-i} \leqslant n$, so $a_{i}=i$.

Thus large sequences are determined by $r$ and $d$. It is not hard to check that all sequences of the form $a_{i}=i$ for $i<r+d$ and with period $d$ and offset $r$ are $n$-sequences. There are $(n-k-1)(n+k+2) / 2$ possible choices of $(r, d)$ where $0 \leqslant r<n, d \geqslant 1$, and $k+1<r+d \leqslant n$.

For small sequences, for a given period $d$ and offset $r$, we need to choose the period $(a_{r}, \ldots, a_{r+d-1})$ satisfying $r \leqslant a_{j} \leqslant k$ and $d \mid a_{j}-j$ for $r \leqslant j<r+d$. There are $g(k+1-r, d)$ such choices, where we define $g(x, d)$ to be $(p+1)^{q} p^{d-q}$ with $p=\lfloor x / d\rfloor$ and $q=x-d p$.

Furthermore, if $d$ is even then there are $g(k+1, d)$ choices for the period $(a_{0}, \ldots, a_{d-1})$ satisfying $d \mid a_{j}-j-d / 2$ for $j<d$. Again it is not hard to check that, once these choices are made, then the resulting sequence is an $n$-sequence.

Thus the total number of $n$-sequences is
$$\begin{equation*} f(n)=1+\frac{(n-k-1)(n+k+2)}{2}+\sum_{d'=1}^{\lfloor(k+1) / 2\rfloor} g\left(k+1,2 d'\right)+\sum_{r=0}^{k} \sum_{d=1}^{k+1-r} g(k+1-r, d) \tag{1} \end{equation*}$$

Now, to show that $f(n)>c_{1} \lambda^{n}$ for some $c_{1}$, we note that
$$f(n)>g\left(k+1,\left\lfloor\frac{k+1}{3}\right\rfloor\right) \geqslant 3^{\lfloor(k+1) / 3\rfloor}>3^{n / 6}-1 .$$

To show that $f(n)<c_{2} \lambda^{n}$ for some $c_{2}$, it actually suffices to show that there is a positive real number $c_{3}$ such that for all positive integers $x$,
$$\sum_{d=1}^{x} g(x, d) \leqslant c_{3} 3^{x / 3}$$
In fact, the following lemma suffices, as it bounds the left hand side of the above inequality by a pair of geometric series with initial term $3^{x / 3}$ :

Lemma. For positive $d, x$, we have:
$$g(x, d) \leqslant \begin{cases}3^{x / 3}\left(\frac{64}{81}\right)^{x / 3-d}, & \text{ if } d \leqslant x / 3 ; \\ 3^{x / 3}\left(\frac{8}{9}\right)^{d-x / 3}, & \text{ if } d \geqslant x / 3 .\end{cases}$$

Proof. There are a few key observations needed, all of which are immediate from the definition:
- $(x, d)$ is the maximum product of a sequence of $d$ integers that sums to $x$.
- For any positive integer $k$, we have $g(k x, k d)=g(x, d)^{k}$.
- If $2 d \leqslant x \leqslant 3 d$, then $g(x, d)=2^{3 d-x} 3^{x-2 d}$. Likewise, if $3 d \leqslant x \leqslant 4 d$ then $g(x, d)= 3^{4 d-x} 4^{x-3 d}$.

With these observations, if $d \leqslant x / 3$, then
$$3^{4(x-3 d)} g(3 x, 3 d) \leqslant g(3 x+12(x-3 d), 3 d+4(x-3 d))=g(15 x-36 d, 4 x-9 d)$$
To calculate $g(15 x-36 d, 4 x-9 d)$, note that
$$\begin{aligned} & 3(4 x-9 d)=12 x-27 d \leqslant 15 x-36 d, \\ & 4(4 x-9 d)=16 x-36 d \geqslant 15 x-36 d, \end{aligned}$$
so
$$g(15 x-36 d, 4 x-9 d)=3^{4(4 x-9 d)-(15 x-36 d)} 4^{(15 x-36 d)-3(4 x-9 d)}=3^{x} 4^{3(x-3 d)}$$
Thus
$$g(x, d)^{3}=g(3 x, 3 d)=\frac{3^{4(x-3 d)} g(3 x, 3 d)}{3^{4(x-3 d)}} \leqslant \frac{3^{x} 4^{3(x-3 d)}}{3^{4(x-3 d)}}=3^{x}\left(\frac{64}{81}\right)^{x-3 d},$$
which completes the proof of the first claim. Likewise, if $d \geqslant x / 3$,
$$3^{2(3 d-x)} g(3 x, 3 d) 3 \leqslant g(3 x+6(3 d-x), 3 d+2(3 d-x))=g(18 d-3 x, 9 d-2 x) .$$
Again we have
$$2(9 d-2 x) \leqslant 18-3 x \leqslant 18-3 x+3(3 d-x)=3(9 d-2 x),$$
so
$$g(18 d-3 x, 9 d-2 x)=2^{3(9 d-2 x)-(18 d-3 x)} 3^{(18 d-3 x)-2(9 d-2 x)}=2^{3(3 d-x)} 3^{x} .$$
Thus
$$g(x, d)^{3}=g(3 x, 3 d)=\frac{2^{3(3 d-x)} g(3 x, 3 d)}{3^{2(3 d-x)}} \leqslant \frac{2^{3(3 d-x)} 3^{x}}{3^{2(3 d-x)}}=3^{x}\left(\frac{8}{9}\right)^{3 d-x}$$
from which the second claim follows.