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. Continue reading “IMO Shortlist 2015 – Combinatorics”

Nguyên lý bù-trừ


Mở đầu

Bài viết xem như sự mở đầu của phương pháp SÀNG trong các bài toán đếm. Ở phương pháp này, khi muốn đếm số phần tử của một tập A, ta bắt đầu với một tập B chứa A, sau đó tìm cách loại đi các phần tử không nằm trong A.

Chúng ta biết rằng nếu AB là các tập hữu hạn rời nhau thì |A\cup B|=|A|+|B|, tổng quát hơn ta có: Nếu AB là các tập hữu hạn bất kỳ(không nhất thiết rời nhau) thì  |A\cup B|=|A|+|B|-|A\cap B|, đây chính là nguyên lý bù-trừ cho hai tập hợp, dễ hiểu tại sao người ta lại gọi đây là nguyên lý bù trừ. Với n>1 tập hợp ta có định lý sau

Định lý. Nếu A_1,A_2,\cdots,A_n là các tập hữu hạn thì |\cup_{i=1}^nA_i|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+...+(-1)^{n+1}|\cap_{1\leq i\leq n}A_i|.

Ta sẽ chứng minh rằng rằng mỗi phần tử trong \cup_{i=1}^nA_i được đếm đúng một lần trong vế phải. Gọi x là một phần tử trong hợp đó và nó nằm trong dúng m tập A_i, khi đó trong vế phải nó sẽ được đếm đúng C_m^1-C_m^2+\cdots+(-1)^{m+1}C_m^m=1 lần (lưu ý (1-1)^m=0). Định lý được chứng minh.

Ngoài cách chứng minh trên các bạn có thể chứng minh Định lý bằng phương pháp quy nạp toán học, tôi chọn giới thiệu cách chứng minh đó vì phong cách Tổ hợp của nó.

Một áp dụng đẹp của nguyên lý bù-trừ là bài toán Bernoulli-Euler về các bức thư sai địa chỉ: Có n>1 bức thư khác nhau phải gửi đến n địa chỉ khác nhau. Có bao nhiêu cách gửi mà các bức thư đều đến không đúng địa chỉ của mình? Theo ngôn ngữ ánh xạ, bài toán được phát biểu như sau: Có bao nhiêu song ánh từ S={1,2,…,n} đến chính S sao cho nó không có điểm cố định? Ta đếm số các song ánh có điểm cố định, số này bằng C_n=|\cup_{1\leq i\leq n}A_i|, ở đây A_i là tập các song ánh nhận i làm điểm cố định. Theo nguyên lý bù-trừ dễ có C_n=\sum_{k=1}^nC_n^k(-1)^{k+1}(n-k)! và đáp số của bài toán là D_n=n!-C_n.

Bài tập.

Bài 1. Tìm số các số nguyên dương trong {1,2,…,500} chia hết cho 2 hoặc 3 hoặc 5.

Bài 2. Tính giá trị của phi hàm Euler tại n theo phân tích chính tắc của n.

Bài 3. Chứng minh nguyên lý bù-trừ bằng quy nạp toán học.

Bài 4. Cho X là một tập hữu hạn và A,B,C là các tập con của nó. Chứng minh rằng |\bar{A}\cap B|=|B|-|A\cap B||\bar{A}\cap\bar{B}\cap C|=|C|-|A\cap C|-|B\cap C|+|A\cap B\cap C|.

Bài 5. Tìm số các số nguyên trong tập {1,2,…,1000} không chia hết cho 5, không chia hết cho 7, nhưng chia hết cho 3.

Bài 6. Có bao nhiêu số nguyên dương n sao cho n là ước của ít nhất một trong hai số 10^{40}20^{30}?

Bài 7. Với mỗi số nguyên dương n>1, gọi A_n là số các song ánh từ S đến S sao cho f(k) khác k+1 với mỗi k=1,2,…,n-1.

a)Tính A_n;

b)Chứng minh rằng A_n=D_n+D_{n-1} với mỗi n>1.

Bài 8. Tìm số các số nguyên dương là ước của ít nhất một trong các số 10^{60},20^{50},30^{40}.

Bài 9. Với k=1,2,…,1992 cho A_k là một tập với 44 phần tử. Gỉa sử rằng |A_i\cap A_j|=1 với mỗi i,j khác nhau trong {1,2,…,1992}. Tính |\cup_{i=1}^{1992}A_i|.

Bài 10. Cho A_1,A_2,\cdots,A_n là n tập hữu hạn. Chứng minh rằng |\cup_{i=1}^nA_i|\geq \sum_{i=1}^n|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|. Sử dụng bất đẳng thức này để giải bài toán sau: Một hoán vị của {1,2,…,2n} được gọi là có tính chất P nếu có ít nhất hai số dạng k,n+k đứng cạnh nhau. Chứng minh rằng với mỗi số nguyên dương n, số các hoán vị có tính chất P nhiều hơn số các hoán vị không có tính chất đó.

Bài 11. Cho các số nguyên dương m\leq n và A,B là các tập có n,m phần tử tương ứng. Tìm số các toàn ánh từ A lên B. Từ đó suy ra \sum_{k=0}^n(-1)^kC_n^k(n-k)^n=n!.