Let $A_n$ be the number of permutations which satisfy the property. We claim that $A_N=F_{N+1}$, where $F_k$ is the $k^{th}$ Fibonacci number; defined as $F_0=0, F_1=1, F_{m+2}=F_{m+1}+F_{m} \forall m\ge0$. Claim: In the permutation, either $N=a_{N-1}$ or $N=a_N$. Proof: Suppose $N=a_{N-k}$ for some integer $k\ge 2$. We can deduce that any integer $m<N-k$ must be given an index of less than $N-k$; if it were not, we would need $m_i\ge N(N-k)$ for some index $i$, however as $m<N-k$ and $i\le n$, $mi<N(N-k)$, hence a contradiction. Therefore the first $N-k-1$ integers are in the permutation $(a_1,a_2\dots a_{N-k-1})$ and the integer $N-k$ must be placed further along in the permutation than $N$, so we would need $(N-k)j\ge N(N-k)$ for some index $j$, hence $j=N$. So $a_N=N-k$, and therefore $(N-k)a_{N-k}=Na_N$, sow e need $(N-r)a_{N-r}=N(N-k)$ for all non-negative integers $r\le k$. Consider the largest prime $p$ which is less than or $k+1$. By Bertrand's Postulate, $p > \frac{k+1}{2}$, hence this prime divides only one of the integers in the set $\{N-k,N-k+1\dots,N\}$, as there are $k+1$ terms, and so at most two of the products $xa_x$ are divisible by this prime. However as $k\ge 2$, we have at least 3 products, and so this is impossible. We now show that $A_N=F_{N+1}$ by induction. Base cases: $N=1$ and $N=2$. $N=1$, we only have 1 permutation so $A_1=1=F_2$. $N=2$, we only have 2 permutations, $\{1,2\}$ and $\{2,1\}$, so $A_2=2=F_3$. Now we assume $A_n=F_{n+1}$ and $A_{n+1}=F_{n+2}$ for some $n$. Consider $A_{n+2}$. By the earlier lemma, either $n+2=a_{n+1}$ or $n+2=a_{n+2}$. In the first case, if $a_{n+1}=n+2$, we must have $a_{n+2}=n+1$. As these products are greater than all other possible products, we can arrange the previous $n$ terms in a way which satisfies the condition, and we can do this in $A_n=F_{n+1}$ ways. In the second case, the largest product is $(n+2)^2$ and hence we can arrange the remaining terms in $A_{n+1}=F_{n+2}$ ways. So we have $A_{n+2}=F_{n+1}+F_{n+2}=F_{n+3}$, and so we are done.

We claim that the answer is $a_n= F_{n+1}$ where $F_n$ is the $n$-th fibonacci number defined by $F_0=0$, $F_1=1$, $F_k=F_{k-1}+F_{k-2}$. We proceed with induction, our base cases are $a_1=1=F_2$, any permutation works. And $a_2=2=F_3$, once again any permutation works. Inductive step. We do casework on the position of $n$. Case 1: $a_n=n$. In this case, all $i\cdot a_i\leq n\cdot a_n$, so we will be left with any of the $a_{n-1}$ permutations of the first $n-1$, all of which will work, Case 1 contributes $a_{n-1}$. Case 2: $a_{n-1}=n$. In this case \[a_{n-1}\cdot n\leq (n-1)\cdot a_{n-1}\leq n\cdot a_n\]thus, $a_n\geq n-1$, so $a_n=n$. Now, once again all of the first $n-2$: $1\leq j\leq n-2$ will satisfy $a_j\cdot j \leq n\cdot (n-1)$, so any of the first $n-2$ work, so this case contributes $a_{n-2}$. Case 3: $a_j=n$ for $j\leq n-2$. I claim that there are no valid solutions. Note for all indices $n\geq k \geq j$, we have \[j\cdot n = j\cdot a_j \leq k\cdot a_k \Longrightarrow a_k\geq \frac{j\cdot n}{k}\geq j\]Thus, \[a_j,a_{j+1},\ldots, a_n\geq j\]Since these $a_k$ are distinct, $\{a_j,\ldots a_n\}$ must be some permutation of $\{j,\ldots,n\}$. Consider $x>j$ such that $a_x=j$. Then, \[jn=j\cdot a_j\leq x\cdot a_x=xj\]Thus, $x\geq n$ so $x=n$ and $a_n=j$. Now, note that $a_y=n-1$ for some $j<y<n$. Thus, \[n\cdot j=n\cdot a_n\geq y\cdot a_y = y\cdot (n-1)\geq (j+1)(n-1)=nj+n-j-1\geq nj+n-(n-2)-1=nj+1\]Thus, $nj\geq nj+1$, a contradiction. Thus, there are no solutions for $j\leq n-2$. To recap, $a_n=a_{n-1}+a_{n-2}+0=a_{n-2}+a_{n-2}$, so our induction is complete.

Solved with nukelauncher We claim the answer is $F_{n+1}$, where $F_1=F_2=1$ and $F_n=F_{n-1}+F_{n-2}$ for $n\geq3$ are the Fibonacci numbers. We prove this by induction on $n$, with the base cases of $n=1,2$ being trivially true. Claim: $n\in\left\{ a_{n-1},a_n \right\}$. Proof. Suppose not. Then let $a_k=n$. Note that none of $1,2,\dots,k-1$ are elements of $\left\{ a_{k+1},a_{k+2},\dots,a_n \right\}$ as that would contradict the given inequality. Therefore, $\left\{ a_{k+1},\dots,a_n \right\}$ is a permutation of $\left\{ k,k+1,\dots,n-1 \right\}$. We must have $a_n=k$ to satisfy the inequality for $na_n\geq ka_k$, but then this implies that we have the equality \[ka_k=(k+1)a_{k+1}=\dots=na_n,\]a clear contradiction when $k<n-1$. $\blacksquare$ With the claim, the number of permutations for $n$ is the sum of the number of permutations for the cases of $n-2$ and $n-1$ by taking cases on whether $a_n=n$ or $a_{n-1}=n$ and $a_n=n-1$. This completes the inductive step, so we are done.

Claim: We have $n\in \{a_{n-1},a_n\}$. Proof: Suppose instead that $a_x=n$ and $x \le n-2$. For all $y>x$, we have \[ xn = xa_x \le ya_y \le na_y \implies a_y \ge x. \]Therefore, \[ \{a_{x+1},a_{x+2},\ldots, a_{n-1}\} = \{x,x+1,\ldots,n-1\}. \]In particular, $a_z=x$ for some $z>x$. Then \[ xn = xa_x \le za_z=zx \implies n \le z \implies z=n. \]So $a_n=x$. Now, \[ xn = xa_x \le \cdots \le na_n = nx, \]so actually $ia_i=xn$ for all $x\le i\le n$. Now the finish is easy. We have $(n-1)a_{n-1} = nx$, so $n-1 \mid nx$, so $n-1\mid x$. But $x\le n-2$, contradiction. $\blacksquare$ If $a_n=n$, then there are $f(n-1)$ ways for the first $n-1$. If $a_{n-1}=n$, then $a_n=n-1$, and there are $f(n-2)$ ways for the first $n-2$. Hence $f(n)=f(n-1)+f(n-2)$, and since $f(1)=f(2)=1$, we have $f(n) = F_{n+1}$.

The answer is $F_{n+1}$, the $(n+1)^{th}$ Fibonacci number. Let $a_1,...,a_n$ be such a permutation. Claim. (i) $a_i\geq i-1$ (ii) $a_i\leq i+1$ Proof. (i) If $a_i\leq i-2$, we prove by backward induction that $a_j\leq j-2$ for all $1\leq j\leq i$. If $a_i=i-2$, then $$(i-1)a_{i-1}\leq ia_i=i(i-2)$$hence $a_{i-1}<i-1$, which implies $a_i\leq i-3$. If $a_i\leq i-3$ then $$(i-1)a_{i-1}\leq ia_i=i(i-3)$$hence $a_{i-1}<i-2$, which implies $a_{i-1}\leq i-3$ as desired. But this is obviously impossible since $a_2\leq 0$. (ii) Suppose on the contrary that $a_i\geq i+2$, then $a_{i+1}\geq i+1$, hence at least one of $1,...,i$, say $k$ is not in $a_1,...,a_{i-1}$. Suppose $a_j=k$, then $j\geq i+2$, contradiction. $\blacksquare$ Now it is easy to see that the permutation consists of only $2$-cycles $(i,i+1)$ and fixed points, and conversely every such permutation satisfies the condition. We count the number of such permutation, denote it by $x_n$. If $a_1=2$ then there are $x_{n-2}$ ways to permute $\{3,..,n\}$, and if $a_1=1$ there are $x_{n-1}$ ways to permute $\{2,...,n\}$. Hence $$x_n=x_{n-1}+x_{n-2}$$combine with the obvious fact that $x_1=1$ and $x_2=2$ we have $x_n=F_{n+1}$ as desired.

Let $a_j=n$ First we will show that $j \leq n-2$ If $j < i< n$ then $a_i > j$ because $jn \leq ia_i < na_i$ Also $a_n > j$ because $na_n\geq (n-1)a_{n-1} > nj$. But notice that $a_j, a_{j+1}, a_{j+2}, \cdot \cdot \cdot a_n$ are $(n-1)(j+1)-nj=n-j+1$ numbers which are all greater than $j$, Whereas there are only $n-j$ such values. Hence we get that $n$ can only be placed in the last two positions. So let $S_n$ denote the total no of permutations satisfying the condition for n numbers. Now $(a_1,a_2,a_3...a_{n-1},n)$ first keep $n$ constant so we will have $S_{n-1}$ such permutations And then consider $(a_1, a_2, a_3...., n, n-1)$ which is $S_{n-2}$ So $S_n=S_{n-1}+S_{n-2}$ which is indeed the $(n+1)th$ Fibonacci number.

