IMO Shortlist 2015 – Combinatorics


Mọi người xem phần đầu ở đây nhé: Algebra https://nttuan.org/2016/08/06/topic-807/. Dưới đây là phần Tổ hợp.

C1. Ở Lineland có n\geq1 thị trấn, được sắp xếp dọc một con đường từ trái sang phải. Mỗi thị trấn có một xe ủi trái (đặt bên trái của thị trấn và hướng sang trái) và một xe ủi phải (đặt bên phải của thị trấn và hướng sang phải). Kích thước của 2n xe ủi là đôi một khác nhau. Tại mỗi thời điểm khi một xe ủi trái đối diện một xe ủi phải, xe lớn hơn sẽ đẩy xe nhỏ hơn ra khỏi đường. Mặt khác, các xe ủi sẽ không được bảo vệ đằng sau; vì vậy, nếu một xe ủi húc vào đuôi của xe khác thì nó sẽ đẩy xe bị húc ra khỏi đường. Cho AB là hai thị trấn, với B nằm bên phải A. Ta nói A có thể quét B biến mất nếu xe ủi phải của A có thể di chuyển đến B và đẩy tất cả xe ủi mà nó gặp ra khỏi đường. Tương tự, B có thể quét A biến mất nếu xe ủi trái của B có thể di chuyển tới A và đẩy tất cả xe ủi mà nó gặp ra khỏi đường. Chứng minh rằng có đúng một thị trấn không bị quét biến mất bởi mỗi thì trấn còn lại.

C2. Ta nói tập hữu hạn \mathcal{S} các điểm trong mặt phẳng là cân bằng nếu với mỗi hai điểm khác nhau AB trong \mathcal{S}, tồn tại C trong \mathcal{S} sao cho AC=BC. Ta nói \mathcal{S}không tâm nếu với mỗi ba điểm phân biệt A, BC của \mathcal{S}, không tồn tại P trong \mathcal{S} sao cho PA=PB=PC.

(a) Chứng minh rằng với mỗi n\ge 3, tồn tại tập cân bằng chứa n điểm.

(b) Xác định tất cả n\ge 3 sao cho tồn tại tập cân bằng và không tâm chứa n điểm.

C3. Với tập hữu hạn các số nguyên dương A, một phân hoạch của A thành hai tập con khác rỗng A_1, A_2 được gọi là tốt nếu bội chung nhỏ nhất của các phần tử trong A_1 bằng ước chung lớn nhất của các phần tử trong A_2. Tìm số nguyên dương n nhỏ nhất sao cho tồn tại tập gồm n số nguyên dương với đúng 2015 phân hoạch tốt.

C4. Cho số nguyên dương n. Hai người chơi AB chơi một trò chơi chọn các số nguyên dương k \le n. Luật chơi là:

(i) Người chơi không được chọn số đã được chọn ở các bước trước.

(ii) Người chơi không được chọn số liên tiếp với các số đã được người đó chọn ở các bước trước.

(iii) Trò chơi sẽ kết thúc với kết quả hòa nếu không còn số nào để chọn; trong trường hợp còn lại, ai không chọn được sẽ thua.

A đi trước. Xác định kết quả của trò chơi, giả sử rằng cả hai cùng chơi giỏi.

C5. Cho dãy các số nguyên a_1,a_2,\dots thỏa mãn đồng thời hai điều kiện:

(i) 1\le a_j\le2015 với mỗi j\ge1,

(ii) k+a_k\neq \ell+a_\ell với mỗi 1\le k<\ell.

Chứng minh rằng tồn tại hai số nguyên dương bN sao cho

\displaystyle \left\vert\sum_{j=m+1}^n(a_j-b)\right\vert\le1007^2 với mỗi hai số mn thỏa mãn n>m\ge N.

C6. Cho S là tập khác rỗng các số nguyên dương. Một số nguyên dương được gọi là dọn dẹp nếu nó có thể biểu diễn duy nhất thành tổng của một số lẻ các phần tử khác nhau của S. Chứng minh rằng tồn tại vô hạn số nguyên dương không dọn dẹp.

C7. Trong một công ty có một số cặp là kẻ thù của nhau. Một nhóm người được gọi là không ưa giao tiếp nếu số thành viên trong nhóm là số lẻ lớn hơn 1, và có thể sắp xếp tất cả các thành viên của nhóm xung quanh một bàn tròn sao cho mỗi cặp ngồi cạnh nhau đều là kẻ thù của nhau. Biết có nhiều nhất 2015 nhóm không ưa giao tiếp, chứng minh rằng có thể chia công ty thành 11 phần sao cho trong mỗi phần không có hai người nào là kẻ thù của nhau.

2 thoughts on “IMO Shortlist 2015 – 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