Thuvientoan.net xin gửi đến bạn đọc tài liệu Lời giải chi tiết đề thi chọn Đội tuyển quốc gia Việt Nam dự thi IMO năm 1990.

Bài 6.
Cho n học sinh đứng thành một vòng tròn và quay mặt vào cô giáo ở tâm đường tròn. Mỗi lần cô giáo thổi còi thì hai em nào đó đứng cạnh nhau đổi chỗ cho nhau, các em còn lại đứng im. Tìm số M nhỏ nhất sao cho sau M lần thổi còi, bằng cách đổi chỗ như trên một cách thích hợp thì các em học sinh đứng được thành một vòng tròn mới sao cho: Hai em lúc đầu đứng cạnh nhau, nhưng hai em đó, tạm gọi là A và B, thì nếu lúc đầu A đứ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.
Lời giải.
Ta thấy rằng yêu cầu của bài toán có thể phát biểu thành:
Giả sử ban đầu n bạn học sinh đứng theo một thứ tự nhất định nào đó trên vòng tròn theo cùng kim đồng hồ. Tìm số lần đổi chỗ nhỏ nhất sao cho các học sinh vẫn đứng theo thứ tự đó trên vòng tròn nhưng ngược chiều kim đồng hồ.

Đánh số các học sinh này là 1, 2,3,..., n - 2, n - 1 theo chiều kim đồng hồ và ở trạng thái cuối, các học sinh cũng được đánh số như thế nhưng ngược chiều kim đồng hồ.
Ta thấy rằng với ba học sinh A, B, C đứng theo thứ tự đó thì khi đổi chỗ B và C, ta nhận được thứ tự mới là A, C, B. Ta có thể coi trong việc đổi chỗ đó, B đứng yên và C chuyển qua vị trí xen giữa A và B. Như thế, với bất kì dãy các cách đổi chỗ nào, ta luôn có thể chọn ra được ít nhất 1 học sinh đứng yên trong suốt quá trình đó, giả sử là học sinh được đánh số 1.

Tài liệu

THEO THUVIENTOAN.NET