Olimpiada Naţională de Matematică

Solution:
The main trick is to look where $n$ is positioned. In that idea let us denote by $x_{n}$ the number of all the straight permutations and by $a_{n}$ the number of straight permutations having $n$ on the first or on the last position, i.e. $\sigma(1)=n$ or $\sigma(n)=n$. Also let us denote by $b_{n}$ the difference $x_{n}-a_{n}$ and by $a_{n}^{\prime}$ the number of permutations having $n$ on the first position, and by $a_{n}^{\prime \prime}$ the number of permutations having $n$ on the last position. From symmetry we have that $2 a_{n}^{\prime}=2 a_{n}^{\prime \prime}=a_{n}^{\prime}+a_{n}^{\prime \prime}=a_{n}$, for all $n$-s. Therefore finding a recurrence relationship for $\left\{a_{n}\right\}_{n}$ is equivalent with finding one for $\left\{a_{n}^{\prime}\right\}_{n}$.
One can simply compute: $a_{2}^{\prime}=1, a_{3}^{\prime}=2, a_{4}^{\prime}=4$. Suppose that $n \geq 5$. We have two possibilities for the second position: if $\sigma(2)=n-1$ then we must complete the remaining positions with $3,4, \ldots, n$ thus the number of ways in which we can do that is $a_{n-1}^{\prime}$ (because the permutation $\sigma^{\prime}:\{1,2, \ldots, n-1\} \rightarrow \{1,2, \ldots, n-1\}, \sigma^{\prime}(k)=\sigma(k+1)$, for all $k, 1 \leq k \leq n-1$, is also a straight permutation).
If on the second position we have $n-2, \sigma(2)=n-2$, then $n-1$ can only be in the last position of the permutation or on the third position, i.e. $\sigma(3)=n-1$ or $\sigma(n)=n-1$. If $\sigma(n)=n-1$, then we can only have $\sigma(n-1)=n-3$ thus $\sigma(3)=n-4$ and so on, thus there is only one permutation of this kind. On the other hand, if $\sigma(3)=n-1$ then it follows that $\sigma(4)=n-3$ and now we can complete the permutation in $a_{n-3}^{\prime}$ ways (because the permutation $\sigma^{\prime}:\{1,2, \ldots, n-3\} \rightarrow\{1,2, \ldots, n-3\}, \sigma^{\prime}(k)=\sigma(k+3)$, for all $k$, $1 \leq k \leq n-3$, is also a straight permutation).
Summing all up we get the recurrence:
$$a_{n}^{\prime}=a_{n-1}^{\prime}+1+a_{n-3}^{\prime} \Rightarrow a_{n}=a_{n-1}+a_{n-3}+2, \forall n \geq 5$$
The recurrence relationship for $\left\{b_{n}\right\}$ can be obtained by observing that for each straight permutation $\tau:\{1,2, \ldots, n+1\} \rightarrow\{1,2, \ldots, n+1\}$ for which $2 \leq \tau^{-1}(n+1) \leq n$ we can obtain a straight permutation $\sigma:\{1,2, \ldots, n\} \rightarrow\{1,2, \ldots, n\}$ by removing $n+1$. Indeed $n+1$ is "surrounded" by $n$ and $n-1$, so by removing it, $n$ and $n-1$ become neighbors, and thus the newly formed permutation is indeed straight. Now, if $\tau^{-1}(n) \in\{1, n+1\}$ then the newly formed permutation $\sigma$ was counted as one of the $a_{n}$-s, minus the two special cases in which $n$ and $n-1$ are on the first and last positions. If $\tau^{-1}(n) \notin\{1, n+1\}$ then certainly $\sigma$ was counted with the $b_{n}$-s. Also, from any straight permutation of $n$ elements, not having $n$ and $n-1$ in the first and last position, thus $n$ certainly being neighbor with $n-1$, we can make a straight $n+1$-element permutation by inserting $n+1$ between $n$ and $n-1$.
Therefore we have obtained the following relationship:
$$b_{n+1}=a_{n}-2+b_{n}=x_{n}-2, \forall n \geq 4$$
From (1) and (2) we get that
$$x_{n}=x_{n-1}+a_{n-1}+a_{n-3}, \forall n \geq 5$$
It is obvious that $\left\{x_{n}\right\}_{n}$ is a "fast" increasing sequence, so we will compute the first terms using the relationships obtained above, which will prove that the number that we are looking for is $n=16$ :
$$\begin{aligned} & a_{2}=2 \quad x_{2}=3 \\ & a_{3}=4 \quad x_{3}=6 \\ & a_{4}=8 \quad x_{4}=12 \\ & a_{5}=12 \quad x_{5}=22 \\ & a_{6}=18 \quad x_{6}=38 \\ & a_{7}=28 \quad x_{7}=64 \\ & a_{8}=42 \quad x_{8}=104 \\ & a_{9}=62 \quad x_{9}=164 \\ & a_{10}=92 \quad x_{10}=254 \\ & a_{11}=136 \quad x_{11}=388 \\ & a_{12}=200 \quad x_{12}=586 \\ & a_{13}=294 \quad x_{13}=878 \\ & a_{14}=432 \quad x_{14}=1308 \\ & a_{15}=634 \quad x_{15}=1940 \\ & a_{16}=928 \quad x_{16}=2882 \end{aligned}$$
Therefore, the smallest positive integer $n$ for which there exist at least 2003 straight permutations is $n=16$.