Bài viết đã được chỉnh sửa nội dung bởi LNH: 15-02-2014 - 16:24
Tìm số M bé nhất để sau M lần thổi còi, bằng các đổi chỗ như nói ở trên một cách thích hợp, các học sinh đứng được thành vòng tròn sao cho: Hai em bất
#1
Đã gửi 14-02-2014 - 21:32
#2
Đã gửi 15-07-2018 - 16:30
Đầu tiên ta chứng minh bổ đề: cho dãy $1,2,...,k$ muốn lộn ngược dãy thành $k,k-1,...,2,1$ thì phải tốn ít nhất $\frac{(k-1).k}{2}$ bước đổi 2 số cạnh nhau.
Thật vậy, vì muốn chuyển $1$ tới $k$ thì phải qua $k-1$ bước, sau đó ko mất tổng quát, dãy sẽ trở thành: $2,3,...,k,1$ (bởi nếu đổi chỗ 2 vị trí khác số 1, thì cũng chẳng khác nào đổi sau khi 1 về vị trí cuối cùng rồi). do đó, lại tốn ít nhất $k-2$ bước cho 2 vị trí của $k$, cứ như thế số bước ít nhất là $1+2+...+k-1$=$\frac{(k-1).k}{2}$.
Bắt đầu xét 2 TH:
TH1: n=2k, ta chia đường tròn thành 2 phần có số điểm bằng nhau: $1,2,...,k$ và $k+1,...,n$. (*)
Ta chứng minh số cách ít nhất là lôn ngược 2 phần trên.
Thật vậy giả sử còn cách nào đó mà chia đường tròn thành các phần để lộn ngược, ta hoàn toàn có thể ghép 2 phần cạnh nhau với nhau thành 1 phần, cứ ghép đến khi chỉ còn 2 phần, 2 phần này khác $1,2,...,k$ và $k+1,...,n$ tức là 1 phần có độ dài là $1,2,....,k+i$, một phần có độ dài $1,2,...,k-i$, $i>0$, số bước ít nhất để lộn 2 phần là:
$\frac{(k+i-1)(k+i)}{2}+\frac{(k-i-1)(k-i)}{2}=\frac{2k^{2}+2i^{2}-2k}{2}>k(k-1)$ là số bước cho cách chia (*), vậy suy ra phải tốn ít nhất $k(k-1)$ bước
TH2: n=2k+1. Tương tự ta chứng minh đc cách chia nhỏ nhất là $\frac{k(k+1)}{2}+\frac{(k-1)k}{2}$
- YoLo yêu thích
s2_PADY_s2
Hope is a good thing, maybe the best thing, and no good thing ever dies
2 người đang xem chủ đề
0 thành viên, 2 khách, 0 thành viên ẩn danh