Bài 16:Đánh số n người đó theo các số từ 1 đến n theo 1 chiều xác định, khi đó chiều ngược lại: $\Rightarrow 2\rightarrow n,3\rightarrow n-1,...$
Chia n người đó làm 2 phần sao cho độ dài cung từ vị trí ban đầu đến vị trí cần tới(ngược lại) là nhỏ nhất thì ta cần sắp dãy $q,q+1,...,k-1,k\rightarrow k,k-1,...q+1,q$ Với k=2 thì hiển nhiên cần ít nhất 1 lần đổi chỗ
Giả sử với k=m ta cần ít nhất a lần đỗi chỗ thì với k=m+1 ta cần ít nhất a+m-1 lần vì khi đó $k \rightarrow q$ cần m-1 lượt và khi đó ta phải sắp dãy k-1 số còn lại giống với TH k=m và vì khi $k \rightarrow q$ vị trí tương đối của k-1 số còn lại không đổi nên dù thay đổi thứ tự di chuyển k thì ta vẫn cần ít nhất a lần để thực hiên sắp xếp dãy còn lại Vậy Với k=m thì ta cần ít nhất số lượt là : $\sum_{1}^{m-1}= \frac{m(m-1)}{2}$
Với n lẻ ta được 2 phần là $\frac{n+1}{2},\frac{n-1}{2}\rightarrow a= \frac{(n-1)^2}{4}$
Với n chẵn ta được 2 phần là $\frac{n-2}{2},\frac{n+2}{2}\rightarrow a= \frac{(n-1)^2+3}{4}$
- halloffame yêu thích