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\ne 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⩽k$, then $a_i⩽k$. Proof. We have $i+i⩽n$, so $a_i+a_i⩽n$ whence $a_i⩽k$.

Lemma 3. There exist $r,s$ such that $a_r=a_s$ and $r\ne s$. Proof. If $a_0\ne 0$ then $a_{2a_0}=a_0$. Otherwise, $a_{a_i}=a_i$ for all $i$, so take $i$ such that $a_i\ne 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},\dots ,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⩾r$ and $d\mid v-u$. 2. $a_i=i$ for $i<r$ and $a_i⩾r$ for $i⩾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⩽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_{2a_0}$ so $2a_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 2a_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⩽k+1$, then by Lemma 2, $(a_0,\dots ,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⩽k$ for all $i$ by induction. Note that Lemma 2 already establishes this for $i⩽k$. We must have $d\mid a_{d/2}$ and $a_{d/2}⩽k<d$ so $a_{d/2}=0$. Thus, for $i>k$, if $a_j⩽k$ for $j<i$, then $a_{i-d/2}⩽k$, so $a_i=a_{(i-d/2)+d/2}=a_{a_{i-d/2}}⩽k$.

Lemma 7. If $(a_i)$ is small, then $r+d⩽k+1$. Proof. Since $(a_i)$ is small, there exists $u,v⩽k+1$ such that $u<v$ and $a_u=a_v$. Thus $u⩽r$ and $d\mid v-u$, so $r+d⩽v⩽k+1$.

Lemma 8. If $(a_i)$ is large, then $r+d>k+1$ and $a_i=i$ for all $0⩽i<r+d$. Proof. Since $(a_i)$ is large and has period $d$ and offset $r$, the period $(a_r,\dots ,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⩽i⩽k$. By Lemma 6 we have $d\mid a_i-i$ but $r⩽i⩽k$. Since $k-r+1>d$, this means that $a_i=i$ for $i⩽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⩾i$ (otherwise $a_i=a_j$ for some $j<i$, but then $r⩽j$ and $i<r+d$ means that $d\nmid j-i$.) However, $a_i+(n-i)=a_i+a_{n-i}⩽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⩽r<n,d⩾1$, and $k+1<r+d⩽n$.

For small sequences, for a given period $d$ and offset $r$, we need to choose the period $(a_r,\dots ,a_{r+d-1})$ satisfying $r⩽a_j⩽k$ and $d\mid a_j-j$ for $r⩽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-dp$.

Furthermore, if $d$ is even then there are $g(k+1,d)$ choices for the period $(a_0,\dots ,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{array}{c}f(n)=1+\frac{(n-k-1)(n+k+2)}{2}+\sum _{d^{\prime }=1}^{\lfloor (k+1)/2\rfloor }g\left(k+1,2d^{\prime }\right)+\sum _{r=0}^k\sum _{d=1}^{k+1-r}g(k+1-r,d)\end{array}\text{\hspace{1em}(1)}$$

Now, to show that $f(n)>c_1{\lambda }^n$ for some $c_1$, we note that $$f(n)>g\left(k+1,\lfloor \frac{k+1}{3}\rfloor \right)⩾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)⩽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)⩽\{\begin{array}{ll}{3}^{x/3}{\left(\frac{64}{81}\right)}^{x/3-d},& \text{ if }d⩽x/3;\\ 3^{x/3}{\left(\frac{8}{9}\right)}^{d-x/3},& \text{ if }d⩾x/3.\end{array}$$

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(kx,kd)=g(x,d{)}^k$. - If $2d⩽x⩽3d$, then $g(x,d)=2^{3d-x}{3}^{x-2d}$. Likewise, if $3d⩽x⩽4d$ then $g(x,d)=3^{4d-x}{4}^{x-3d}$.

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