Pretty easy. Let the number of permutations be $x_n$. We claim that $x_n = F_{n+1}$ (the $n+1$th Fibonacci number). Claim : if $a_i =n$, then $i \in \{n-1, n\}$. Proof : FTSOC assume $a_i = n, i \leq n-2$. Then we must have $a_{i+1} \geq \frac{in}{i+1} >i \implies a_{i+1} \geq i+1$. Now $a_{i+2} \geq \frac{(i+1)^2}{i+2} > i \implies a_{i+2} \geq i+1$. Now we either have $a_{i+2} \geq i+2$ or $a_{i+2}=i+1$. But if $a_{i+2}=i+1, a_{i+1}=i+2$ for size reasons. Now note that $a_{i+3} \geq \frac{(i+1)(i+2)}{i+3} > i \implies a_{i+3} \geq i+3$. Continuing this till $n$, we see that $a_n \geq n$, or that $a_n=n-1$ and $a_{n-1}=n$. Either way, this is a contradiction. To finish, note that if $a_n=n$ we have $x_{n-1}$ sequences, and if $a_{n-1}=n, a_n=n-1$ for size reasons, so we have $x_{n-2}$ sequences. We get $x_{n}=x_{n-1}+x_{n-2}$, and seeing $x_1 =1, x_2=2$, we are done !

Let $X_n$ denote the total number of permutation of $[n]$ with the given property.Let $b_n$ denote the number of permutation of $[n]$ with the given property with $a_n=n$ and $c_n$ denote the number of permutation of $[n]$ with the given property with $a_n\ne n$.Then, $$X_n=b_n+c_n =X_{n-1}+c_n$$Now we will try to find out recursion for $c_n$ Claim: If $a_m=n$ then $a_n=m$. Proof. If $a_m=n$ then, $$mn=ma_m\le (m+1)a_{m+1}\le\dots\le na_n$$. So $m+r\le n$ so the above relation implies $a_{m+r}\ge m$ for $r=1,2,\dots,n-m$. But then $\{a_{m+1},a_{m+2}\dots a_n\}=\{m,m+1,m+2,\dots,n-1\}$ [becoz size of both set are equal]. But then $$a_{m+r}=m\implies m(m+r)\ge ma_m=mn\implies {m+r}\ge n$$So indeed $m+r=n$ $\blacksquare$ So, $ma_m=(m+1)a_{m+1}=(m+2)a_{m+2}=\dots =na_n=mn$ In particular,$(n-1)a_{n-1}=nm$.Since $\gcd(n,n-1)=1$ so $n\mid a_{n-1}$.This is possible only when $a_{n-1}=n$.In particular,$m=n-1$. So $c_n=X_{n-2}$ because $a_{n-1}=n\implies a_n=(n-1)$ for size reason. So $X_n=X_{n-1}+X_{n-2}$ . Now $X_1=1$ and $X_{2}= 2$ implies $X_n=F_{n+1}$.Where $F_n$ is $n$th Fibonacci number. $\blacksquare$

We will induct. We establish the base cases first: for $n = 1$ and $n = 2$, the answers are $1$ and $2$, respectively, and we claim that the answer is $F_{n + 1}$ where $F_0 = 0$, $F_1 = 1$, $F_2 = 1$, etc. Proceed by strong induction. For the inductive step of $i - 1$ to $i$, the idea is to consider where the largest element $i$ could go. It can obviously go at the end; this reduces to the $i - 1$ case, contributing $F_i$. Additionally, it can also go one place before the end, so the second to last product is $i(i - 1)$. As a result, this forces $i(i - 1) \leq ia_i$, so $i - 1 \leq a_i$ and so $a_i = i - 1$, reducing to the $i - 2$ case. This contributes $F_{i - 1}$. The key claim now which finishes the problem is as follows: Claim: There are no other positions for $i$ that work other than the two named above. Assume that $a_k = i$ where $k \leq i - 2$. The idea is to consider what the minimum of $a_{k + 1}, a_{k + 2}, \cdots, a_i$ is. Observe that this minimum element is at most $k$ since there are $i - k$ elements from $a_{k + 1}$ to $i$. Consequently, we know that the elements from $a_{k + 1}$ to $a_i$ are forced to be some permutation of $(k, k + 1, \cdots, i - 1)$ with $a_i = k$. Since $a_k = a_i$, we know that every term in between must be equal to them as well. Now, we just need to consider where the $i - 1$ element goes. By our logic above, we can write $(i - 1) \cdot a = ki$ for some integer $a$. However, $\gcd(i, i - 1) = 1$, so we know $i - 1 \mid k$, implying $i - 1 \leq k$, contradiction. $\square$ Thus we are done since $F_{i - 1} + F_i = F_{i + 1}$.

The answer is the $n+1$th Fibonacci number. I prove this with strong induction. Let $P(n)$ be the number of ways to do so. The base cases are easy since $$P(1)=|\{1\}|=1=F_2$$$$P(2)=|\{1,2\}, \{2,1\}|=2=F_3$$We do casework on the index of $n$. If $n$ is at the last position, there are $P(n-1)$ ways. If $n$ is at the second-to-last position, $n-1$ must be at the last position, hence there are $P(n-2)$ ways. I now prove that $n$ cannot be at any other position, effectively solving the problem. Suppose the contrary. Clearly, $n$ cannot be at the first position. Hence there is a valid sequence of the first $k$ numbers, then $n$, then a jumble of the other numbers. Consider the number $k+1$. Let's say its at index $r$. Then $$n(k+1)\le (k+1)r$$$$n\le r$$$$r=n$$Hence $k+1$ is the last number. Suppose that the number at index $n-1$ is $r$. Thus $$(n-1)r\le(k+1)n$$But $k+2\le r$, hence $$(k+2)(n-1)\le (k+1)n$$$$nk+2n-k-2\le nk+n$$$$n\le k+2$$Meaning that there are at least $n-2$ numbers before the number $n$, i.e. $n$ is at one of the last two spots, as desired.

