The seventy-eighth problem: Let $n$ be a positive integer, find the number of permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of $1, 2, \ldots, n$ such that $a_{1} \leq$ $2a_{2} \leq 3a_{3} \leq \ldots \leq na_{n}$.
The 78th problem: Let $n$ be a positive integer, find the number of permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of $1, 2, \ldots, n$ such that $a_{1} \leq 2a_{2} \leq 3a_{3} \leq \ldots \leq na_{n}$. (61st IMO Shortlist)

Solution: We call a permutation $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ that satisfies the given condition a good permutation.
First, we prove a lemma: For $n \geq 3$, if $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ is a good permutation, then either $a_{n}=n$ or $a_{n-1}=n, a_{n}=n-1$.
Proof of the lemma: Let $a_{k}=n$.
If $k=n$, then the conclusion holds.
If $k=n-1$, since $(n-1)a_{n-1}=(n-1)n \leq na_{n}$, it must be that $a_{n}=n-1$, and the conclusion still holds.
If $k \leq n-2$. According to the condition, for any $k+1 \leq i \leq n-1$, we have $kn=ka_{k} \leq ia_{i} \Rightarrow a_{i} \geq \left\lceil\frac{kn}{i}\right\rceil \geq k+1$; thus, $na_{n} \geq (n-1)a_{n-1} \geq (n-1)(k+1) > nk$, so $a_{n} \geq k+1$. This shows that $a_{k}, a_{k+1}, \ldots, a_{n}$, these $n-k+1$ numbers are all greater than $k$. However, $1, 2, \ldots, n$ only have $n-k$ numbers greater than $k$, which leads to a contradiction.
In summary, the lemma is proven.
Now, let's return to the original problem.
Assume there are exactly $P_{n}$ good permutations of order $n$.
It is easy to see that $P_{1}=1, P_{2}=2$.
For $n \geq 3$, according to the lemma, either $a_{n}=n$ or $a_{n-1}=n, a_{n}=n-1$.
(1) If $a_{n}=n$, then $\left(a_{1}, a_{2}, \ldots, a_{n-1}\right)$ is a good permutation of order $n-1$ of $1, 2, \ldots, n-1$; conversely, for each such good permutation of order $n-1$, we have $(n-1)a_{n-1} \leq (n-1)^2 < na_{n}$, thus $\left(a_{1}, a_{2}, \ldots, a_{n-1}, n\right)$ is a good permutation of order $n$. Hence, there are exactly $P_{n-1}$ such good permutations of order $n$.
(2) If $a_{n-1}=n, a_{n}=n-1$. Then $\left(a_{1}, a_{2}, \ldots, a_{n-2}\right)$ is a good permutation of order $n-2$ of $1, 2, \ldots, n-2$; conversely, for each such good permutation of order $n-2$, we have $(n-2)a_{n-2} \leq (n-2)^2 < (n-1)a_{n-1} = na_{n}$, thus $\left(a_{1}, a_{2}, \ldots, a_{n-2}, n, n-1\right)$ is a good permutation of order $n$. Hence, there are exactly $P_{n-2}$ such good permutations of order $n$.
Combining the above two aspects, we get $P_{n}=P_{n-1}+P_{n-2}$.
Solving the characteristic equation, we get $P_{n}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)$.