Câu hỏi 29
Một du khách đang học một cách sắp xếp sai một hoán vị $\left(p_{1}, \ldots, p_{n}\right)$ của các số nguyên $(1, \ldots, n)$. Ta định nghĩa một phép sửa trên hai phần tử kề nhau $p_{i}$ và $p_{i+1}$ là phép toán đổi chỗ hai phần tử đó nếu $p_{i}\gt p_{i+1}$, và không làm gì trong trường hợp ngược lại. Du khách thực hiện $n-1$ vòng sửa, đánh số $a=1,2, \ldots, n-1$. Trong vòng sửa thứ $a$, du khách sửa $p_{a}$ và $p_{a+1}$, rồi $p_{a+1}$ và $p_{a+2}$, và cứ thế cho đến $p_{n-1}$ và $p_{n}$. Trong quá trình này, có tổng cộng $(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$ phép sửa được thực hiện. Có bao nhiêu hoán vị của $(1, \ldots, 2018)$ mà du khách có thể bắt đầu để thu được $(1, \ldots, 2018)$ sau khi thực hiện các bước này?