Question 48
A permutation $\sigma:\{1,2, \ldots, n\} \rightarrow\{1,2, \ldots, n\}$ is called straight if and only if for each integer $k, 1 \leq k \leq n-1$ the following inequality is fulfilled
$$
|\sigma(k)-\sigma(k+1)| \leq 2
$$
Find the smallest positive integer $n$ for which there exist at least 2003 straight permutations.
$$
|\sigma(k)-\sigma(k+1)| \leq 2
$$
Find the smallest positive integer $n$ for which there exist at least 2003 straight permutations.