Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


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
  • Giới tính:Nam
  • Đến từ:10 Toán 1,THPT chuyên Nguyễn Huệ
  • Sở thích:inequalities,geometry and number theory

Đã gửi 14-02-2014 - 21:32

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
  • Giới tính:Không khai báo
  • Đến từ:Nơi cuối của đường chân trời!
  • Sở thích:Ngắm những gì đẹp nhất, bao gồm cả cô ấy!

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


s2_PADY_s2

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





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

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