For $m \leq n$, let $f_m(n)$ denote the number of permutations of the set $\{m,m+1, \dots , n\}$ such that $ma_m \leq (m+1)a_{m+1} \leq \dots \leq na_n$. We will prove that $f_i(n) = f_{i+1}(n) + f_{i+2}(n)$ for all $1 \leq i \leq n-2$. Now fix some $1 \leq i \leq n-2$. Let $a_k = i$. If $k = i$, then we are left with $f_{i+1}(n)$ such permutations. Let $k > i$. Then we have $k\cdot a_k = k \cdot i \geq (k-1) \cdot a_{k-1} \ge(k-1) \cdot (i+1) \iff k \leq i + 1$. So we have $k = i+1$, in other words $a_{i+1} = i$. Then $ia_i \leq (i+1)i \implies a_i \leq i+1 \implies a_i = i+1$. So $a_i = i+1$ and $a_{i+1} = i$ and we are left with $f_{i+2}(n)$ such permutations. Thus we have proved the claim. Now define a sequence as $F_1 = 1 , F_2 = 1,$ and $F_n = F_{n-1} + F_{n-2}$ for all $n \geq 3$. It is easy to see that $f_n(n) = 1$ and $f_{n-1}(n) = 2$. Thus, we have $f_1(n) = F_{n+1}$. Also it is well known that $F_n = \frac{(\frac{1 + \sqrt{5}}{2})^n - (\frac{1 - \sqrt{5}}{2})^n}{\sqrt{5}}$. So, our answer is $F_{n+1} = \frac{(\frac{1 + \sqrt{5}}{2})^{n+1} - (\frac{1 - \sqrt{5}}{2})^{n+1}}{\sqrt{5}}$.

This problem was used in 2017 Uzbekistan young mathematicians olympiad, but it was take from Crux.

