Đến nội dung

Hình ảnh

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

- - - - -

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
ngoctruong236

ngoctruong236

    Trung sĩ

  • Thành viên
  • 146 Bài viết
Có $n$ em học sinh ($n>3$) đứng thành một vòng tròn và luôn quay mặt vào cô giáo ở tâm vòng tròn. Mỗi lần cô giáo thổi còi thì có hai em nào đó đứng sát cạnh nhau đổi chỗ cho nhau, còn các em khác không dời chỗ. 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 kỳ lúc ban đầu đứng sát cạnh nhau thì lúc kết thúc cũng đứng sát cạnh nhau, nhưng trong hai em đó, tạm gọi là A và B, nếu A lúc ban đầu đứng bên tay trái của B thì lúc kết thúc A đứng bên tay phải của B

Bài viết đã được chỉnh sửa nội dung bởi LNH: 15-02-2014 - 16:24


#2
Hr MiSu

Hr MiSu

    Thượng sĩ

  • Thành viên
  • 206 Bài viết

Đầ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}$


s2_PADY_s2

Hope is a good thing, maybe the best thing, and no good thing ever dies





0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh