IMO 2016 Shortlist – Combinatorics


Các bạn có thể xem hai phần trước ở các link dưới đây:
Số học https://nttuan.org/2017/07/21/imo-2016-shortlist-number-theory/
Đại số https://nttuan.org/2017/07/20/imo-2016-shortlist-algebra/
—-
C1. Trưởng đoàn của một đội IMO chọn hai số nguyên dương \displaystyle n\displaystyle k thỏa mãn \displaystyle n>k, và gửi chúng đến phó đoàn và một thí sinh trong đoàn. Sau đó trưởng đoàn bí mật gửi cho phó đoàn một xâu nhị phân độ dài \displaystyle n, và phó đoàn viết ra một xâu nhị phân độ dài \displaystyle n khác xâu của trưởng đoàn đúng \displaystyle k vị trí. Thí sinh được nhìn xâu của phó đoàn và phải đoán xâu của trưởng đoàn. Hỏi thí sinh cần đoán ít nhất bao nhiêu lần để có câu trả lời đúng?
C2. Tìm tất cả các số nguyên dương \displaystyle n sao cho tất cả các ước dương của \displaystyle n có thể đặt vào các ô của bảng chữ nhật để các điều kiện sau được thỏa mãn đồng thời:
(a) mỗi ô chứa một ước phân biệt;
(b) tổng các số trên mỗi hàng bằng nhau;
(c) tổng các số trên mỗi cột bằng nhau.
C3. Cho số nguyên dương \displaystyle n nguyên tố cùng nhau với \displaystyle 6. Ta tô các đỉnh của một \displaystyle n-giác đều bởi ba màu (mỗi đỉnh tô đúng một màu) sao cho với mỗi màu, có một số lẻ đỉnh mang màu đó. Chứng minh rằng tồn tại một tam giác cân có ba đỉnh khác màu.
C4.Tìm tất cả các số nguyên dương \displaystyle n sao cho trên mỗi ô vuông con của bảng \displaystyle n \times n ta có thể viết một trong các chữ cái \displaystyle I,M\displaystyle O để hai điều kiện sau được thỏa mãn đồng thời:
1) trên mỗi dòng và mỗi cột, một phần ba là I, một phần ba là M và một phần ba là O;
2) trên mỗi đường chéo có số ô là bội của 3, một phần ba là I, một phần ba là M và một phần ba là O.
Chú ý. Các dòng và các cột của một bảng \displaystyle n \times n được đánh số từ \displaystyle 1 đến \displaystyle n theo cách tự nhiên. Như vậy mỗi ô tương ứng với một cặp số nguyên dương \displaystyle (i,j) với \displaystyle 1 \le i,j \le n. Khi \displaystyle n>1, bảng có \displaystyle 4n-2 đường chéo. Các đường chéo này có hai kiểu, kiểu thứ nhất chứa các ô \displaystyle (i,j) với \displaystyle i+j là hằng số, kiểu thứ hai chứa các ô \displaystyle (i,j) với \displaystyle i-j là hằng số.
C5. Cho số nguyên dương \displaystyle n>2. Tìm số lớn nhất các đường chéo của một \displaystyle n-giác đều mà ta có thể chọn sao cho không có hai đường chéo nào có điểm trong chung và không có hai đường chéo nào vuông góc với nhau.
C6.\displaystyle n>2 hòn đảo trong một thành phố. Lúc đầu, một công ty quản lý phà mở vài tuyến phà giữa các cặp đảo sao cho không thể chia các đảo thành hai nhóm thỏa mãn: không có hai đảo thuộc hai nhóm khác nhau mà có một tuyến phà nối chúng. Sau mỗi năm, công ty sẽ đóng một tuyến phà giữa hai đảo \displaystyle X\displaystyle Y. Đồng thời, họ mở các tuyến phà mới theo quy tắc: với mỗi đảo nối với đúng một trong hai đảo \displaystyle X,Y bởi một tuyến phà, một tuyến phà mới sẽ được mở để nối nó với đảo còn lại. Giả sử rằng tại mọi thời điểm, nếu ta chia các đảo thành hai nhóm khác rỗng theo cách bất kỳ, công ty sẽ đóng các tuyến phà nối hai hòn đảo thuộc hai nhóm sau vài năm. Chứng minh rằng sau vài năm, có một đảo có thể nối với tất cả các đảo còn lại bởi các tuyến phà.
C7. Trong mặt phẳng, cho \displaystyle n\geq 2 đoạn thẳng sao cho hai đoạn thẳng bất kì cắt nhau tại một điểm nằm trên mỗi đoạn và không có ba đoạn thẳng nào đồng quy. Với mỗi đoạn thẳng thầy Minh chọn một đầu mút của nó rồi đặt lên đó một con ếch sao cho mặt con ếch hướng về đầu mút còn lại. Sau đó thầy vỗ tay \displaystyle n-1 lần. Mỗi lần vỗ tay con ếch ngay lập tức nhảy đến giao điểm gần nhất trên đoạn thẳng của nó. Tất cả những con ếch đều không thay đổi hướng nhảy của mình trong toàn bộ quá trình nhảy. Thầy Minh muốn đặt các con ếch sao cho sau mỗi lần vỗ tay không có hai con nào nhảy đến cùng một điểm.
(a) Chứng minh rằng thầy Minh luôn thực hiện được ý định của mình nếu \displaystyle n là số lẻ;
(b) Chứng minh rằng thầy Minh không thể thực hiện được ý định của mình nếu nếu \displaystyle n là số chẵn.
C8. Cho số nguyên dương \displaystyle n. Tìm số nguyên dương \displaystyle k nhỏ nhất có tính chất: có thể đánh dấu \displaystyle k ô đơn vị của bảng \displaystyle 2n\times 2n để tồn tại duy nhất cách chia bảng thành các mảnh \displaystyle 1\times 2 hay \displaystyle 2\times 1 sao cho không mảnh nào chứa hai ô đã được đánh dấu.

One thought on “IMO 2016 Shortlist – Combinatorics”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s