Call the answer $f(n)$, and define the Fibonacci sequence as $F_0=F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ for all $n \geq 2$. I claim $f(n)=F_n$. The key claim is the following: Claim: Suppose $a_k=n$. Then we have $k \in \{n-1,n\}$. Proof: Suppose otherwise. Note that for $i<k$, we cannot have $i \in \{a_{k+1},\ldots,a_n\}$: if $i=a_j$ where $j \geq k+1$, then $ka_k=kn\leq ja_j\leq ni$, but since $k<i$ this cannot be true. Thus $\{a_k,a_{k+1},\ldots,a_n\}=\{k,k+1,\ldots,n\}$. Suppose $k=a_m$, where $m>k$. Then $ka_k=kn\leq ma_m$, so $m=n$ and we must have $$ka_k=(k+1)a_{k+1}=\cdots=na_n.$$Now consider $k+1<n$, and let $i\geq k$ be the index with $a_i=k+1$. Clearly $i \neq n$, but if $i \leq n-1$ we have $ia_i\leq (n-1)(k+1)=nk+n-k-1<nk=ka_k$, which is a contradiction, $\blacksquare$ We can manually verify that $f(1)=F_1=1$ and $f(2)=F_2=2$. Now, if we have a permutation with $n$ elements with $a_n=n$, then $(a_1,a_2,\ldots,a_{n-1})$ must be a permutation of the first $n-1$ positive integers satisfying the inequality chain, and if $a_{n-1}=n$, we must have $a_n=n-1$ and $(a_1,a_2,\ldots,a_{n-2}$ must be a permutation of the first $n-2$ positive integers satisfying the inequality chain, so $f(n)=f(n-1)+f(n-2)$ for $n \geq 3$, implying $f(n)=F_n$. $\blacksquare$

Let $f(n)$ denote this number. Its easy to check that $f(1) = 1, f(2) = 2$ and $f(3) = 3$ I will show that $f(n) = f(n-1) + f(n-2)$ which will imply that $f(n) = F_{n+1}$ where $F_k$ is the kth Fibbonacci number. If $n$ appears as $a_n$, then by induction we have $f(n-1)$ ways to choose the rest Suppose the number $n$ is at the $k$th position of the permutation ($k < n$). Then, there are $n-k$ numbers to appear to the right of it. But since for any number $a_j$ appearing to the right, we must have $kn \le na_j$, we have $a_j \ge k$ and so there are exactly $n-k$ possible numbers which may appear. So, all numbers $\ge k$ appear exactly once to the right of $n$. But, notice that the number $k$ cannot appear in any position except the last one. So, we must have $a_n = k$. But then, we have $kn \le (k+1)a_{k+1} \le ... \le kn \implies (k+i)a_{k+i} = kn$ for all $0 \le i \le n-k$ Suppose $a_{n-1}$ appears in the $q$th position. Then, we must have $q(n-1) = kn \implies n-1 | kn \implies n - 1 | k \implies k \ge n-1$ So, since we assumed $k < n$, we must have $k = n-1$. So, we have $a_{n-1} = n$ and $a_n = n-1$ and we have $f(n-2)$ ways to arrange the rest. This means we have $f(n) = f(n-1) + f(n-2)$, as claimed. $\blacksquare$

I claim that our answer is $\boxed{F_{n+1}}$, the ${(n+1)}^{th}$ Fibonacci number, where $F_0=0,F_1=1$ and $F_n = F_{n-1} + F_{n-2}$ for $n\ge2$. Claim: $n \notin \{a_1,a_2,...,a_n-2\}$ Proof: We will assume the contrary. Suppose $a_k = n$ for an integer $k$ where $1 \le k \le n-2$. We then have $kn \le (k+1)a_{k+1} \le ... \le (n-1)a_{n-1} \le na_n$. If $a_{n-1} = k$ we then have that $kn \le (n-1)k$ which is absurd, so it follows that $a_n=k$. From this we have that $kn =(k+1)a_{k+1} = ... = (n-1)a_{n-1} = nk$. More specifically, let us observe $kn = (n-1)a_{n-1}$. Let $a_{n-1} = k+c$ for some $c \in [1,n-k-1]$. Expanding we get that $k+c=nc$. However, $\max{(k+c)} = n-1$ which results in a contradiction. Now we have that $n \in \{a_{n-1},a_n\}$. Denote $P(n)$ as the number of permutations that satisfy our property. We will now consider both cases. If $a_n = n$, then we get $P(n-1)$ permutations. If $a_{n-1}=n$, then it is not hard to see that $a_{n} = n-1$ and hence there are $P(n-2)$ permutations. Adding, we get that $P(n) = P(n-1) + P(n-2)$. It is easy to see that $P(1) = 1$ and $P(2) = 2$, and our claim follows. $\blacksquare$

Short and easy, it should not be in shortlist. also finally not hardstuck on BCX rigid lol Notice that n can either be $a_{n-1}$ or $a_n$. In the former case, we are forced $a_n=n-1$ and it's reduced to $f_{n-2}$ ways, where $f_n$ denotes the number of ways to satisfy this with n numbers. In the latter case, it reduces to $f_{n-1}$. So our answer (noting that indices shift by 1, since $f_2=2$) is the n+1th Fibonacci number.

We claim, that the number of ways to order is $\boxed{F_{n+1}}$, where, $F$, denotes fibonacci. We will proceed, with induction. Base case: $n=1.$ Proof: Obviously, there is only one way to order the sequence, which is $1$, hence, $F_{1+1}=F_2=1$, and we are done. Inductive step: The, only possible values, for $n$, are $a_n$, or $a_{n-1}.$ If $a_n=n$, we have, then, it just matters, on the first $n-1,$ terms, which can be arranged, in $F_{n-1}$, ways. Now, if $a_{n-1}=n$, it just matters on the first, $n-2$, terms, which, is $F_{n-2}$, since, $F_{n-1}+F_{n-2}=F_n$, we are done.

Call a permutation good if it satisfies the inequality chain. Let $r_k$ be the number of good perumations for $n=k$. Let $k\ge 2$ for now. Note that for each good permutation for $k-1$, we can just add $k$ to the end. Also, if $k$ appears as $a_{k-1}=k$, then $a_k=k-1$, as for $a_k=j<k-1$ we would have \[(k-1)k\le a_k\cdot k<(k-1)k,\]a contradiction. Hence $r_k=r_{k-1}+r_{k-2}+t$, and we will show that $t=0$. For this, assume ftsoc that $a_i=k$ for any $i\le k-2$. Clearly, the remaining numbers that must be use for $a_i$ for $j>i$ are exactly $i,i+1,\ldots,k-1$ as otherwise $ki\le a_k\cdot k<ik$, a contradction. In particular, this means that $i$ must be used somewhere. It is easy to see somewhere means $a_i=k$. Thus, all the numbers in between must be equal to $ik$. Hence $a_{k-1}(k-1)=(i+m)(k-1)= ik$. However, $(i+m)(k-1)=ik+mk-m-k\ge (i+1)(k-1)=ik+k-(i-1)>ik$, as $k>i$, a contradiction. Thus $t=0$, and $r_k=r_{k-1}+r_{k-2}$. As $r_1=1$ and $r_2=2$, we see that $r_n$ is the $n+1$-th Fibonacci number.

We claim that the number of permutations $P(n)=F_{n}$ where $F_n$ is the $n+1^{th}$ term of the recursion $$F_{0}=1, F_1 = 1, F_{n+1}=F_{n}+F_{n-1} \text{ for all } n \geq 1$$Now, we first show via induction that $a_n \geq n-1$ for all $n \geq 2$. Note that obviously $a_2 \geq 1$. Now, assume that $a_2 \geq 1 , \cdots , a_k \geq k-1$ for some $k \geq 2$. Now, if $a_{k+1}\leq k-2$ we have $$(k+1) a_{k+1} \leq (k+1)(k-2) = k^2-k-2 < k^2 -k \leq ka_k$$which violates the given condition. If $a_{k+1}=k-1$ then, $$ka_k \geq k^2 > k^2 -1 = (k+1)(k-1) = (k+1)a_{k+1}$$which is also impossible.

This one was very cute! The number of permutations is precisely the $n+1$'th Fibonacci number. Let $p_n$ denote the number of permutations of $[n]$ satisfying the condition. We prove $p_n$ satisfies the following recursion: $p_1=1, p_2=2, p_{n}=p_{n-1}+p_{n-2}.$ The values of $p_1$ and $p_2$ are easy to verify. In the chain of inequalities, assume $n$ is at index $n-k,$ so that we have $n(n-k).$ Observe that the maximum value in the inequality chain that can be attained by $1,2, \dots, n-k-1$ are $n, 2n, \dots, n(n-k-1),$ which are all less than $n(n-k).$ Thus these numbers must all be before the $n-k$th index in the inequality. Thus $n-k, n-k+1, \dots, n-1$ are forced to be after the $n-k$th index. Observe the maximum value achieved by $n-k$ in the inequality chain is $n(n-k),$ at index $n.$ Thus $n-k$ must be the last term in the chain. Now consider the term $n-1.$ The minimum possible value it can attain is at the index $n-k+1,$ in which we have $(n-1)(n-k+1)=n^2-kn+k-1.$ Observe that $n^2-kn+k-1 > n^2-kn$ for all integers $k > 1.$ Thus there exist no valid sequences when the index of $n$ in the inequality chain is less than $n-2.$ It remains to consider when $n$ is at index $n-1$ or $n.$ In the former case, we must have $n-1$ to be at index $n,$ otherwise the inequality immediately fails. For the remaining $n-2$ numbers $1,2, \dots, n-2,$ there are $p_{n-2}$ ways to arrange them in the inequality $a_1 \le 2a_2 \le \dots \le (n-2)a_{n-2}.$ If $n$ is at index $n,$ there are $p_{n-1}$ ways to arrange the remaining $n-1$ numbers $1,2, \dots, n-1$ to satisfy the inequality $a_1 \le 2a_2 \le \dots \le (n-1)a_{n-1}.$

Main claim: $a_n$ is a valid permutation iff $|a_i-i| \leq 1 \; \forall i$ . FTSoC suppose $|a_i - i| \geq 2$ for some $i$, write $a_i = i+k$ with $k \geq 2$, and further require such $k$ to be maximal. By the Pigeonhole principle, it is possible to choose $ \phi \geq i$ so that $a_\phi \leq i$. Then since $\phi \geq i$, $$\phi a_{\phi} \geq i a_i = i(i+k).$$Suppose $a_\phi = i-t$, then $\phi \geq i+k+t$ as otherwise $\phi a_\phi < (i+k+t)(i-t) = i(i+k) - tk - t \leq i(i+k).$ Futhermore, we claim $|a_\phi - \phi| > k$ even if $t = 0$ ($t > 0$ is trivial). That is, $\phi > i+k+t$ is strict as otherwise $$\phi a_\phi = (i+k)i, ia_i = (i+1)a_{i+1} = ... = (i+k)a_{i+k} = i(i+k).$$This is contradictive if $k \geq 2$, as $gcd(i, i+1) = 1$ so $a_i = i+1 = i+k$ implying $k=1$, so $|a_\phi - \phi| > k$, contraditing with maximality. The converse is easy to check, as $$ ia_i \leq i(i+1) = (i+1)((i+1)-1) \leq (i+1)a_{i+1}$$for any $1 \leq i \leq n$. Now consider $p_n$ to be the number of such permutations. By combinatorics reasoning, if $a_n = n$ then there are $p_{n-1}$ ways of valid permutation, and if $a_n = n-1$, $a_{n-1} = n$ and we have $p_{n-2}$ ways. So $p_n = p_{n-1} + p_{n-2}$. It's easy to check $p_1 = 1$ and $p_2 = 2$, so $p_n = F_{n+1}$, the $n+1$-th Fibonacci number.

We prove the answer is $f(n) = \boxed{F_{n+1}}$ through recursion, starting by noting trivial base cases $n=1$ and $n=2$. Our problem can be translated to selecting $n$ numbers from each row of an $n \times n$ multiplication table such that each cell is in a distinct column and the entries are in weakly increasing order. We consider the number selected in the last column: $n^2$: The remaining $n-1$ numbers have $f(n-1)$ permutations. $n(n-1)$: We're forced to select $n(n-1)$ from the $(n-1)$-th column too, leaving $f(n-2)$ possibilities. $n(n-k)$ for $k \ge 2$: Consider the selections from row $n-k+1$ to row $n$, which must be at least $n(n-k)$. Since we clearly can't select $n(n-k)$ on row $n$, as this forces equality to holds on all rows in between, we are left with a $k \times (k-1)$ rectangle of potential cells. Attempting to select $k$ cells in distinct rows and columns results in a Pigeonhole contradiction. Hence we get $f(n) = f(n-1)+f(n-2)$, as desired. $\blacksquare$

For each $n\in\mathbb{Z^*_+}$, let $P_n$ be the number of permutations of $\{1,2,3,\dots, n\}$ such that \[a_1\le 2a_2\leq 3a_3\le\dots na_n\] Afirmation: $P_n= F_{n+1}$, where $F_n$ denotes the $n$th Fibonacci. Proof: Induction in $n$ (I) Base case: $n= 2$, we have two possible permutations: $\{1,2\}$ and $\{2,1\}$, note that $1\cdot 1\le 2\cdot 2$ and $1\cdot 2\le 2\cdot 1$. So, $P_2= 2= F_3$. (ii) Hypothesis: Assuming the lemma is valid for all $m\le n-1$ $m\in\mathbb{Z^*_+}$, we will prove it is valid for $n$. We have two cases: If $a_n= n$, then we need to choose $\{1,2,\dots, n-1\}$ for $a_1, a_2, \dots, a_{n-1}$. So, there are $P_{n-1}$ possible permutations. If $a_n= n-i$, with $i\in\{1,2,\dots, n-1\}$, then we know that $(n-1)a_{n-1}\le na_n= n(n-i)\implies \dfrac{a_{n-1}}{n-i}\le 1+\dfrac{1}{n-1}$. If $a_{n-1}\ge n-i+1\implies \dfrac{n-i+1}{n-i}\le \dfrac{a_{n-1}}{n-i}\le 1+\dfrac{1}{n-1}\implies n-1\le n-i\implies i\le 1\therefore i=1$. So, $a_n= n-1$ and $a_{n-1}= n$. Indeed, this gives us a solution, because we now have $\{1,2,3,\dots, n-2\}$ for $a_1, a_2, \dots, a_{n-2}$, which leads us to $P_{n-2}$ possible permutations. Now, if $a_{n-1}\le n-i-1$. Let $a_{n-1}= n-j$, with $j\ge i+1$. Observe that $(n-2)a_{n-2}\le (n-1)a_{n-1}= (n-j)(n-1)\implies \dfrac{a_{n-2}}{n-j}\le \dfrac{n-1}{n-2}= 1+\dfrac{1}{n-2}$. If $a_{n-2}\geq n-j+1$ ($a_{n-2}\neq a_{n-1}$), thus $1+\dfrac{1}{n-j}=\dfrac{n-j+1}{n-j}\le\dfrac{a_{n-2}}{n-j}\le 1+\dfrac{1}{n-2}$ $\implies n-2\le n-j\implies j\le 2\implies j=2\implies i=1$. Finally, $a_n= n-1$ and $a_{n-1}= n-2$. Also, we get that $a_{n-2}\ge n-2+1= n-1\implies a_{n-2}= n$. But $a_{n-2}(n-2)= n(n-2)\leq a_{n-1}(n-1)= (n-2)(n-1)\implies n\le n-1$, absurd! So, we must have $a_{n-2}\le n-j-1$. Inductively, we will have that $a_1<a_2<a_3<\dots<a_{n-2}<a_{n-1}<a_n$. One number is missing! As $a_n\neq n$, then $n$ would appear somewhere, but with this ordination is impossible! Contradiction! Therefore, $P_n= P_{n-1}+P_{n-2}$, $\forall n$. As $P_2= 2$ and $P_3=3$, we get that $P_n= F_{n-1}$, QED $\blacksquare$

Almost similar to the solutions above but i'll still post it becoz i spent an hour solving it and another to write it... The answer is $A_n=F_{n+1}$, the ${n+1}^{th}$ Fibonacci number (this can be checked by going upto $n=5$) where $A_n$ denotes the number of permutations. CLAIM: $a_i\neq n$ for $1\le i\le n-2$. PROOF: Note that if $a_i \le k-2$, then $a_k=k-2$ or $a_k \le k-3$. If $a_k = k -2$, then we have \[ a_{k-1} (k-1) < (k-1)^2 \implies a_{k-1} < k-1 \implies a_{k-1} \le k-2.\]If $a_k = k-2$, then $a_{k-1} \ne k-2$, hence $a_{k-1} \le k-3$. Otherwise if $a_k \le k-3$, then we have \[ a_{k-1} (k-1) \le k(k-3) < (k-1)(k-2) \implies a_{k-1} < k-2 \implies a_{k-1} \le k-3.\]This is a contradiction, so the only remaining cases to be checked are $a_{n-1}=n$ or $a_n=n$ which is trivial recurrence. Hence, $A_n=A_{n-1}+A_{n-2}$ where $A_1=1$ and $A_2=2$ so $\boxed{A_n=F_{n+1}}$.

The answer is $F_{n+1},$ where $F_k$ is the kth Fibonacci number. The key claim is that in any permutation that works (interchangeable with the description "is good"), $n=a_{n-1}$ or $n=a_n.$ FTSOC assume there is a $k$ with $1 \le k \le n-2$ such that we have a good permutation and $a_{k}=n.$ First, we establish that all the numbers $a_i$ with index higher than $k$ must be at least $k,$ else there is a value $m$ such that $ma_m<kn,$ which does not happen in a good permutation. Then the only option for $a_n$ is $k,$ as a lower index causes the $ia_i$ value to be less than $kn.$ Then, every number in between must have the exact value $kn.$ However, any permutation of the numbers that are at least $k$ into the indices $a_{k+1}, a_{k+2}\dots a_n$ is $\sum _{i=1}^{k}(n-k+i)(n-i)$ by the rearrangement inequality. This sum equals $kn(n-k)+\frac{k^2(k+1)}{2},$ which exceeds $kn(n-k).$ This is a contradiction. Therefore, $n=a_{n-1}$ or $n=a_n.$ Now we use induction to count the number of permutations. Base case: $n=2,3.$ These cases are true, verified on paper (too lazy to type) Inductive step: Assume for the values $n=k-1,k$ there are $F_k$ and $F_{k+1}$ good permutations. Now consider $n=k+1.$ In the case of $n=a_{n-1},$ $a_n=n-1$ is the only option, then the earlier terms are permuted in $F_k$ ways When $a_n=n,$ the earlier terms are permuted in $F_{k+1}$ ways. Therefore, in total for the $k+1$ case there are $F_k+F_{k+1}=F_{k+2}$ total ways to permute, completing the induction. Q.E.D.

I think just split into 2 cases whether $a_n$ and $a_{n-1}$ are $n$ and $n-1$ or not. Maybe induction is also ok? Btw I am a noob at LaTeX so I can't type my solution out

Our answer is $\text{F}_{n + 1}$, with $\text{F}_0 = 1, \text{F}_1 = 2$. Let $F_n$ denote the number of permutations for $n$. First off, if $n$ is in $n ^{\text{th}}$ spot, then the number of permutations is simply $\text{F}_{n - 1}$, since $n^2 > (n - 1)^2$. If $n$ is the $(n - 1)^{\text{th}}$ spot, then $n - 1$ is forced to be in the $n^{\text{th}}$ spot, since $n(n - 1) > n(n - 2)$. Now, our number of permutations is simply $F_{n - 2}$, as $n(n - 1) > (n - 2)^2$. Now, we claim that $n$ can't be in the spots $1, 2, \dots, n - 2$. Say $n$ is in the $(n - k) ^ {\text{th}}$ spot, where $k \geq 2$. Observe that $n(n - k) > (n - k - 1)n$, so numbers $\leq n - k - 1$, can't be in the spots ahead of where $n$ is positioned. So $n - k, n - k + 1, ..., n - 1$, are forced to be in the spots ahead of $n$. Note that $n - k$ is forced to be in the $n^{\text{th}}$ spot, and since $n(n - k) < (n - k + 1)(n - 1)$, we have a contradiction. So, $\text{F}_n = \text{F}_{n - 1} + \text{F}_{n - 2}$, and we are done.

Counting solution

The answer is $F_{n + 1}$ where $F_i$ is the $i$th Fibonacci number. We prove this by induction. The base cases of $n = 1,2$ are trivial. Inductive Step: We consider the placement of the element $n$. If it is in the end, we get $F_{n}$ valid sequences. If it is second to the end, we must have $a_n \cdot n \ge n(n - 1)$, forcing $a_n = n - 1$, so we just need the condition to hold for the first $n - 2$ elements, giving another $F_{n - 1}$ valid sequences. We now claim that $n$ cannot be placed any further back. Assume for the sake of contradiction that it is placed at $n - k$. Then we have $k$ elements less than $n$ after $n$, at least one of these $a_i$ is at most $n - k$. If it is less than $n - k$, we would have $n(n - k) > ia_i$, since $n \ge i, n - k > a_i$, so it must be exactly $n - k$ (furthermore all of these elements located after $n$ are at least $n - k$ to satisfy the inequality). Furthermore, since $i(n - k) \ge (n - k)n$, we have $i \ge n$, forcing $ i = n$. So we have for $n > i > n - k$, $ na_n \ge ia_i \ge (n - k)a_{n - k}$, so $ia_i = n(n - k)$, however just consider when $a_i = n -1$, we must have $ i > n - k$ since the elements located after $n$ are all the elements from $n - 1$ to $n - k$ in some order. Then we have $ia_i \ge (n - 1)(n - k + 1) = n^2 - kn + k - 1 > (n)(n - k)$, contradiction.

Let $f(n)$ be the number of permutations satisfying the statement. The answer is $\boxed{f(n)=F_{n+1}=\frac{(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}}{\sqrt{5}}}$ We´re prove it by a strong induction in $n$: Base Case: For $n=1$ we just have the permutation {1}, so, $f(1)=F_2=1$. For $n=2$ we have {1,2} and {2,1}, so $f(2)=F_3=2$. $\blacksquare$ Induction Hypothesis: Assume the afirmation is valid for all $m\leq n-1$. Inductive Step: Let´s prove the following lemma: Lemma: In a permutation such that \[a_1\le 2a_2\leq 3a_3\le\dots na_n\]we just can have $n=a_{n-1}$ or $n=a_n$ Proof: FTSoC, assume that we can have $n=a_{n-2}$. Clearly, if this case is impossible, the other ones will be too. Look at the position of $n-2$ in that permutation: Since $n(n-2)>(n-1)(n-2)$ for $n>2$, we must have $a_n=n-2$. But, note that we won´t have numbers to place in $a_{n-1}$ since $(n-2)a_{n-2}=n^2-2n$ and $na_n=n^2-2n$, so we´ll must have $(n-1)a_{n-1}=n^2-2n$ but $(n-1)\nmid n^2-2n$ for $n>1$. Contradiction! $\blacksquare$ Therefore, if $n+a_n$, we´ll have $f(n-1)=F_n$ permutations for the other numbers and if $n=a_{n-1}$, we´ll must have $a_n=n-1$ therefore we´re going to have $f(n-2)=F_{n-1}$ permutations. Hence by the additive principle, $f(n)=f(n-1)+f(n-2)=F_n+F_{n-1}=F_{n+1}=\frac{(\frac{1+\sqrt{5}}{2})^{n+1}-(\frac{1-\sqrt{5}}{2})^{n+1}}{\sqrt{5}}$ as we wanted to show $\blacksquare$