## Task 2.

For a permutation $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of the set $\{1,2, \ldots, n\}$, we say it is balanced if

$$
a_{1} \leqslant 2 a_{2} \leqslant \ldots \leqslant n a_{n}
$$

Let $S(n)$ denote the number of balanced permutations of the set $\{1,2, \ldots, n\}$.

Determine $S(20)$ and $S(21)$.
## Solution.

Let $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ be a balanced permutation of the set $\{1,2, \ldots, n\}$. We will show that one of the following two statements must hold:

(a) $a_{n}=n$,

(b) $a_{n-1}=n$ and $a_{n}=n-1$.

Let $k \in\{1,2, \ldots, n\}$ be such that $a_{k}=n$. Assume that $k < n$. Then for all $j > k$,
$$
a_{j} > k
$$

Also, $n a_{n} \geqslant k a_{k}=n k$ and since $a_{n} \neq k$, we conclude that $a_{n}>k$, and $a_{k}=n>k$. Therefore, $a_{j}>k$ for all $j \in\{k, k+1, \ldots, n\}$, meaning there are $n-k+1$ distinct numbers from the set $\{1,2, \ldots, n\}$ that are strictly greater than $k$, leading to a contradiction. Hence, we conclude that $k \geqslant n-1$.

If $k=n-1$, then $(n-1) n=(n-1) a_{n-1} \leqslant n a_{n}$, so it must be that $a_{n}=n-1$. This proves the statement.

Notice that balanced permutations such that $a_{n}=n$ correspond exactly to balanced permutations of the set $\{1,2, \ldots, n-1\}$, and balanced permutations such that $a_{n-1}=n$ and $a_{n}=n-1$ correspond to balanced permutations of the set $\{1,2, \ldots, n-2\}$. This gives us the recursive relation

$$
S(n+2)=S(n+1)+S(n), \forall n \in \mathbb{N}
$$

It is easy to see that $S(1)=1$ and $S(2)=2$, and in a finite number of steps, we get $S(20)=10946$ and $S(21)=17711$.