Cực trị tập hợp

CỰC TRỊ TẬP HỢP 1 MỘT SỐ ĐỊNH LÝ QUAN TRỌNG 1. MỘT SỐ ĐỊNH LÝ QUAN TRỌNG Định nghĩa 1.1. Cho F là một họ các tập hợp con của một tập n phần tử X. Khi đó F được gọi là họ T giao nếu với mọi A, B ∈ F ta có A B 6= 0. / Định lý 1.2. Cho F là một họ giao của một tập n phần tử X. Khi đó |F | ≤ 2n−1 . Chứng minh. Lấy một tập con A ⊆ X. Khi đó với mỗi cặp tập con (A, X\A) của X, thì nhiều nhất là một trong hai tập A hoặc X\A thuộc vào F (vì nếu cả hai tập A, X\A đều thuộc vào F thì do A ∩ (X\A) = 0/ mâu thuẫn với F là một họ giao các tập con của X). Vì X có 2n tập con, và mỗi cặp tập con (A, X\A) có nhiều nhất một tập thuộc F . Do đó |F | ≤ 1 n · 2 = 2n−1 . 2 Định lý 1.3 (Định lý Erdos-Ko-Rado). Một họ F các k_tập (một tập hợp có k phần tử gọi là k_tập) n của một tập n phần tử X (k ≤ ). Khi đó 2   n−1 . |F | ≤ k−1 Chứng minh. 1. Với n, k là các số nguyên dương với n ≥ 2k. Một k_cung là một tập {i, i + 1, . . ., i + k}, với các số nguyên lấy theo modulo n. Một cách hình dung cho một k_cung như là k đoạn cung tròn liên tiếp, nối hai điểm i và i + k( mod n) trên đường tròn. Ta nói hai cung A và A′ giao nhau nếu chúng có chung nhau một đoạn cung tròn (k_cung và hai cung giao nhau được minh họa bởi hình dưới đây). an a1 3 − cung b an b a1 b A b a2 b a2 b cung chung b b b A′ b b b b b b b 2. Một họ {A1 , A2 , . . . , At } các k_cung giao nhau đôi một của [n] thì t ≤ k. Thật vậy, mỗi điểm i (điểm gắn cho một cung tròn) là điểm kết thúc của hai cung: một cung nhận i là điểm đầu tiên và một cung nhận i là điểm cuối cùng. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 1 CỰC TRỊ TẬP HỢP 1 MỘT SỐ ĐỊNH LÝ QUAN TRỌNG b i k-cung b b b b b b b k-cung b b b Do hai cung này không giao nhau, dẫn đến nhiều nhất một trong hai cung này thuộc vào họ F . Xét một cung A1 cho trước. Vì các cung còn lại đều phải giao với A1 một đoạn cung chung. Do đó các cung còn lại phải nhận một trong các điểm trong của cung A1 , là các điểm i1 , i2 , . . . , ik−1 , là điểm kết thúc. Vì mỗi điểm kết thúc có không quá một k_cung thuộc F , nên có k − 1 điểm kết thúc sẽ có không quá k_cung thuộc F , cộng với cung A1 thì có không quá k_cung thuộc tập F. i+1 i+2 b b i b k-cung A1 b b b b b b b b b b i+k−1 i+k b b b b 3. Bây giờ xét một hoán vị của [n] có dạng (a1 , a2 , . . . , an ). Ta đánh dấu các đoạn cung tròn bởi các số ai như hình vẽ ban đầu. Mỗi một tập của F xem như là một k_cung của hoán vị này. Theo kết quả trên, thì với một hoán vị này ta có ≤ k các k_cung. • Lấy tổng hết tất cả các hoán vị [n] trên đường tròn, có (n − 1)! hoán vị, thì ta thấy có nhiều nhất là k(n − 1)! các tập như thế này. • Tuy nhiên, khi sắp xếp trên đường tròn và trong cách đếm trên, tập A1 được đếm làm nhiều lần (vì sắp xếp trên đường tròn, thì tập A1 hay bất kỳ tập nào lấy để làm thứ tự là giống nhau). Vì trong nhiều lần hoán vị của (n − 1)!, sẽ tạo ra những hoán vị khác nhau, nhưng phần tử của A1 vẫn như vậy. Do đó có k! cách sắp xếp các phần tử của A1 và (n − k)! cách sắp xếp các phần tử bù của tập A1 . Do đó |F |k!(n − k)! ≤ k(n − 1)!   n−1 k(n − 1)! = . ⇒ |F | ≤ k−1 k!(n − k)! Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 2 CỰC TRỊ TẬP HỢP 1 MỘT SỐ ĐỊNH LÝ QUAN TRỌNG Định lý 1.4 (Bollobas). Cho A1 , A2 , . . . , Am và B1 , B2, . . . , Bm là các tập con của S = [n]. Đặt ai = |Ai | và bi = |Bi | với mọi i = 1, 2, . . . , m. Giả sử Ai ∩ B j = 0/ khi và chỉ khi i = j. Khi đó   ai + bi −1 ≤ 1. ∑ ai i=1 m Chứng minh. 1. Với mỗi hoán vị trong số n! hoán vị các phần tử của S, ta nói một hoán vị π là chứa B sau A nếu tất cả các phần tử của A đều đứng trước các phần tử của B trong π . 2. Với một hoán vị π có tính chất chứa Bi sau Ai , mà cũng có thêm tính chất chứa B j sau A j , khi đó Ai ∩ B j = 0/ (nếu Ai đứng trước B j , minh họa hình dưới) các vị trí cho các phần tử của Ai các vị trí cho các phần tử của Bi π các vị trí cho các phần tử của B j các vị trí cho các phần tử của A j hoặc A j ∩ Bi = 0/ (khi Ai kết thúc sau B j ). Nhưng điều này mâu thuẫn với giả thiết Ai ∩ B j = 0/ khi và chỉ khi i = j. Do đó, với mỗi hoán vị π , tồn tại nhiều nhất một chỉ số i để π chứa Bi sau Ai . 3. Ngược lại, với mỗi i ∈ {1, 2, . . . , m}, ta đếm số hoán vị mà Ai đứng trước Bi .
n • Chọn ai + bi ví trí để sắp xếp cho Ai và Bi , ta có ai +b cách. i • Đặt ai phần tử của Ai vào ai vị trí đầu tiên trong ai + bi ví trí vừa chọn có ai ! cách, sau đó sắp xếp bi các phần tử của Bi vào các vị trí còn lại có bi ! cách. Vậy có ai !.bi ! cách sắp xếp Ai trước Bi . • Sắp xếp n − ai − bi phần tử còn lại của S vào n − ai − bi vị trí còn lại có (n − ai − bi )! cách. Vậy ta có  n · ai ! · bi ! · (n − ai − bi )! = ai + bi  4. Lấy tổng số tất các các chỉ số i = 1, 2, . . . , m ta có m ∑ i=1 Định lý được chứng minh. n! ai +bi ai
.   ai + bi −1 ≤ n! ⇒ ∑ ≤ 1. ai +bi
a i i=1 n! m ai Định nghĩa 1.5. Cho S là một tập hợp hữu hạn. Một họ các tập con A1 , A2 , . . . , An của S được gọi là một xích nếu Ai ⊂ Ai+1 và |Ai+1 | = |Ai | + 1 ∀i = 1, 2, . . . , n. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 3 CỰC TRỊ TẬP HỢP 1 MỘT SỐ ĐỊNH LÝ QUAN TRỌNG Định nghĩa 1.6. Cho P là một tập hợp hữu hạn. Một họ các tập con A1 , A2 , . . . , An của S được gọi là một phản xích nếu Ai 6⊂ A j , ∀i 6= j. Định lý 1.7 (Bất đẳng thức LYM, Lubell, Yamamoto, Meshalkin). Cho F là một phản xích trong [n] (ta dùng ký hiệu [n] thay cho {1, 2, . . . , n}). Khi đó ta có bất đẳng thức  −1 n ∑ |A| ≤ 1. a∈F Chứng minh. 1. Gọi C là tập hợp tất cả các xích C, mỗi xích C gồm n tập hợp, mỗi tập hợp là một tập con của [n] và đây là xích chứa nhiều phần tử nhất, C1 ⊂ C2 ⊂ . . . ⊂ Cn , |Ci | = i, ∀i = 1, 2, . . . , n. Hỏi C có bao nhiêu phần tử? (mỗi phần tử thuộc C là một xích độ dài n). Xét một xích C ∈ C thì • Có n cách chọn cho tập C1 . Thật vậy, vì |C1| = 1 nên C1 ∈ {{1}, {2}, . . . , {n}}. • Với mỗi cách chọn tập C1 , có n − 1 cách chọn tập C2 . Thật vậy, minh họa cho C1 = {3}, khi đó C2 ∈ {{3, 1}, {3, 2}, {3, 4}, . . . , {3, n}}. • Cứ tiếp tục như vậy, ta có n − 2 cách chọn tập C3 , n − 3 cách chọn tập C4 , . . . và cuối cùng là 1 cách chọn tập Cn vì Cn = [n]. Vậy C có n! phần tử. 2. Một tập A ⊂ [n] thì A có thể vừa thuộc vào xích C , vừa thuộc vào đối xích F. Do đó ta đi đếm số cặp N = {(A,C)| với C ∈ C và A là một tập hợp vừa thuộc xích C vừa thuộc đối xích F}. • Với mỗi C ∈ C , có nhiều nhất một tập A mà A ∈ C và A ∈ F. Thật vậy, giả sử có hai tập A1 , A2 vừa thuộc vào C, vừa thuộc vào F. Vì A1 , A2 thuộc xích C nên hoặc A1 ⊂ A2 hoặc A2 ⊂ A1 , nhưng khi đó thì A1 , A2 không thể thuộc vào F được, vì các tập con của F không có tập nào là tập con của tập khác. Vậy |N| ≤ n! • Với mỗi tập A ∈ F mà |A| = k. Khi đó có k! cách chọn các tập A1 , A2 , . . . , Ak−1 (cách đếm giống hệ ý 1) mà A1 ⊂ A2 ⊂ . . . ⊂ Ak−1 ⊂ A, |Ai | = i, ∀i = 1, 2, . . . , k − 1 và có (n − k)! cách chọn các tập Ak+1 , . . . An mà A ⊂ Ak+1 ⊂ . . . ⊂ An , Suy ra mỗi A ∈ F ta có |A j | = j, ∀ j = k + 1, k + 2, . . ., n. k!(n − k)! = |A|!.(n − |A|)! cách chọn xích C chứa A. Do đó |N| = ∑ |A|!(n − |A|)!. A∈F Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 4 CỰC TRỊ TẬP HỢP 1 MỘT SỐ ĐỊNH LÝ QUAN TRỌNG Từ hai cách đếm trên, ta có |A|!(n − |A|)! ≤1 n! A∈F ∑ |A|!(n − |A|)! ≤ n! ⇒ ∑ A∈F đây chính là điều phải chứng minh. Nhận xét 1. Bất đẳng thức LYM có thể dễ dàng suy ra từ định lý Bollobas, định lý 1.4 bằng cách, đặt F = {A1 , A2 , . . . , Am } và đặt Bi = [n]\Ai . Khi đó điều kiện Ai ∩ Bi = 0/ thỏa mãn và điều kiện Ai ∩ B j 6= 0/ trở thành Ai 6⊆ A j , tức là điều kiện của một phản xích. Chú ý là bi = n − ai . Đến đây thì  −1  n  n ai + bi −1 =∑ ≤ 1. ∑ ai i=1 ai i=1 m Định lý 1.8. Một họ F các tập con của tập n phần tử X được gọi là không so sánh được nếu A, B là hai phần tử bất kỳ của F thì A 6⊆ B. Định lý 1.9 (Định lý Sperner). Cho F là một họ không so sánh được các tập con của tập n phần tử X. Khi đó [n] |F | ≤ Cn 2 . Chứng minh. Mặt khác, theo tính chất của nhị thức Newton thì hệ số trong khai triển (1 + x)n thỏa tính chất           n n n n n < . . . <  n−1  <  n  . < < 2 1 0 2 2 Áp dụng vào ta có     n n < n . kj 2 Thay vào (*) ta có đánh giá m. m 1 n n 2 [ ]
≤ ∑ 1 n j=1 k j
≤ 1. hni phần tử Từ đây ta có điều phải chứng minh. Dấu bằng xảy ra khi B chứa tất cả các tập con gồm có 2 của tập B. Hệ quả 1.10 (Bất đẳng thức Lubell). Cho F là một họ không so sánh được các tập con của tập n phần tử X. Gọi ak là số các k_tập con thuộc F . Khi đó n ak ∑ Ck ≤ 1. k=1 n Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 5 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP 2. MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP 2.1. KHOẢNG CÁCH HAMMING - CHẶN PLOTKIN Cho n là số nguyên dương, ký hiệu [0, 1]n = {x1 x2 . . . xn |xi ∈ {0, 1}, i = 1, 2, . . . , n} là tập tất cả các xâu nhị phân độ dài n. Định nghĩa 2.1. Cho hai xâu nhị phân x = x1 . . . xn và y = y1 . . . yn . Khi đó khoảng cách giữa hai xâu x và y được định nghĩa là d(x, y) = số vị trí i mà xi 6= yi . Khoảng cách này gọi là khoảng cách Hamming thỏa tất cả các điều kiện của một khoảng cách • d(x, x) = 0, ∀x ∈ [0, 1]n ; • d(x, y) > 0, ∀x 6= y ∈ [0, 1]n ; • d(x, y) = d(y, x), ∀x, y ∈ [0, 1]n ; • d(x, z) ≤ d(x, y) + d(y, z), ∀x, y, z ∈ [0, 1]n. Định nghĩa 2.2. Cho d là số nguyên dương. Gọi C là tập hợp tất các các xâu nhị phân trong [0, 1]n sao cho d(x, y) ≥ d, ∀x 6= y ∈ C. Định lý 2.3 (PLOTKIN). Cho n, d là các số nguyên dương. Đặt M = |C|. Khi đó 1. Nếu d chẵn, 2d > n thì 2. Nếu d lẻ, 2d + 1 > n thì   d M≤2 . 2d − n  d +1 . M≤2 2d + 1 − n  Để chứng minh định lý, ta sử dụng một số nhận xét sau: Bổ đề 2.4. Giả sử N, M là các số nguyên dương và 0 ≤ N ≤ M thì ( 2 M nếu M chẵn N(M − N) ≤ M42 −1 nếu M lẻ. 4 Bổ đề 2.5. Nếu x ∈ R thì [2x] ≤ 2[x] + 1. Bổ đề 2.6. Cho v là xâu nhị phân ∈ [0, 1]n. Khi đó d(v + w) bằng với số số 1 xuất hiện trong v + w. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 6 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Chứng minh. Bằng việc kiểm tra tất cả các khả năng của vi và wi , ta thấy ( 0 nếu vi = wi (v + w)i = 1 nếu vi 6= wi . Do đó d(v, w) = |{i|vi 6= wi }| = |{i|(v + w)i = 1}|.
Chứng minh định lý với d chẵn. Ta viết ma trận A = M2 × n, với mỗi dòng là một phần tử u + v, với u, v ∈ C. Ta đếm số lần xuất hiện số 1 trong ma trận trên. 1. Ta đếm số lần xuất hiện số 1 trong mỗi cột. Xét một cột j. Lấy một dòng tùy ý, giả sử dòng đó là xâu nhị phân của u + w, khi đó số 1 xuất hiện ở cột j nếu và chỉ nếu v và w có một số 1 ở vị trí j, xâu còn lại có số 0 ở vị trí j. Gọi N là số xâu ký tự trong C có số 1 ở vị trí j, khi đó số cách chọn cặp u, w sao cho v + w có số 1 ở vị trí j là N(M − N). Khi đó số số 1 xuất hiện trong cột thứ j là ( 2 M nếu M chẵn N(M − N) ≤ M42 −1 nếu M lẻ. 4 Điều này đúng cho mọi j = 1, 2, . . . , n. Do đó số số 1 xuất hiện trong ma trận A là ( 2 n M4 nếu M chẵn 2 n M 4−1 nếu M lẻ. 2. Ta đếm số lần xuất hiện số 1 trong mỗi dòng. Với một dòng chứau + w. Ta đã biết số số 1 trong dòng đó là d(v, w). Mà theo giả thiết thì d(v, w) ≥ d. Do đó có ít nhất d số 1 trong mỗi dòng. Do đó số các số 1 trong A ít nhất là   M · d. 2 Từ đây ta thấy 1. Nếu M chẵn. Khi đó kết hợp hai kết quả trên thì   M2 M ≤ n· 4 2 2 dM dM M2 ⇒ − ≤ n· 2 2 4 2 ⇒ (2d − n)M ≤ 2dM. Theo giả thiết thì 2d − n và M đều là các số nguyên dương, nên M≤ 2d . 2d − n Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 7 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Lại vì M là số nguyên dương nên mà M chẵn, và 2  d 2d−n     d 2d ≤2 + 1; M≤ 2d − n 2d − n  + 1 lẻ nên 2. Nếu M lẻ, thì Do đó (2d − n)M ≤ n nên  d . M≤2 2d − n    M M+1 M2 − 1 M ⇒d· ≤n . ≤n d· 4 2 4 2 M≤ Do M là số nguyên, ta được n 2d = − 1. 2d − n 2d − n   2d M≤ −1 2d − n   2d = −1 2d − n   d +1−1 ≤2 2d − n   d =2 , 2d − n tức chúng ta đã có được chặn Plotkin cho d chẵn. Ví dụ 2.1.1 (Vĩnh Phúc 2012). Có 7 em học sinh tham gia vào m nhóm hoạt động ngoại khóa, mỗi học sinh có thể tham gia nhiều nhóm hoạt động. Biết rằng với hai nhóm tùy ý thì có ít nhất 4 học sinh chỉ tham gia vào một trong hai nhóm đó. Tìm giá trị lớn nhất có thể có của m. Chứng minh. Gọi bảy học sinh là a1 , a2 , . . . , a7 và đặt X = {a1 , a2 , . . . , a7 }. Ta mỗi nhóm là một xâu nhị phân x1 x2 . . . x7 , trong đó xi = 1 nếu nhóm đó chứa ai và xi = 0 nếu nhóm đó không chứa ai . Xét hai nhóm A, B tùy ý trong số m nhóm, khi đó có ít nhất 4 học sinh, giả sử là a1 , a2 , a3 , a4 . Gọi hai xâu biểu diễn cho A, B là v, w. • Nếu {a1 , a2 , a3 , a4 } ∈ A thì ai 6∈ B, ∀i = 1, 2, 3, 4. Khi đó hai xâu có dạng v 1 b w 0 b 1 b b 0 1 b b 0 1 b b 0 b b b b b b Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 8 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Khi đó d(v, w) ≥ 4. • Nếu a1 ∈ A, {a2 , a3 , a4 } ∈ B. Khi đó hai xâu có dạng v b 1 b w 0 b b 0 b 1 b 0 b 1 b 0 b 1 b b b b b Khi đó d(u, v) ≥ 4. Xét tất cả các trường hợp tương tự, ta luôn có d(v, w) ≥ 4 với mọi v, w. Vậy d = 4, n = 7. Khi đó theo định lý 3.3 thì   4 = 8. m≤2 2.4 − 7 Khi đó m ≤ 8. Với m = 8 ta có một cách xây dựng các nhóm là, với a, b, c, d, e, f , h là 7 học sinh A1 : a b c A2 : a d e A3 : a f g A4 : b A5 : b d f e A6 : c d A7 : c g f e f A8 : a b c d e f g Ví dụ 2.1.2 (China TST 1994). Cho A1 , A2 , . . . , Ak là các tập con của X = {1, 2, . . . , 10} sao cho ( |Ai | = 5, ∀i = 1, 2, . . . , k |Ai ∩ A j | ≤ 2, ∀1 ≤ i < j ≤ k. Tìm giá trị lớn nhất có thể có của k. Chứng minh. Ta coi mỗi tập con At là một xâu nhị phân dạng x1 . . . x10 , trong đó xi = 1 nếu i ∈ At và xi = 0 nếu i 6∈ At . Do |Ai ∩ A j | ≤ 2, ∀1 ≤ i < j ≤ k nên suy ra d(x, y) ≥ 6. v b 1 w 1 b b b 1 1 b b 1 0 b b 0 0 b b 1 0 b b 0 1 b b 0 1 b b 0 0 b b 0 1 b b 1 0 Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 9 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP (Giả sử xâu v biểu diễn cho Ai , xâu w biểu diễn cho A j . Nếu |Ai ∩ A j | = 2 thì có hai xâu v, w chỉ có đúng hai số 1 trùng nhau vị trí. Như hình bên minh họa cho hai số 1 ngoài cùng bên trái. Đối với xâu v còn 3 số 1, tương ứng 3 vị trí đó của xâu w phải là số 0 và ngược lại đối với xâu w còn 3 số 1, tương ứng 3 ví trí đó của xâu v phải là số 0. Trong trường hợp này là d(v, w) = 6. Nếu |Ai ∩ A j | = 1 hay Ai ∩ A j = 0/ thì rõ ràng d(x, y) > 6.) Theo định lý 3.3 thì   6 k≤2 = 6. 2.6 − 10 Vậy k lớn nhất bằng 6, và dưới đây là một cách xây dựng các tập A1 : 1 2 3 4 5 A2 : 2 3 A3 : 6 7 8 3 4 A4 : 8 9 10 4 5 6 7 A5 : 1 5 6 A6 : 1 2 9 8 7 10 9 10 Cách xây dựng 6 tập hợp trên không phải là duy nhất. Dưới đây cũng là 6 tập hợp thỏa mãn A1 : 1 2 3 4 5 A2 : 1 2 A3 : 1 A4 : A5 : A6 : 6 7 8 3 2 6 4 3 9 10 7 5 9 10 7 8 4 5 6 10 8 9 Ví dụ 2.1.3 (PTNK 2012). Cho số nguyên dương n và tập hợp X = {1, 2, 3, . . . , 4n}. Hai tập con A, B của X được gọi là không giống nhau nếu |A∆B| ≥ 2n + 1, với A∆B = (A\B) ∪ (B\A). Xét m tập hợp A1 , A2 , . . . , Am là các tập con đôi một không giống nhau của X. Chứng minh rằng 4(n + 1) . m≤ 3 Chứng minh. Ta đồng nhất mỗi tập At là một xâu nhị phân độ dài 4n x1 x2 . . . x4n với xi = 1 nếu i ∈ At và xi = 0 nếu i 6∈ At . Xét hai tập Ai , A j tùy ý trong m tập, gọi v, w là hai xâu nhị phân biểu diễn của chúng. Do |A∆B| ≥ 2n + 1 Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 10 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP nên tương tự như ví dụ 3.1 thì d(v, w) ≥ 2n + 1. Từ đó suy ra d = 2n + 1. Do 2.d = 4n + 2 > 4n, nên theo định lý 3.3 thì     2n + 1 + 1 2n + 2 4(n + 1) m≤2 . =2 ≤ 4n + 2 + 1 − 4n 3 3 Ví dụ 2.1.4 (Inspired IMO 1998). Trong một cuộc thi có n thí sinh và p giám khảo, ở đó n, p là các số nguyên dương, p > 2. Mỗi giám khảo đánh giá từng thí sinh và cho kết luận thí sinh đó đỗ hay trượt. Giả sử k là số thỏa mãn điều kiện: với hai giám khảo tùy ý, số thí sinh mà họ cho kết quả giống nhau nhiều nhất là k. Chứng minh rằng k p−2 ≥ . n 2(p − 1) Chứng minh. Giả sử n thí sinh là S1 , S2 , . . . , Sn . Mỗi giám khảo cho tương ứng với một xâu nhịn phân độ dài n: x1 x2 . . . xn với xi = 1 nếu thí sinh Si đỗ và xi = 0 nếu thí sinh Si rớt. Theo điều kiện bài toán thì d = n − k. Xét hai trường hợp 1. Nếu 2(n − k) ≤ n thì p−2 k 1 ≥ > . n k 2(p − 1) 2. Nếu 2(n − k) > n, xét hai khả năng xảy ra • Nếu n − k chẵn, theo định lý 3.3 thì   n−k n−k 2(n − k) p≤2 ≤2 = . 2(n − k) − n 2(n − k) − n n − 2k Do đó p(n − 2k) ≤ 2n − 2k ⇒ p−2 k ≥ . n 2(p − 1) • Nếu n − k lẻ, theo định lý 3.3 thì   n−k+1 n−k+1 2(n − k + 1) p≤2 ≤2 = . 2(n − k) + 1 − n 2(n − k) + 1 − n n − 2k + 1 Do đó p(n − 2k + 1) ≤ 2n − 2k + 2 ⇒ Bài toán được chứng minh hoàn toàn. k p−2 n+1 p−2 ≥ . > . n 2(p − 1) n 2(p − 1) Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 11 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP 2.2. SỬ DỤNG CÁC NGUYÊN LÝ TỔ HỢP Ví dụ 2.2.1. Gọi A là tập tất cả các số tự nhiên lẻ không chia hết cho 5 và nhỏ hơn 30. Tìm số k nhỏ nhất sao cho mỗi tập con của A gồm k phần tử đều tồn tại hai số chia hết cho nhau. Giải. Ta có A = {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29}, |A| = 12. Xét tập B = {9, 11, 13, 17, 19, 21, 23, 29}. Khi đó hai phần tử bất kì thuộc B thì không chia hết cho nhau. Từ đó ta suy ra được k ≥ 9. Ta chứng minh k = 9 thỏa đề bài. Xét S là một tập con bất kì của A và |S| = 9. Xét ba cặp {21, 7}, {27, 9}, {1, 11} ta thấy mỗi cặp là bội của nhau. Nếu trong 3 cặp trên có ít nhất một cặp thuộc S thì bài toán được giải quyết. Giả sử trong ba cặp trên không có cặp nào cùng thuộc S, do |S| = 9 nên S phải chứa một số trong mỗi cặp và chứa 6 số còn lại. Từ đó suy ra trong S phải có cặp {3, 9} hoặc {3, 27} và mỗi cặp này là bội của nhau. Hay nói cách khác trong S luôn tồn tại hai số chia hết cho nhau. Vậy min k = 9. Nhận xét 2. Mấu chốt trong bài toán trên là chúng ta phát hiện ra tập A0 để từ đó ta khẳng định được k ≥ 9 và dự đoán min k = 9. Để tìm tập B, ta liệt kê hết các số trong A mà không có hai số nào là bội của nhau. Với bài toán này, việc tìm ra tập B khá đơn giản. Ví dụ 2.2.2 (KMO 1990). Cho n tập hợp A1 , A2 , . . . , An thỏa mãn   |Ai | = 30, ∀i = 1, 2, . . . , n |Ai ∩ A j | = 1, ∀i 6= j   / A1 ∩ A2 ∩ · · · ∩ An = 0. Chứng minh n < 872. Chứng minh. 1. Giả sử n ≥ 872. Xét tập hợp A1 , |A1 | = 30. Do |Ai ∩ A1 | = 1, ∀i = 2, 3, . . . , n nên theo nguyên lý Dirichlet, tồn tại phần tử a ∈ A1 thuộc vào ít nhất là   hni 872 +1 ≥ + 1 = 30 30 30 tập hợp. Không mất tính tổng quát, gọi các tập hợp đó là A2 , A3 , . . . , A31 . 2. Vì A1 ∩ A2 ∩ . . . ∩ An = 0, / nên tồn tại một tập B trong số các tập A32 , . . . , An không chứa phần tử a. 3. Xét 31 tập hợp A2 , A3 , . . . , A31 và B với a ∈ A j , ∀ j = 2, 3, . . . , 30 và a 6∈ B. • Vì |A j ∩ B| = 1, ∀ j = 2, 3, . . . , 31, các tập A j đều chứa a, còn B không chứa a, nên {x j } = A j ∩ B thì x j ∈ B\{a}. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 12 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP • Có 31 phần tử x2 , . . . , x31 trong tập B\{a}, mỗi phần tử trong chúng thuộc vào ít nhất một tập hợp trong 30 tập A j , j ∈ {2, . . . , 31}, nên tồn tại một phần tử xt , với t ∈ {2, 3, . . . , 29} thuộc vào hai tập hợp Ar , As (r, s ∈ {2, 3, . . . , 31}). • Khi đó {a, xt } ⊂ Ar ∩ As , mâu thuẫn với giả thiết |Ar ∩ As | = 1. Vậy điều giả sử là sai. Bài toán được chứng minh. Ví dụ 2.2.3 (China TST1994, Ví dụ 3.1.2). Cho A1 , A2, . . . , Ak là các tập con của X = {1, 2, . . . , 10} sao cho ( |Ai | ≥ 5, ∀i = 1, 2, . . . , k |Ai ∩ A j | ≤ 2, ∀1 ≤ i < j ≤ k. Tìm giá trị lớn nhất có thể có của k. Chứng minh. Trong ví dụ 3.1.2 ta đã giải bài toán này bằng chặn Plotkin, và xây dựng được với k = 6. Do đó k ≥ 6. Nếu k ≥ 7, ta trình bày một lời giải kết hợp đếm số tập hợp chứa phần tử và nguyên lý bao hàm loại trừ (inclusion - exclusion principle). Với mỗi i ∈ X, đặt ni = |{ j ∈ {1, 2, . . . , k|i ∈ A j }}| tức đếm số tập hợp trong A1 , A2 , . . . , Ak chứa phần tử i. Khi đó 10 ∑ ni = i=1 k ∑ |Ak | ≥ 5k = 35. j=1 Do đó phải tồn tại chỉ số i0 sao cho ni0 ≥ 4, vì nếu tất cả ni ≤ 3 thì ∑10 i=1 ni ≤ 3 × 10 = 30, mâu thuẫn với đánh giá trên. Tức là tồn tại một phần tử i0 trong X thuộc vào ít nhất 4 tập hợp trong k tập A1 , A2 , . . . , Ak . Không mất tính tổng quát, giả sử i0 thuộc vào 4 tập hợp A1 , A2 , A3 , A4 . Khi đó với mọi 1 ≤ i < j < t ≤ 4 thì |Ai ∩ A j ∩ At | ≥ |A1 ∩ A2 ∩ A3 ∩ A4 | ≥ 1. Theo nguyên lý IE thì 10 = |X| ≥ |A1 ∪ A2 ∪ A3 ∪ A4 | 4 = ∑ |Ai | − i=1 ∑ 1≤i< j≤4 |Ai ∩ A j | + ∑ 1≤i< jB i∈I i∈II Gọi T là một cách chia như thế. Nếu i∈I i∈II thì chọn cách này. Nếu i∈I i∈II không mất tính tổng quát, giả sử ∑ bi > ∑ bi ⇒ ∑ bi − ∑ bi > B. i∈I i∈II i∈I i∈II Khi đó tồn tại j ∈ I, k ∈ II sao cho b j > bk . Khi đó ta chỉ việc đổi chỗ (a j , b j ) từ nhóm I sang nhóm II và (ak , bk ) từ nhóm II sang nhóm I (cách đổi chỗ này không ảnh hưởng đến điều kiện (1)). Khi đó ∑ bi i∈I Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 15 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP sẽ giảm đi ít nhất 1, còn ∑ bi sẽ tăng lên ít nhất 1. Do đó i∈I ∑ bi − ∑ bi i∈I i∈II sẽ giảm đi ít nhất là 2. Nếu sau khi đổi chỗ mà thỏa điều kiện (2) thì dừng, nếu chưa thỏa thì tiếp tục làm như trên sẽ đến lúc thỏa vì hiệu trên giảm ngặt trên tập số nguyên dương. Vậy ta luôn chia được thành 2 nhóm sao cho ∑ ai − ∑ ai ≤A ∑ bi − ∑ bi ≤ B. i∈II i∈I i∈II i∈I Trong hai nhóm I và II, thì tổng số cam trong mỗi nhóm đã được xác định, nên ta sẽ chọn được nhóm nào số số cam nhiều hơn. Giả sử nhóm I. Khi đó thêm 2 thùng đã lấy ra cho vào nhóm I, thì số cam lấy ra lớn hơn 1 nửa và −A ≤ ∑ ai − ∑ ai ≤ A ⇒ ∑ ai ≤ ∑ ai + A, i∈I i∈II i∈II i∈I tức số Táo thỏa mãn điều kiện. Tương tự kiểm tra cho số Xoài. Ví dụ 2.2.7. Cho X là một tập hợp hữu hạn, |X| = n và A1 , A2 , . . . , Am là các tập con của X thỏa mãn |Ai | ≥ 2, ∀i = 1, 2, . . . , n và |Ai ∩ A j | = 6 1, ∀1 ≤ i < j ≤ m. Chứng minh rằng có thể tô các phần tử của X bằng hai màu, mỗi phần tử tô một màu, sao cho mọi tập Ai đều chứa các phần tử được tô cả hai màu. Chứng minh. 1. Giả sử X = {x1 , x2 , . . . , xn }. Giả sử kết luận bài toán sai. Trong tất cả các cách tô màu mỗi phần tử của tập X, chọn cách tô được một tập con cực đại của X, giả sử Y = {x1, x2 , . . . , xk }(k < n) thỏa mãn bài toán theo nghĩa: nếu thêm phần tử xk+1 vào Y thì không thể tô màu cho xk+1 được để thỏa mãn bài toán. 2. Điều đó dẫn đến sẽ có hai tập, giả sử là Ar , As chứa xk+1 và Ar , As ⊆ {x1 , x2 , . . . , xk , xk+1 } sao cho • Nếu xk+1 được tô màu xanh thì Ar ∩Y gồm toàn các phần tử màu xanh; • Còn nếu xk+1 được tô màu đỏ thì As ∩Y gồm toàn các phần tử màu đỏ. Nhưng khi đó thì Ar ∩ As = {xk+1 }, mâu thuẫn với giải thiết bài toán. Vậy điều giả sử là sai. Bài toán được chứng minh. Ví dụ 2.2.8 (2000 Hungarian-Israeli). Đặt S = {1, 2, . . . , 2000}. Nếu A và B là hai tập con của S, ta ký hiệu |A| và |B| là số phần tử trong tập A và tập B tương ứng. Giả sử rằng |A|.|B| ≥ 3999. Chứng minh rằng khi đó hai tập hợp A − A và B − B chứa ít nhất một phần tử chung. Ký hiệu X − X = {s − t, s ∈ X và t ∈ X, s 6= t}. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 16 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Giải. Đặt T = {(a, b)|a ∈ A, b ∈ B} thì |T | = |A|.|B| ≥ 3999. Tập W = {a + b|a ∈ A, b ∈ B} là một tập con của tập {2, 3, . . . , 4000}. Nếu W = {2, 3, . . . , 4000} thì vì hai số 2 và 4000 đều nằm trong W nên suy ra cả hai tập A và B đều chứa hai số 1 và 2000. Suy ra hai tập A − A và B − B đều có một phần tử chung là 1999. Nếu W 6= {2, 3, . . . , 4000} thì W có ít hơn 3999 phần tử. Theo nguyên lý Dirichlet, phải tồn tại hai cặp (a, b) 6= (a′, b′ ) trong T để a + b = a′ + b′ =⇒ a − a′ = b − b′ . Khi đó hai tập hợp A − A và B − B đều chứa chung một phần tử là a − a′ = b − b′ . Ta có điều phải chứng minh. 2.3. THIẾT LẬP ÁNH XẠ GIỮA CÁC TẬP HỢP Ví dụ 2.3.1 (Italy 2000). Cho X là một tập hợp hữu hạn với |X| = n, và đặt A1 , A2 , . . . , Am là các tập T con chứa 3 phần tử của X thỏa mãn |A A j | ≤ 1 với mọi i 6= j. Chứng tỏ tồn tại tập con A của X chứa i √ ít nhất [ 2n] phần tử mà không nhận bất cứ tập Ai (i = 1, 2, . . . , m) nào là tập con của nó. 1. Để tập A không chứa bất kỳ tập Ai nào làm tập con, thì lẽ tự nhiên tập A chứa càng ít phần tử càng tốt. √ 2. Tuy nhiên đề bài lại yêu cầu |A| ≥ 2n, tức một chặn dưới cho |A|. Nghĩa là đề bài yêu cầu tồn tại tập A có số lượng phần tử "tương đối" nhiều. Để làm việc với những tập tương đối nhiều phần tử, thông thường ta làm trên tập có nhiều phần tử nhất. Giả sử A là một tập con của X mà không chứa bất kỳ một tập Ai nào, với số phần tử lớn nhất. Đặt k = |A|. Giải. • Ý nghĩa như sau: bất kỳ tập con nào của X có số phần tử > k, sẽ đều chứa một tập con Ai nào đó. • Do đó ta sẽ khảo cứu những tập vi phạm sinh ra từ A, những tập đó bằng tập A thêm một phần tử ngoài A, tức thêm vào A một phần tử của tập X\A. 3. Cách 1. Vì |A| chứa k phần tử nên X\A có n − k phần tử. 4. Cách 2. Xét x là một phần tử của X nhưng không thuộc A, x ∈ X\A. Theo tính tối đại của tập A, thì S A {x} sẽ không thỏa mãn điều kiện bài toán. Nghĩa là sẽ tồn tại một chỉ số i(x) ∈ {1, 2, . . . , m} sao cho [ Ai(x) ⊆ A {x}. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 17 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Ai(x) x b A X\A Ai(y)y b Vì Ai(x) 6⊂ A và Ai(x) ⊆ A {x} nên x ∈ Ai(x) . Từ đó suy ra S Ai(x) \{x} ⊂ A. Vì mỗi tập Ai có ba phần tử nên Ai(x) \{x} chỉ có hai phần tử, mà nó lại là tập con của A, dẫn đến tập \ Lx = A Ai(x) có đúng hai phần tử. Lại theo giả thiết bài toán |Ai A j | ≤ 1 với mọi i 6= j nên các tập Lx đều là các tập phân biệt (theo nghĩa, hai tập hợp Lx và Ly , ở đây x 6= y thuộc X\A thì Lx 6= Ly . Vì nếu T Lx = Ly , giả sử Lx = Ly = {a, b}. Khi đó {a, b} ⊂ Ax , {a, b} ⊂ Ay , dẫn đến Ax Ay = {a, b}, mâu thuẫn). T 5. Từ đó chúng ta đã xác lập được một đơn ánh từ tập X\A đến tập hợp chứa các tập hai phần tử của A. Do đó theo tính chất đơn ánh thì √   k k2 − k −1 + 1 + 8n √ 2 n−k ≤ = =⇒ k + k ≥ 2n =⇒ k ≥ > 2n − 1. 2 2 2 √ √ Vì k nguyên và k > 2n − 1 nên k ≥ [ 2n]. Ví dụ 2.3.2 (AMM, E3459). Cho X là một tập hợp, |X| = n ≥ 12 và F = {A1 , A2 , . . . , Am } là họ các 4_tập của X sao cho |Ai ∩ A j | ≥ 2, ∀i 6= j ∈ {1, 2, . . . , m}. √ Chứng minh rằng tồn tại một tập con S của S, |S| ≥ 3 6n − 6 sao cho Ai 6⊂ S, ∀i ∈ {1, 2, . . . , m}. Chứng minh. 1. Ta gọi một tập con T của X là một tập độc lập nều Ai 6⊂ T, ∀i ∈ {1, 2, . . . , m}. 2. Xét S là tập độc lập có kích thước lớn nhất trong X, đặt |S| = k. Khi đó k ≥ 3. Vì S lớn nhất, nên với mỗi phần tử x ∈ X\S, sẽ tồn tại một 3_tập f (x) ⊆ S sao cho f (x) ∪ {x} ∈ F. (vì nếu mọi tập B chứa 3 phần tử trong S mà B ∪ {x} 6∈ F thì ta bổ sung x và S và được tập S ∪ {x} cũng là tập độc lập, mâu thuẫn với tính lớn nhất của S). Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 18 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP X X\S S f (x) b b b b x 3. Lấy x1 6= x2 (x1 , x2 thuộc X\S). Theo kết quả trên, tồn tại hai tập chứa 3 phần tử f (x1 ), f (x2 ) trong S sao cho f (x1 ) ∪ {x1 } ∈ F, f (x2 ) ∪ {x2 } ∈ F. Rõ ràng f (x1) 6= f (x2 ), vì nếu f (x1 ) ≡ f (x2 ). Khi đó hai tập A1 = f (x1 )∪{x1 }, A2 = f (x2 )∪{x2 } có |A1 ∩ A2 | = | f (x1 )| = 3 mâu thuẫn giả thiết. 4. Từ trên ta thấy f là một đơn ánh từ X\S vào các tập con chứa 3 phần tử của S. Do đó   k . |X\S| ≤ |S| ⇔ n − k ≤ 3 Từ đây suy ra   √ k + 6k = k3 − 3k2 + 8k ≤ k3 − 3 ⇒ k ≥ 3 6n + 3. 6n ≤ 6 3 Bài toán được chứng minh hoàn toàn. Ví dụ 2.3.3 (India Postal Coaching 2014 Set 5 Problem 4). Tập M được viết dưới dạng M = A1 ∪ A2 ∪ . . . ∪ An và Ai ∩ A j = 0/ với mọi 1 ≤ i < j ≤ n, thì các tập A1 , A2 , . . . , An được gọi là một n_phân hoạch của M. Giả sử A1 , A2, . . . , An và B1 , B2 , . . . , Bn là hai n_phân hoạch của M thỏa mãn |Ai ∪ B j | ≥ n, ∀1 ≤ i, j ≤ n. Chứng minh |M| ≥ n2 . 2 Chứng minh. Đặt k = min{|Ai |, |B j |, 1 ≤ i, j ≤ n}. Không mất tính tổng quát, giả sử |A1 | = k. 1. Do B1 , B2 , . . . , Bn là các tập con phân biệt. Và |A1 | = k, nên có nhiều nhất k tập B j trong {B1 , B2, . . . , Bn } mà A1 ∩ B j 6= 0. / Khi đó tồn tại ít nhất n − k tập B j trong {B1 , B2 , . . . , Bn } mà A1 ∩ B j = 0. / 2. Giả sử trong các tập B1 , B2 , . . . , Bn có chính xác m tập B j mà A1 ∩ B j 6= 0, / khi đó m ≤ k. Không mất tính tổng quát, gọi m tập đó là B1 , B2 , . . . , Bm . Khi đó n − m tập Bm+1, Bm+2 , . . . , Bn còn lại có A1 ∩ B j = 0, / ∀ j = m + 1, m + 2, . . . , n. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 19 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP 3. Vì B j ∩ A1 = 0, / ∀ j = m + 1, m + 2, . . ., n, lại theo giả thiết |B j ∪ A1| ≥ n, ∀ j = m + 1, m + 2, . . ., n. Chứng tỏ |B j | ≥ n − |A1 | = n − k, ∀ j = m + 1, . . . , n. 4. Theo định nghĩa của k thì |B j | ≥ |A1| = k, ∀ j = 1, 2, . . . , m. Từ đó ta có |M| = |B1 ∪ B2 ∪ . . . ∪ Bn | = |B1 | + · · · + |Bm | + |Bm+1| + · · · + |Bn | | {z } | {z } m tập n−m tập ≥ m × k + (n − m) × (n − k) = n(n − k) − m(n − 2k). • Nếu n ≥ 2k, thì n − 2k ≥ 0. Do m ≤ k nên n 2 n2 n2 −k ≥ . |M| ≥ n(n − k) − k(n − 2k) = + 2 2 2 2 • Nếu n < 2k, khi đó |M| = |B1 ∪ B2 ∪ . . . ∪ Bn | = |B1 | + · · · + |Bn | ≥ n × k > n2 . 2 Bài toán được giải quyết hoàn toàn. Ví dụ 2.3.4. Cho Ai là các tập hợp hữu hạn, với i = 1, 2, . . . , n. Chứng minh rằng nếu |Ai ∩ A j | < 1, 1≤i< j≤n |Ai |.|A j | ∑ thì tồn tại ai ∈ Ai (i = 1, 2, . . . , n) để ai 6= a j , ∀1 ≤ i < j ≤ n. Chứng minh. Đặt S = {1, 2, . . . , n} và T = A1 ∪ A2 ∪ . . . ∪ An . Xét ánh xạ f : S → T sao cho: với mỗi i ∈ S thì f (i) ∈ Ai (i = 1, 2, . . . , n). Gọi M là tập hợp tất cả các ánh xạ như vậy. Khi đó |M| = |A1 |.|A2 | . . . |An |. Ta chứng minh có ít nhất một đơn ánh trong M. Nếu f ∈ M mà không là đơn ánh, khi đó tồn tại i, j ∈ S, i 6= j sao cho f (i) = f ( j). Với ánh xạ f như vậy, thì f (i) = f ( j) nhận nhiều nhất là |Ai ∩ A j | giá trị khác nhau, và f (k) (k 6= i, j) nhận nhiều nhất là |Ak | giá trị khác nhau. Do đó với i, j ∈ S(i 6= j), số ánh xạ f mà f (i) = f ( j) nhiều nhất là n |Ai ∩ A j | · ∏ k=1,k6=i, j |Ak | = |Ai ∩ A j | .|M|. |Ai |.|A j | Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 20 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Từ đó suy ra số ánh xạ trong M mà không phải là đơn ánh nhiều nhất là |Ai ∩ A j | .M < |M|. 1≤i< j≤n |Ai |.|A j | ∑ Từ đó suy ra tồn tại ít nhất một đơn ánh f0 ∈ M. Đặt f0 (i) = ai (i = 1, 2, . . . , n). Khi đó ai ∈ Ai (i = 1, 2, . . . , n) và do f0 đơn ánh nên i, j ∈ S(i 6= j) thì ai = f0 (i) 6= f0 ( j) = a j . Ví dụ 2.3.5 (Iran 1999). Cho n là số nguyên dương và tập hợp X = {1, 2, . . . , n}. Các tập A1 , A2 , . . . , Ak là các tập con của X sao cho với mọi 1 ≤ i1 , i2 , i3 , i4 ≤ n ta có |Ai1 ∪ Ai2 ∪ Ai3 ∪ Ai4 | ≤ n − 2. Chứng minh rằng k ≤ 2n−2 . Chứng minh. Một tập con T ⊂ X được gọi là 2−phủ nếu T ⊆ Ai ∪ A j với i, j thuộc {1, 2, . . . , k} (i, j không nhất thiết phân biệt). Trong số tất cả các tập con của X không bị 2−phủ, ta chọn ra tập có số lượng phần tử nhỏ nhất. Gọi đó là tập A. 1. Xét họ tập hợp S1 = {A ∩ A1 , A ∩ A2 , . . . , A ∩ Ak } (ở đây A ∩ Ai có thể trùng A ∩ A j , nếu xảy ra điều này ta bỏ khỏi tập S1 những tập trùng nhau). Vì A không phải 2−phủ nên nếu X ∈ S1 thì A\X 6∈ S1 (thật vậy, giả sử cả X và A\X ∈ S1 , khi đó X = A ∩ Ar , A\X = A ∩ As với r, s thuộc {1, 2, . . . , k}. Nhưng khi đó thì A = X ∪ (A\X) = (A ∩ Ar ) ∪ (A ∩ As ) = A ∩ (Ar ∪ As ) ⇒ A ⊆ Ar ∪ As , mâu thuẫn với A không là 2−phủ.) Như vậy có không quá một nửa số tập con của A nằm trong S1 . Do đó |S1 | ≤ 2|A|−1 . 2. Bây giờ lấy B = X\A (dĩ nhiên B sẽ là 2−phủ, vì |B| > |A|), lại xét tiếp tập hợp S2 = {B ∩ A1 , B ∩ A2 , . . . , B ∩ Ak }. Khi đó nếu X ∈ S2 thì B\X 6∈ S2 . Thật vậy, giả sử cả hai tập X và B\X đều nằm trong S2 . Khi đó X = B ∩ Ap B\X = B ∩ Aq thì B ⊆ A p ∪ Aq . Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 21 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Theo tính nhỏ nhất của |A|, suy ra bất kỳ tập nào có < |A| phần tử sẽ là 2−phủ. Do đó với m ∈ A thì A\{m} = Ac ∪ Ad với c, d ∈ {1, 2, . . . , k}. Khi đó |Ac ∪ Ad ∪ A p ∪ Aq | ≥ |B ∪ (A\{m})| = |X\{m}| = n − 1, mâu thuẫn với giả thiết. Từ đây, tương tự lập luận trên, cũng suy ra |S2 | ≤ 2|B|−1 = 2n−|A|−1 . 3. Mặt khác, mỗi tập Ai xác định duy nhất bởi (B ∩ Ai ) ∪ (A ∩ Ai ). Do đó k ≤ |S1 |.|S2 | ≤ 2|A|−1 .2n−|A|−1 = 2n−2 . 2.4. ĐẾM SỐ TẬP HỢP CHỨA PHẦN TỬ - ĐẾM HAI CÁCH Ví dụ 2.4.1 (PUTNAM 1980). Cho A1 , A2 , . . . , A1066 là các tập con của tập hữu hạn X sao cho |Ai | > 1 |X|, với mọi 1 ≤ i ≤ 1066. Chứng minh rằng tồn tại 10 phần tử x1 , x2 , . . . , x10 của X sao cho mọi tập 2 A j ( j ∈ 1, 1066) đều chứa ít nhất một phần tử trong mười phần tử này. Chứng minh. Bài toán chỉ xét khi |X| ≥ 10. Đặt X = {x1 , x2 , . . . , xm }, với m = |X|. 1. Với mỗi t (t ∈ {1, 2, . . . , m}), đặt nt = |{ j ∈ {1, 2, . . . , 1066}|xt ∈ A j }| tức nt đếm số tập hợp A j chứa phần tử xt . Khi đó • n1 đếm số tập hợp A j chứa phần tử x1 ; • n2 đếm số tập hợp A j chứa phần tử x2 ; • .........; • nm đếm số tập hợp A j chứa phần tử xm . Do đó m = 533m. 2 Từ đây suy ra có một số ni , không mất tính tổng quát giả sử là n1 , mà n1 > 533. Tức là ta có hơn một nửa tập hợp trong số các tập A1 , A2 , . . . , A1066 chứa phần tử x1 . n1 + n2 + · · · + nm = |A1 | + |A2| + · · · + |A1066| > 1066 · 2. Gọi B1 , B2 , . . . , Bs là các tập hợp trong số các tập Ai mà không chứa phần tử x1 . Ta có s = 1066 − n1 ≤ 532 . Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 22 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Đặt Y = X\{x1 } = {x2 , . . . , xm }. Ngoài ra 1 1 1 |Bi | = |Ai | > m > (m − 1) = |Y |. 2 2 2 Với mỗi t (t ∈ {2, . . . , 1066}), đặt kt = |{ j ∈ {1, 2, . . . , s}|xt ∈ B j }| tức kt đếm số tập hợp B j chứa phần tử xt . Khi đó k2 + k3 + · · · + km = |B1 | + |B2 | + · · · + |Bs | > s · m−1 s = .(m − 1). 2 2 Vế trái là tổng của m − 1 số, do đó phải tồn tại một ki , không mất tính tổng quát giả sử k2 sao cho s k2 > . Nghĩa là có hơn một nửa tập hợp trong số B1 , B2 , . . . , Bs chứa phần tử x2 . 2 3. Đến đây lại đặt C1 ,C2 , . . . ,Cr là các tập hợp trong số các tập B j mà không chứa phần tử x2 . Ta có s s 532 r = s − k2 < s − = ≤ = 265 . 2 2 2 r Tiếp tục quá trình trên, ta lại chỉ ra được > (hơn một nửa trong số các tập C1 , . . . ,Cr ) chứa 2 r phần tử x3 . Ta lại chỉ ra được một dãy tập hợp D1 , D2 , . . . , Du với u < = 132 không chứa phần 2 tử x4 . 4. Cứ tiếp tục quá trình này ở lần thứ 5 đến lần thứ 10, mỗi dãy sẽ không nhiều hơn 65, 32, 15, 7, 3, và 1. Do đó ta nhận được các phần tử x1 , x2 , . . . , x10 thỏa mãn yêu cầu bài toán. Ví dụ 2.4.2 (China 1996, Romania 1994). Cho 11 tập hợp Mi , i = 1, 2, . . . , 11 thỏa mãn ( |Mi | = 5, ∀i = 1, 2, . . . , 11 (I) Mi ∩ M j 6= 0, / ∀1 ≤ i < j ≤ 11. Gọi m là số nguyên dương lớn nhất sao cho tồn tại các tập Mi1 , . . . , Mim trong số 11 tập trên để m \ k=1 / Mik 6= 0. Tìm giá trị nhỏ nhất của m trên tất cả cách chọn 11 tập hợp Mi thỏa mãn (I). Chứng minh. Đặt X = i=1 Mi . S11 và m = max{nx |x ∈ X}. Khi đó Với mỗi x ∈ X, đặt nx = |{ j ∈ {1, 2, . . . , 11}|x ∈ M j }| ∑ nx = |M1 | + |M2| + · · · + |M11| = 55. x∈X Theo giả thiết thì Mi ∩ M j 6= 0/ với mọi 1 ≤ i < j ≤ 11. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 23 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP
• Có 11 2 cách chọn giao khác rỗng, mỗi cách chọn giao khác rỗng là một cách chọn một cặp tập hợp Mi , M j trong số 11 tập M1 , M2 , . . . , M11 ;
• Mặt khác, mỗi phần tử x xuất hiện trong n2x giao khác rỗng của các tập Mi , M j . Do đó     nx 11 ∑ 2 ≥ 2 = 55. x∈X Do đó nx (nx − 1) ≥ 55. 2 x∈X ∑ Vì nx ≤ m, ∀x ∈ X, do đó 55 ≤ nx (nx − 1) m − 1 m−1 m−1 nx = ≤ .55 ⇒ ≥ 1 ⇒ m ≥ 3. ∑ 2 2 x∈X 2 2 x∈X ∑ Nếu m = 3, khi đó dấu bằng phải xảy ra trong tất cả các bất đẳng thức trên, nên nx = m = 3, ∀x ∈ X. Nhưng ∑x∈X nx = 55 không chia hết cho 3, nên nx không thể bằng 3 với mọi giá trị của x ∈ X. Từ đây suy ra m ≥ 4. Tiếp theo ta chứng minh m = 4 thỏa mãn. Xét a e 1 5 b f 2 6 b g 3 7 d h 4 8 Khi đó 11 tập Mi được lấy như sau: • 4 tập dòng M1 = {a, b, c, d, D}, M2 = {e, f , g, D}, M3 = {1, 2, 3, 4, D}, M4 = {5, 6, 7, 8, D}. • 4 tập cột M5 = {a, e, 1, 5,C}, M6 = {b, f , 2, 6,C}, M7 = {c, g, 3, 7,C}, M8 = {d, h, 4, 8,C}. • 3 tập đường chéo M9 = {a, f , 3, 8, D}, M10 = {b, g, 4, 5, D}, M11 = {c, h, 1, 6, D}. (Mỗi tập trên đều lấy trên mỗi dòng, mỗi cột đúng một phần tử) Ví dụ 2.4.3 (USAMO 2011). Cho A1 , A2 , . . . , A11 là các hợp sao cho ( |Ai | = 45, ∀1 ≤ i ≤ 11 |Ai ∩ A j | = 9, ∀1 ≤ i < j ≤ 11. Chứng minh rằng |A1 ∪ A2 ∪ . . . ∪ A11| ≥ 165 và cho một ví dụ với trường hợp dấu bằng xảy ra. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 24 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Chứng minh. Đặt X = A1 ∪ A2 ∪ . . . ∪ A11 , với mỗi x ∈ X, đặt nx = |{ j ∈ {1, 2, . . . , 11}|x ∈ A j }|. Khi đó ∑ nx = |A1| + |A2| + · · · + |A11| = 11 × 45 = 495. x∈X • Có
cách chọn hai tập giao khác rỗng Ai , A j trong số 11 tập A1 , A2 , . . . , A11 .
• Mặt khác, mỗi phần tử x xuất hiện trong n2x giao khác rỗng của các tập Ai , A j . 11 2 Theo giả thiết thì |Ai ∩ A j | = 9 với mọi 1 ≤ i < j ≤ 11 nên mỗi tập giao của hai tập Ai , A j thì mỗi phần tử được đếm lặp 9 lần. Do đó     nx 11 ∑ 2 = 9 × 2 = 495. x∈X Từ đây suy ra   nx ∑ nx = ∑ 2 ⇒ nx = 3, ∀x ∈ X. x∈X x∈X Mặt khác   nx ∑ nx = ∑ 2 = 495 ⇒ ∑ n2x = 3 × 495 x∈X x∈X x∈X Đặt n = |X|, theo bất đẳng thức Cauchy - Schwarz thì ∑ 1.nx x∈X !2 ≤ ∑1 x∈X ! ∑ n2x x∈X ! ⇒ 4952 ≤ n × 3 × 495 ⇒ n ≥ 165. Để kết thúc bài toán, ta chỉ ra một thuật xây dựng. Coi 11 tập hợp là 11 mặt phẳng trong R3 , trong đó không có hai mặt phẳng nào song song với nhau. Khi đó ba mặt phẳng tùy ý cắt nhau tại một điểm. Tổng số giao điểm đạt được là   11 = 165 3 là các điểm trong tập X. Ví dụ 2.4.4 (USA TST 2005). Cho n là số nguyên dương lớn hơn 1. Với mỗi số nguyên dương m, đặt Xm = {1, 2, . . . , mn}. Giả sử tồn tại một họ F = {A1 , A2 , . . . , A2n} gồm 2n tập con của Xm sao cho 1. |Ai | = m, ∀i = 1, 2, . . . , 2n; 2. |Ai ∩ A j | ≤ 1, ∀1 ≤ i < j ≤ 2n; 3. Mỗi phần tử của Xm đều nằm trong đúng hai tập hợp thuộc F . Tìm giá trị lớn nhất của m theo n. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 25 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Chứng minh. Với mỗi i ∈ Xmn , đặt ni = |{ j ∈ {1, 2, . . . , 2n}|i ∈ A j }|. Khi đó, theo giả thiết thứ 3 thì ni = 2, ∀i = 1, 2, . . . , mn. Mặt khác, sử dụng giả thiết thứ 2 thì   mn   ni 2n ∑ 2 = ∑ |Ai ∩ A j | ≤ ∑ 1 = n . 1≤i< j≤mn i=1 1≤i< j≤mn Từ đây suy ra   2n ⇒ m ≤ 2n − 1. mn ≤ 2 Mặt khác, ta lấy 2n đường thẳng trong R2 , trong đó không có hai đường thẳng nào song song. Tổng số giao điểm của các cặp đường thẳng này là   2n = n(2n − 1) = n.m 2 là các phần tử của Xmn . Khi đó mỗi tập Ai chứa 2n − 1 giao điểm trên đường thẳng i. Nhận thấy các tập Ai thỏa mãn điều kiện bài toán. Vậy giá trị lớn nhất của n là 2m − 1. Ví dụ 2.4.5. Tìm số nguyên dương n lớn nhất sao cho tồn tại n tập hợp A1 , A2, . . . , An thỏa mãn   |Ai | = 4, ∀i = 1, 2, . . . , n |Ai ∩ A j | = 1, ∀1 ≤ i < j ≤ n   |A1 ∪ A2 ∪ . . . ∪ An | = n. Chứng minh. 1. Đặt A1 ∪ A2 ∪ . . . ∪ An = {1, 2, . . . , n}. Với mỗi i ∈ {1, 2, . . . , n}, đặt Khi đó ta có ni = | j ∈ {1, 2, . . . , n}|i ∈ A j |. n ∑ ni = |A1| + · · · + |An| = 4n. (∗) i=1 Dẫn đến với mỗi i, thì trung bình nó xuất hiện trong 4 tập hợp A j . 2. Giả sử tồn tại một phần tử, không mất tính tổng quát, giả sử là 1 nằm trong nhiều hơn 4 tập hợp. Không mất tính tổng quát, giả sử là A1 , A2 , . . . , A5 . • Vì |Ai ∩ A j | = 1, ∀1 ≤ i < j ≤ 5 và ta luôn có Ai ∩ A j = {1}, ∀1 ≤ i < j ≤ 5, nên 3 × 5 = 15 phần tử còn lại của các tập A1 , A2 , A3 , A4 , A5 phải khác nhau. • Ngoài ra 1 không thể nằm trong tất cả các tập hợp A1 , . . . , An , vì nếu không áp dụng lập luận trên thì 3 × n = 3n phần tử còn lại trong các tập A1 , . . . , An phải phân biệt. Nhưng khi đó thì mâu thuẫn. |A1 ∪ A2 ∪ . . . ∪ An | = 3n + 1 > n, Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 26 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP • Do đó tồn tại một tập hợp trong A6 , . . . , An không chứa phần tử 1. Giả sử A6 = capAi (i = 1, 2, . . . , 5) là các tập phân biệt. Nếu ngược lại, giả sử A6 ∩ A1 = A6 ∩ A2 = {b} thì b 6= 1 do 1 6∈ A6 . Nhưng khi đó thì b ∈ A1 , b ∈ A2 , mâu thuẫn với ý đầu tiên. Từ đây dẫn đến tập A6 phải có ít nhất 5 phần tử, mâu thuẫn với giả thiết. Vậy mỗi phần tử nằm trong không quá 4 tập hợp. Ngoài ra nếu có một phần tử nào đó nằm trong ít hơn 4 phần tử, theo (*) phải có một phần tử nằm trong ≤ 4 tập hợp, dẫn đến mâu thuẫn. Vậy một phần tử xuất hiện trong đúng 4 tập hợp A j . 3. Giả sử 1 nằm trong A1 , A2 , A3 , A4 . Khi đó, giả sử A1 = {1, 2, 3, 4}, A2 = {1, 5, 6, 7}, A3 = {1, 8, 9, 10}, A4 = {1, 11, 12, 13}. Khi đó n ≥ 13. 4. Nếu n ≥ 14 thì phần tử 14 nằm trong một tập hợp, giả sử A5 . Khi đó 3 phần tử còn lại của A5 sẽ nằm trong các tập A1 , A2 , A3 . Dẫn đến A5 và A4 không có phần tử chung, mâu thuẫn. 5. Vậy n lớn nhất là 13, và dưới đây là 13 tập hợp thỏa mãn A1 = {1, 2, 3, 4}, A2 = {1, 5, 6, 7}, A5 = {2, 5, 8, 11}, A6 = {2, 6, 9, 12}, A7 = {2, 7, 10, 13}, A8 = {3, 5, 10, 12}, A10 = {3, 7, 9, 11}, A11 = {4, 5, 9, 13}, A12 = {4, 6, 10, 11}, A9 = {3, 6, 8, 13}, A3 = {1, 8, 9, 10}, A4 = {1, 11, 12, 13}, A13 = {4, 7, 8, 12}. Ví dụ 2.4.6 (China 1999). Cho n nguyên dương và X là một tập hợp với |X| = n. Gọi A1 , A2 , . . . , An là các tập con của X sao cho |Ai | ≥ 2, ∀i = 1, 2, . . . , n. Giả sử rằng với mỗi tập con A′ ⊂ X, |A′ | = 2 thì tồn tại duy nhất một chỉ số i sao cho A′ ⊆ Ai . Chứng minh rằng Ai ∩ A j 6= 0, / ∀1 ≤ i < j ≤ n. Chứng minh. 1. Vì mỗi tập con, giả sử {a, b} của X thì tồn tại duy nhất một chỉ số i sao cho {a, b} ⊆ Ai và mỗi tập con chứa hai phần tử của Ai thì không thể là tập con của một tập A j nào khác. Do đó    n  n |Ai | ∑ 2 = 2 . (1) i=1 Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 27 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP 2. Đặt X = {x1 , x2 , . . . , xn }. Với mỗi i ∈ {1, 2, . . . , n}X, ký hiệu ni = |{ j ∈ {1, 2, . . . , n}|xi ∈ A j }|. Khi đó n n i=1 i=1 ∑ ni = ∑ |Ai|. (2) Mặt khác • Mỗi phần tử xi ∈ X sẽ nằm trong ni tập hợp. Do đó mỗi phần tử xi sẽ xuất hiện trong tập giao. ni 2
• Xét một tập giao, giả sử {xi , xt } = Ar ∩ As . Khi đó cả xi và xt đều được tính trong tập giao này. Do đó n   ni ∑ 2 = ∑ |Ai ∩ A j | . (3) 1≤i< j≤n i=1 3. Theo giả thiết bài toán, thì |Ai ∩ A j | ≤ 1. Và kết luận bài toán cần chứng minh |Ai ∩ A j | = 1. Khi đó (3) trở thành   n   ni n ∑ 2 = 2 . i=1 Từ đây theo (1), (2) và đẳng thức trên ta được  n   n  ni |Ai | ∑ 2 =∑ 2 , i=1 i=1 n n i=1 i=1 ∑ ni = ∑ |Ai | dẫn đến kết luận bài toán đưa về chứng minh n n i=1 i=1 ∑ n2i = ∑ |Ai |2. (∗) 4. Với mỗi phần tử xi ∈ X, xét tập A j mà xi 6∈ A j . Giả sử A j = {y1 , y2, . . . , ys }. Khi đó mỗi tập hợp chứa 2 phần tử sau đây {xi , y1 }, {xi , y2 }, . . . , {xi , ys } là tập con của các tập, chẳng hạn A1 , A2 , . . . , As (lưu ý không thể xảy ra {xi , y1 }, {xi , y2 } cùng thuộc vào một tập, chẳng hạn A1 . Vì khi đó {y1 , y2} cũng là tập con của A1 , mâu thuẫn với giả thiết. Điều này đúng cho tất cả các tập còn lại). Từ đây suy ra xi thuộc vào s = |A j | tập hợp A1 , A2, . . . , As (dĩ nhiên x còn thuộc vào một số tập khác nữa). Điều này chứng tỏ nếu xi 6∈ A j thì ni ≥ |A j | ⇒ |A j | ni . ≥ n − ni n − |A j | 5. Số tập hợp A j không chứa xi là n − ni . Do đó ∑ j|xi 6∈A j ni ni = (n − ni ) · = ni . n − ni n − ni Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 28 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP Do đó n n ∑ ni = ∑ ∑ ni n − ni ≥∑ ∑ |A j | n − |A j | ∑ ∑ |A j | n − |A j | i=1 i=1 j|xi 6∈A j n i=1 j|xi 6∈A j n = j=1 i|xi 6∈A j n = ∑ |A j |. j=1 Nhưng theo (2) đẳng thức phải xảy ra trong ước lượng trên. Do đó ni = |A j |. Từ đây suy ra n n ∑ (n − ni)ni = ∑ ∑ i=1 di i=1 j|xi 6∈A j n =∑ ∑ |A j | ∑ ∑ |A j | i=1 j|xi 6∈A j n = j=1 i|xi 6∈A j n = ∑ (n − |A j )|A j | j=1 từ đó (*) được chứng minh. Bài toán kết thúc. 2.5. XÂY DỰNG - QUY NẠP - TRUY HỒI Ví dụ 2.5.1. Cho n nguyên dương và tập hợp M = {1, 2, . . . , 20}. Gọi A1 , A2 , . . . , An là các tập con phân biệt khác rỗng của M sao cho |Ai ∩ A j | ≤ 2, ∀1 ≤ i < j ≤ n. Tìm giá trị lớn nhất của n. Chứng minh. 1. Giả sử A1 , A2 , . . . , An là các tập con của M thỏa mãn điều kiện bài toán. Nếu một trong các tập A1 , A2 , . . . , An có ít nhất 4 phần tử, không mất tính tổng quát, giả sử |A1 | ≥ 4. Gọi a là một phần tử trong A1 . • Khi đó A1 \{a} là tập có ít nhất ba phần tử. Do |A1 ∩ Ai | ≤ 2, ∀i = 2, 3, . . . , n nên tập A1 \{a} phải phân biệt với tất cả các tập A2 , . . . , An (vì nếu A1 \{a} ≡ Ai nào đó, thì A1 \{a} ∩ Ai = A1 \{a} có ít nhất ba phần tử. Khi đó A1 ∩ Ai cũng có ít nhất ba phần tử, vô lý.) Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 29 CỰC TRỊ TẬP HỢP • Ngoài ra 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP | (A1 \{a}) ∩ A j | ≤ |A1 ∩ A j | ≤ 2, ∀ j = 2, 3, . . . , n. 2. Từ các kết quả trên, nếu thay A1 bởi A1 \{a} thì hệ tập hợp A1 \{a}, A2, A3 , . . . , An vẫn thỏa mãn bài toán. Hệ mới này có cùng số tập hợp với hệ ban đầu, nhưng số phần tử trong mỗi tập hợp ≤ 1 so với số phần tử trong mỗi tập hợp của hệ ban đầu. Cứ tiếp tục quá trình này, ta thu được dãy tập hợp A∗1 , . . . , A∗n thỏa mãn bài toán và |A∗i | ≤ 3, ∀i = 1, 2, . . . , n Tức là các tập hợp này, mỗi tập hợp chỉ có tối đa ba phần tử. Do đó       20 20 20 = 1350. + + n≤ 3 2 1 3. Tiếp theo, tổng số các tập con chứa 1 phần tử, chứa 2 phần tử, chứa 3 phần tử của M là       20 20 20 + + = 1350 1 2 3 và tất cả các tập này thỏa mãn điều kiện bài toán (rõ ràng hai tập phân biệt bất kỳ trong các tập này có giao không vượt quá 2 phần tử). Do đó n = 1350 đạt được. Từ đó suy ra giá trị lớn nhất của n là n = 1350. Ví dụ 2.5.2 (Indian 2014). Cho số tự nhiên n và X = {1, 2, . . . , n}. Với hai tập con A và B của X, ký hiệu A∆B = {i ∈ X|i ∈ (A\B) ∪ (B\A)}. Gọi F là một họ các tập con của X sao cho với mọi A, B ∈ F thì |A∆B| ≥ 2. Chứng minh rằng |F | ≤ 2n−1 và tìm tất cả các họ F có 2n−1 phần tử. Chứng minh. 1. Với mỗi tập con A ⊂ {1, 2, . . . , n − 1}, thì trong cặp tập hợp (A, A ∪ {n}), tối đa một tập hợp thuộc vào F . Thật vậy vì A\(A ∪ {n}) = 0, / (A ∪ {n})\A = {n} ⇒ A∆(A ∪ {n}) = {n}. Mặt khác, ta có tối đa 2n−1 cặp tập hợp (A, A ∪ {n}). Do đó tập F có tối đa 2n−1 phần tử. 2. Tiếp theo ta chứng minh bằng quy nạp theo n là nếu |F | = 2n−1 thì F hoặc chứa tất cả các tập con chứa số lẻ phần tử hoặc F chứa tất cả các tập hợp chứa số lẻ phần tử. • Kết quả hiển nhiên đúng với n = 1. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 30 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP • Giả sử kết quả đúng đến n = m − 1, với m nguyên dương lớn hơn 1. Xét trường hợp với n = m. Đặt F1 = {A ∈ F |m ∈ A}, F2 = {A ∈ F |m 6∈ A}. Theo giả thiết quy nạp, tập F∈ có nhiều nhất 2m−2 phần tử. • Với mỗi tập hợp A ∈ F1, ta xét tập hợp mới A\{m}. Khi đó F3 = {A\{m}|A ∈ F1 } Khi đó tập F3 cũng thỏa mãn yêu cầu bài toán và theo giả thiết quy nạp thì lại có |F3| ≤ 2m−2 . Nhưng |F2 | = |F3 | ≤ 2m−2 ⇒ |F | = |F1 | + |F2| ≤ 2m−2 + 2m−2 = 2m−1 . Do đó nếu |F | = 2m−1 thì |F1| = |F2| = 2m−2 . Nhưng khi đó lại theo giả thiết quy nạp, họ F∈ chứa tất cả các tập con của \1, 2, . . . , m − 1 với, giả sử, số chẵn phần tử. Khi đó F∞ chứa tất cả các tập con của {1, 2, . . . , m}, chứa m, dạng A ∪ {m}. Tuy nhiên A không thể thuộc vào F2 , vì nếu không thì cả A, A ∪ {m} đều thuộc vào F vô lý. Khi đó A phải có số lẻ phần tử, A ⊂ {1, 2, . . . , m − 1}, và |F1| = 2m−2 nên A phải chạy trên tất cả các tập có số lẻ phần tử. Do đó F1 cũng chứa các tập có số chẵn phần tử. Vậy F chứa tất cả các tập hợp có số chẵn phần tử. Tương tự khi F2 chứa tất cả các tập có số lẻ phần tử. Bài toán được chứng minh. Ví dụ 2.5.3 (Bankal 2012). Cho n là số nguyên dương. Đặt tập hợp Pn = {2n , 2n−1 .3, 2n−2.32 , . . . , 3n }. Với mỗi tập con X của Pn , đặt SX là tổng tất cả các phần tử trong X, ở đây S0/ = 0. Cho y là một số thực thỏa mãn điều kiện 0 ≤ y ≤ 3n+1 − 2n+1 . Chứng minh rằng tồn tại một tập con Y của Pn thỏa mãn điều kiện 0 ≤ y − SY < 2n . Giải. Ta có SPn = 3n + 3n−1 .2 + · · · + 32 .2n−2 + 3.2n−1 + 2n = (3 − 2)(3n + 3n−1 .2 + · · · + 32 .2n−2 + 3.2n−1 + 2n ) = 3n+1 − 2n+1 Bằng cách chia cách phần tử của Pn cho 2n ta đưa bài toán về dạng tương đương như sau: 3 Cho n là số nguyên dương, a = , và Qn = {1, a, a2 , . . . , an }. Chứng tỏ rằng với mỗi giá trị của x thỏa 2 mãn 0 ≤ x ≤ 1 + a + a2 + · · · + an , luôn tồn tại một tập con X của Qn sao cho 0 ≤ x − SX < 1 . 3 5 Ta chứng minh bằng quy nạp theo n. Khi n = 1 thì S0/ = 0, S{1} = 1, S{a} = , S{1,a} = . Từ đây kiểm 2 2 5 chứng thấy ngay là nếu x là một số thực thỏa 0 ≤ x ≤ thì luôn có một tập con X của Q1 thỏa yêu cầu. 2 Giả sử kết quả bài toán đúng đến số nguyên dương n. Xét x là một số thực với 0 ≤ x ≤ 1 + a + a2 + · · · + an + an+1 . + Nếu 0 ≤ x ≤ 1 + a + a2 + · · · + an thì theo giả thiết quy nạp tồn tại tập con X ⊂ Qn ⊂ Qm+1 thỏa Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 31 CỰC TRỊ TẬP HỢP 0 ≤ x − SX < 1. + Xét với x > nên 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP 1 + a + a2 + · · · + an an+1 − 1 , khi đó vì = a−1
an+1 − 1 an+1 − 1 1 = 3 = 2 an+1 − 1 = an+1 + (an+1 − 2) > an+1 + a2 − 2 = an+1 + > an+1 a−1 4 2 −1 0 < (x − an+1 ) ≤ 1 + a + a2 + · · · + an . Theo giả thiết quy nạp, tồn tại tập con X ⊂ Qn thỏa mãn 0 ≤ (x − an+1 ) − SX < 1 =⇒ 0 ≤ x − SX ′ < 1 với X′ = X Bài toán được chứng minh. [ {an+1 } ⊂ Qn+1 . Ví dụ 2.5.4 (Romania, grade 9, final round). Cho p, q là hai số nguyên dương, p ≥ 2, q ≥ 2. Một tập hữu hạn X gọi là có tính chất (S) nếu: với bất kỳ cách chọn p tập con Bi ⊂ X, i = 1, 2, . . . , p, không nhất thiết phân biệt, mỗi tập có q phần tử, thì luôn tồn tại tập con Y ⊂ X có p phần tử, sao cho |Y ∩ Bi | ≤ 2, ∀i = 1, 2, . . . , p. Chứng minh rằng 1. Mọi tập X có pq − q phần tử đều không có tính chất (S). 2. Mọi tập hợp X có pq − q + 1 phần tử đều có tính chất (S). Chứng minh. 1. Nếu X có pq − q = (p − 1)q phần tử, khi đó ta chọn p − 1 tập, mỗi tập có q phần tử (là phân hoạch của X) như sau B1 = {1, 2, . . . , q}, B2 = {q + 1, q + 2, . . . , 2q}, ..., B p−1 = {(p − 2)q + 1, . . . , (p − 1)q} và tập B p là một tập tùy ý có q phần tử. Khi đó, theo nguyên lý Dirichlet, thì với mọi tập Y có p phần tử trong X, sẽ tồn tại ít nhất một tập Bi (i ∈ {1, 2, . . . , p − 1}) sao cho giao của nó với Y có ≥ 2 phần tử. Vậy tập X không có tính chất (S). 2. Bây giờ với mỗi i cho trước, nhận xét tập [ Bi j6=i có ≤ (p − 1)q phần tử. Trong khi đó tập X có pq − q + 1 = (p − 1)q + 1 phần tử. Do đó ta tìm được ít nhất một phần tử của tập X mà nó không nằm trong mọi tập B j , với mọi j 6= i. • Với i = 1, sử dụng lập luận trên, ta tìm được phần tử x1 mà x1 6∈ B j , ∀ j = 2, . . . , p. Nếu x1 ∈ B1 , ta tiếp tục qua bước 2, nếu x1 6∈ B1 , ta xây dựng tập B1 mới bằng cách bỏ ra khỏi B1 một phần tử y1 , và thêm vào tập B1 phần tử x1 . Dĩ nhiên phần tử y1 vẫn là phần tử trong X. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 32 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP • Tiếp tục với i = 2, lưu ý tập B1 sử dụng bây giờ là tập B1 "mới". Lại sử dụng lập luận trên, ta tìm được phần tử x2 mà x2 không nằm trong bất cứ tập B1 , B3 , B4 , . . . , Bn . Khi đó x2 6= x1 (vì x1 ∈ B1 , x2 6∈ B1 ). Nếu x2 ∈ B2 ta tiếp tục quy trình, nếu x2 6∈ B2 , ta xây dựng tập B2 mới bằng cách bỏ ra khỏi B2 một phần tử y2 , và thêm vào tập B2 phần tử x2 . 3. Cứ tiếp tục quy trình này đến bước p, ta sẽ tìm được tập Y = {x1 , x2 , . . . , x p }. Tập Y giao với mỗi tập Bi "mới" chính xác một phần tử, đó là xi . Bây giờ thay ngược trở lại xi bởi yi ta quay trở lại tập Bi "cũ". Nếu yi 6∈ Y thì Y ∩ Bi = 0, / còn nếu yi ∈ Y thì Y ∩ Bi = {yi }. Ví dụ 2.5.5 (China TST 2015). Cho X là một tập khác rỗng và A1 , A2 , . . . , An là n tập con của X sao cho 1. |Ai | ≤ 3, ∀i = 1, 2, . . . , n; 2. Bất kỳ một phần tử nào của X cũng nằm trong ít nhất 4 tập trong số A1 , A2 , . . . , An .   3n Chứng minh rằng có thể chọn tập hợp trong số các tập A1 , A2 , . . . , An mà hợp của chúng bằng X. 7 Chứng minh. Kết luận bài toán yêu cầu chọn được một số tập hợp, hợp lại bằng X, do đó ta sẽ 1. Chọn tập đầu tiên có 3 phần tử, giả sử A1 , |A1 | = 3. Sau đó, ta chọn tiếp tập A2 mà |A2 | = 3 và A2 ∩A1 = 0. / Sau khi chọn được tập A2 , ta chọn tiếp tập A3 mà |A3 | = 3 và A3 ∩A1 = 0, / A3 ∩A2 = 0, / cứ tiếp tục như vậy đến khi không thể chọn thêm được tập nào nữa vào trong hệ. Trong tất cả cách cách lựa chọn các tập hợp trong A1 , A2 , . . . , An , ta chọn ra hệ tập hợp S3 cực đại, giả sử S3 = {A1 , A2 , . . . , Ai } (i ≤ n) (tức là họ S3 chứa nhiều tập hợp nhất có thể có) mà |At | = 3, ∀t = 1, 2, . . . , i và Ar ∩ As = 0, / ∀1 ≤ r < s ≤ i (điều này có nghĩa, mỗi lần bổ sung một tập hợp vào S3 thì tập X3 có số lượng phần tử tăng lên 3). X3 b b b b b b b b b b b b b b b X\X3 b X Đặt X3 = Ar ∈S3 Ar . S Do tính tối đại của tập S3 , nên với bất kỳ tập hợp A j ( j > i) thì |A j ∩ (X\X3 )| ≤ 2 vì nếu không thì ta tiếp tục bổ sung A j vào tập S3 , mâu thuẫn với tính tối đại của S3 . Và khi đó |X3 | = 3i. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 33 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP 2. Bây giờ ta tiếp tục chọn họ S2 cực đại chứa các tập A j còn lại trong số Ai+1 , . . . , An , sao cho mỗi lần thêm một tập hợp vào họ S2 , thì số lượng phần tử trong hợp của chúng tăng lên 2. Không mất tính tổng quát, giả sử S2 = {Ai+1 , Ai+2 , . . . , A j } X3 X b b b b b b b b b b b b b b b b b X2 b b b b b b b b X\X3 Đặt X2 = [ Ar ∈S2 Ar ∩ (X\X3 ) thì theo cách xác định của S2 ta có |X2 | = 2 j và theo tính tối đại của tập S2 thì |At ∩ (X\(X2 ∪ X3 ))| ≤ 1, ∀t = j + 1, . . . , n. 3. Bây giờ ta tiếp tục chọn họ S1 chứa các tập As còn lại trong số A j+1 , . . . , An , sao cho mỗi lần thêm một tập hợp vào họ S1 , thì số lượng phần tử trong hợp của chúng tăng lên 1 và dĩ nhiên các tập hợp trong họ S1 chứa hết tất cả các phần tử của X\(X3 ∪ X2 ) = X1 . Không mất tính tổng quát, giả sử S1 = {A j+1 , Ai+2 , . . . , Ak }. 4. Khi đó |X| = |X1 | + |X2 | + |X3 | = 3i + 2 j + k, X = X1 ∪ X2 ∪ X3 và Ta cần chứng minh m ≤ 3n 7. |S3 | + |S2| + |S1 | = i + j + k = m. • Vì mỗi phần tử trong X1 nằm trong ít nhất 4 tập hợp, nhưng do |Ar ∩X1 | ≤ 1, ∀r = j +1, . . . , n nên n ≥ i + j + 4k. (1) Mỗi phần tử trong X1 ∪ X2 xuất hiện ít nhất trong 4 tập hợp, như do |Ar | ∩ (X1 ∪ X2 ) ≤ 2, ∀r = i + 1, . . . , n nên n ≥ i+ 4(2 j + k) = i + 4 j + 2k. (2) 2 Mỗi phần tử trong X xuất hiện ít nhất trong 4 tập hợp, và |Ar ∩ X| ≤ 3, ∀r = 1, 2, . . . , n, do đó 4(3i + 2 j + k) . (3) n≥ 3 Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 34 CỰC TRỊ TẬP HỢP 2 MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN CỰC TRỊ TẬP HỢP • Lấy 20 × (1) + 12 × (2) + 27 × (3) ta có 59n ≥ 140(i + j + k) = 140m ⇒ m ≤ 59n 3n < . 140 7 Bài toán được chứng minh hoàn toàn. Ví dụ 2.5.6 (Romania TST 2006). Cho n là số nguyên dương. Một tập con S ⊂ {0, 1, 2, . . . , 4n − 1} được gọi là tập rời rạc nếu với số k bất kỳ, hai điều kiện được sau thỏa mãn 1. Tập S {4k − 2, 4k − 1, 4k, 4k + 1, 4k + 2} có tối đa 2 phần tử. T 2. Tập S {4k + 1, 4k + 2, 4k + 3} có tối đa 1 phần tử. T Hỏi tập {0, 1, . . . , 4n − 1} có bao nhiêu tập con rời rạc? Chứng minh. • Ta diễn giải tập S, trong tập 5 số: gồm 4 số chia hết cho 4, chia 4 dư 1, chia 4 dư 2, chia 4 dư 3 và thêm một số chia 4 dư 2 thì tập S chứa tối đa 2 phần tử trong chúng. Trong một tập 3 số: chia 4 dư 1, dư 2, dư 3 thì tập S chứa tối đa một số. Rõ ra hai số chia cho 4 dư 2 và dư 3 không thể cùng nằm trong tập S (vì vi phạm điều kiện (ii)). • Gọi Sn là tập hợp chứa các tập con rời rạc của tập {0, 1, 2, . . . , 4n − 1}. Rõ ràng là các số có dạng 4k + 1, 4k + 2 bị ràng buộc bởi hai điều kiện. Đây chính là cơ sở cho việc xây dựng công thức truy hồi. • Gọi Xn là tập hợp chứa các tập con của Sn mà mỗi tập con của nó chứa phần tử 4n − 1 (tức là các tập con của Sn mà các tập con đó chứa phần tử chia 4 dư 3). • Gọi Yn là tập hợp chứa các tập con của Sn mà mỗi tập con của nó không chứa cả hai phần tử 4n − 1 và 4n − 2 (tức là chứa các tập con của Sn mà mỗi tập con của nó không chứa hai phần tử chia 4 dư 2 và chia 4 dư 3, nghĩa là nó sẽ chứa các phần tử chia hết cho 4 hoặc chia 4 dư 1). • Gọi Zn là tập hợp chứa các tập con của Sn mà mỗi tập con của nó chứa phần tử 4n − 2 (tức là chứa các tập con của Sn mà các tập con đó chứa phần tử chia 4 dư 2). Khi đó |Sn | = |Xn | + |Yn| + |Zn | . 1. Xét tập hợp Xn+1 được xây dựng từ các tập hợp còn lại. Xét tập hợp {1, 2, . . . , 4n − 2, 4n − 1, 4n, 4n + 1, 4n + 2, 4n + 3}. • Từ tập Xn , khi đó ta chỉ có thể thêm vào mỗi tập của Xn phần tử 4n hoặc không thêm vào, vì bản thân tập Xn+1 đã chứa phần tử 4n + 3. Vậy |Xn+1 | = 2 |Xn |. • Từ tập Yn , ta cũng chỉ có thể thêm vào mỗi tập của Yn phần tử 4n hoặc không thêm vào. Vì vậy |Xn+1 | = 2 |Yn|. • Từ tập Zn , ta cũng chỉ có thể thêm vào mỗi tập của Yn phần tử 4n hoặc không thêm vào. Vậy |Xn+1 | = 2 |Zn |. Từ đó ta có quan hệ truy hồi |Xn+1 | = 2 |Xn | + 2 |Yn| + 2 |Zn | = 2 |Sn | (1). Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 35 CỰC TRỊ TẬP HỢP 3 BÀI TẬP VẬN DỤNG 2. Xét tập hợp Yn+1 được xây dựng từ các tập hợp còn lại • Từ tập Yn, khi đó ta có thể thêm vào mỗi tập con của Yn phần tử 4n hoặc 4n + 1, thêm cả hai hoặc không thêm phần tử nào. Khi đó |Yn+1| = 4 |Yn|. • Từ tập Xn , khi đó ta có thể thêm vào mỗi tập con của Xn phần tử 4n hoặc 4n + 1 nhưng không thể thêm đồng thời hai phần tử này, hoặc không thêm vào. Khi đó |Yn+1| = 3 |Xn |. • Từ tập Zn , khi đó ta có thể thêm vào mỗi tập con của Zn phần tử 4n hoặc 4n + 1 nhưng không thể thêm đồng thời hai phần tử này, hoặc không thêm vào. Khi đó |Yn+1| = 3 |Zn |. Từ đó ta có quan hệ hồi quy |Yn+1| = 3 |Xn | + 4 |Yn| + 3 |Zn | (2). 3. Tương tự ta cũng có |Zn+1 | = 2 |Xn | + 2 |Yn | + 2 |Zn | = 2 |Sn | (3). Từ ba quan hệ (1), (2), (3) ta có |Sn+1 | = 7. |Sn |. Từ đó ta tính được |Sn+1 | = 7n . |S1 | = 8.7n . 3. BÀI TẬP VẬN DỤNG Bài tập 3.1 (Olympic KHTN lần 1). Xét tập M = {1, 2, 3, . . . , 10} và A1 , A2 , . . . , An là dãy các tập con khác rỗng, phân biệt của M sao cho Tìm giá trị lớn nhất của n. |Ai ∩ A j | ≤ 3, ∀1 ≤ i < j ≤ n. Đáp số: n = 385. Bài tập 3.2 (Đài Loan 1998). Cho n ≥ k ≥ 3 và X = {1, 2, . . . , n}. Gọi Fk là một họ các k_tập của X sao cho với mọi A, B ∈ Fk thì |A ∩ B| ≤ k − 2. Chứng minh rằng tồn tại một tập con Mk của X, |Mk | ≥ [log2 n] + 1 sao cho Mk không nhận bất cứ phần tử nào của Fk là tập con của nó. Chứng minh. 1. Nếu k ≥ log2 n thì kết quả hiển nhiên đúng. Xét trường hợp k < log2 n. Đặt m = [log2 n] + 1. 2. Một tập con M chứa k − 1 phần tử của X, thì tồn tại nhiều nhất là một phần tử A ∈ Fk sao cho M ⊂ A. Thật vậy, nếu có hai phần tử A, B trong Fk mà M ⊂ A, M ⊂ B thì |A ∩ B| ≥ |M| = k − 1, mâu thuẫn với giả thiết. Mặt khác mỗi phần tử A thuộc Fk nó sẽ chứa k tập con, mỗi tập chứa k − 1 phần tử. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 36 CỰC TRỊ TẬP HỢP 3 BÀI TẬP VẬN DỤNG A A Fk Sk−1 (Ta giải thích cho hình minh họa trên một chút. Gọi Sk−1 là tập tất cả các tập con, mỗi tập con chứa k − 1 phần tử của X. Một phần tử X ∈ Fk , thì A chứa k tập con, mỗi tập con chứa k − 1 phần tử. Khi đó tương ứng k tập con này sẽ nằm trong Sk−1 , và hợp của k tập con này trong Sk−1 chính là tập A. Vậy trong tập Sk , thì k tập con này cho ta tương ứng một phần tử A thuộc Fk . Dĩ nhiên có thể xảy ra một phần tử trong Sk−1 sẽ không là tập con của bất cứ phần tử nào trong Fk ). Từ đó ta có     1 n n 1 |Fk | ≤ = . k k−1 n−k+1 k 3. Bây giờ ta gọi Sm là họ các tập con, mỗi tập con m phần tử của tập X. Trường hợp "xấu nhất", tức là cần nhiều tập con nhất trong Sm mà mỗi tập đó đều nhận một phần tử trong Fk là tập con, là mỗi phần tử A của Fk , riêng biệt, là tập con của một tập Y trong Sm . A Y Sm Fk Đến đây ta có ngay được kết luận bài toán nếu chứng tỏ được |Sm | ≥ |Fk |. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 37 CỰC TRỊ TẬP HỢP 3 BÀI TẬP VẬN DỤNG (khi đó sẽ có một phần tử trong Sm không nhận bất cứ tập nào trong Fk là tập con, tập này có m phần tử. Dĩ nhiên ta có thể bổ sung vào tập này một số phần tử nữa nếu không bị vi phạm.) Ta có được kết luận nếu chứng tỏ được     1 n! n! n n 1 ≤ ≤ ⇔ n−k+1 k n − k + 1 k!(n − k)! m!(n − m)! m hay     1 (n − k)! 1 n−k m m! (n − k)! m! 1 . ≤ ≤ ⇔ ≤ ⇔ m−k n − k + 1 k! (n − m)! n − k + 1 k!(m − k)! (n − m)!(m − k)! n−k+1 k Nhưng kết quả trên là hiển nhiên, vì ta có được khẳng định mạnh hơn là   1 m < 1 (∗). n−k+1 k 4. Ta sử dụng kết quả   m ≤ 3.2m−3 , k ∀m ≥ k ≥ 3. Thật vậy, với m = 3, m = 4 kiểm tra dễ dàng đúng. Giả sử kết quả đúng cho mọi giá trị ≤ m. Khi đó với m + 1 thì, sử dụng tính chất nhị thức và giả thiết quy nạp, có       n n m+1 ≤ 3.2m−3 + 3.2m−3 = 3.2m−2 . + = k−1 k k Theo giả thiết quy nạp thì đúng. 5. (*) sẽ được chứng minh nếu chứng tỏ được hay 1 1 .3.2m−3 < 1 ⇔ .3.2[log2 n]−2 < 1 n−k+1 n−k+1 Vì 2[log2 n] < 2log2 n = n và (kết quả cuối cùng đúng do 3 .2[log2 n] < 1. 4(n − k + 1) 3n < 1 ⇔ 4k < n + 1 4n − 4k + 1 4k < 4. log2 n = log 2(4n) < log2 (2n+1 ) = n + 1. ) Từ đó (*) được chứng minh. Bài toán kết thúc. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 38 CỰC TRỊ TẬP HỢP 3 BÀI TẬP VẬN DỤNG Bài tập 3.3 (THTT 444 - Trần Nam Dũng). Cho 100 điểm A1 , A2 , . . . , A100 nằm trong hình vuông ABCD có cạnh bằng 1. Chứng minh rằng luôn tồn tại một tập con X của E = {1, 2, . . . , 100} gồm 50 phần tử sao cho √ −→ −→ ∑ AAi − ∑ AAi ≤ 2. i∈X i∈E\X Bài tập 3.4 (China 2006). Cho trước số nguyên dương n ≥ 2 và tập X hữu hạn. Gọi B1 , B2 , . . . , Bn là n tập con tùy ý của X, mỗi tập chứa ít nhất hai phần tử. Tìm giá trị nhỏ nhất của |X| sao cho tồn tại một tập con Y của X thỏa mãn hai điều kiện 1. |Y | = n; 2. |Y ∩ Bi | ≤ 1, ∀i = 1, 2, . . . , n. Đáp số: |X| = 2n − 1. Bài tập 3.5 (Tuyển tập Olympic 30-4 năm 2007). Cho A1 , A2 , . . . , A10 là các tập hợp thỏa mãn điều kiện 1. |Ai | = 8, ∀i = 1, 2, . . . , 10; 2. |Ai ∩ A j | = 1, ∀1 ≤ i < j ≤ 10. Chứng minh rằng |A1 ∪ A2 ∪ . . . ∪ A10| ≥ 39. Bài tập 3.6 (Dan Schwarz). Cho X là một tập hợp. Gọi n và m ≥ 1 là các số nguyên không âm sao cho |X| ≥ m(n − 1) + 1. Giả sử B1 , B2 , . . . , Bn là n tập con của X sao cho |Bi | ≤ m, ∀i ∈ {1, 2, . . . , n}. Chứng minh rằng tồn tại một tập con Y của X sao cho |Y | = n và |Y ∩ Bi | ≤ 1, ∀i = 1, 2, . . . , n. Bài tập 3.7 (China 2010). Cho số nguyên dương n ≥ 2 và A1 , A2 , . . . , A2n là các tập con phân biệt của tập {1, 2, . . . , n}. Xác định giá trị lớn nhất của 2n |Ai ∩ Ai+1 | ∑ |Ai|.|Ai+1| . i=1 Chứng minh. 1. Ta nhận thấy các tập Ai (i = 1, 2, . . . , 2n) phải khác rỗng, vì nếu có tập nào bằng rỗng, thì biểu thức không xác định. 2. Chúng ta chỉ quan tâm tới những biểu thức Ai ∩ Ai+1 6= 0/ vì nếu Ai ∩ Ai+1 = 0/ thì tử số bằng 0 và ta loại bỏ biểu thức đó ra khỏi tổng cần tính. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 39 CỰC TRỊ TẬP HỢP 3 BÀI TẬP VẬN DỤNG 3. Vói mỗi i mà Ai ∩ Ai+1 6= 0. / Đặt X = Ai ∩ Ai+1 thì |X| ≥ 1. Ngoài ra do X ⊂ Ai , X ⊂ Ai+1 và Ai , Ai+1 phân biệt nên |Ai |.|Ai+1 | ≥ |X|.(|X| + 1). Từ đó suy ra |Ai ∩ Ai+1 | |X| 1 ≤ ≤ . |Ai |.|Ai+1 | |X|(|X| + 1) 2 4. Từ đó suy ra 2n |Ai ∩ Ai+1 | 1 ∑ |Ai |.|Ai+1| ≤ 2n. 2 = n. i=1 5. Ta xây dựng một trường hợp cho dấu bằng, đó là A2i−1 = {i}, A2i = {i, i + 1}, i = 1, 2, . . . , n với chú ý A2n = {n, 1}. Bài tập 3.8 (Chọn đội tuyển KHTN 2010). Cho số nguyên dương n > 10. Tìm số nguyên dương m lớn nhất thỏa mãn điều kiện: Tồn tại m tập con A j của tập {1, 2, . . . , 2n}, mỗi tập con gồm n phần tử sao cho |Ai ∩ A j ∩ Ak | ≤ 1, ∀1 ≤ i < j < k ≤ m. Đáp số: m = 4 Bài tập 3.9 (China 2014). Với các tập hợp khác rỗng S, T , ta định nghĩa hai tập S + T = {s + t|s ∈ S,t ∈ T }, 2S = {2s|s ∈ S}. Cho n là số nguyên dương và A, B là các tập con khác rỗng của {1, 2, . . . , n}. Chứng minh tồn tại một tập con D của A + B sao cho 1. D + D ⊆ 2(A + B); 2. |D| ≥ |A|.|B| . 2n Chứng minh. 1. Với mỗi phần tử a ∈ A, xét tập hợp a − B = {a − b|b ∈ B}. Khi đó |a − B| = |B| và a − B ⊂ {−n + 1, −n + 2, . . ., −1, 0, 1, 2, . . . , n − 2, n − 1} = M. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 40 CỰC TRỊ TẬP HỢP 3 BÀI TẬP VẬN DỤNG Ta thấy |M| = 2n − 1. Khi đó ta có |A|.|B| tập hợp dạng a − B, tương ứng sẽ có |A|.|B| số nguyên, tất cả các số nguyên này đều nằm trong M. Do đó theo nguyên lý Dirichlet, tồn tại một phần tử x ∈ M, thuộc vào ít nhất   |A|.|B| |A|.|B| |A|.|B| m= +1 > > 2n − 1 2n − 1 2n tập hợp. Giả sử m tập hợp đó chứa x là a1 − B, a2 − B, . . . , am − B với {a1 , a2 , . . . , am } ⊂ A. 2. Khi đó, các phần tử a1 − a, a2 − x, . . . , am − x đều thuộc vào B. Xét tập D = {2a1 − a, . . . , 2am − x} thì   |A|.|B| |D| = m = +1 2n − 1 và dễ dàng kiểm chứng D + D ⊆ 2(A + B). Bài tập 3.10. Cho n và k là các số nguyên dương sao cho n > k2 − k + 1. Cho n tập hợp, mỗi tập hợp có k phần tử sao cho hai tập hợp tùy ý trong n tập hợp đó đều có đúng một phần tử chung. Chứng minh n tập hợp đó đều có một phần tử chung. Bài tập 3.11. Cho k ≥ 1 là một số tự nhiên. Tìm số tự nhiên nhỏ nhất n sao cho với mọi tập gồm n số nguyên luôn có 2 số mà tổng hoặc hiệu của chúng chia hết cho 2k + 1. Bài tập 3.12. Xác định số n lớn nhất sao cho tồn tại sao cho tồn tại các tập phân biệt S1 , S2 , . . . , Sn thỏa mãn 1. Si 2. Si S S S j ≤ 2006 với mọi 1 ≤ i, j ≤ n. Sj S Sk = {1, 2, . . . , 2010} với mọi 1 ≤ i < j < k ≤ n Bài tập 3.13 (VMO 2004). Cho tập A gồm 16 số nguyên dương đầu tiên. Hãy tìm số nguyên dương k nhỏ nhất có tính chất: trong mỗi tập con có k phần tử của A đều tồn tại hai số phân biệt a, b sao cho a2 + b2 là số nguyên tố. Bài tập 3.14 (Stars of Mathematics 2014). Cho các số nguyên dương M, m, n thỏa mãn 1 ≤ m ≤ m(m + 1) n, 1 ≤ M ≤ và A là một tập con của {1, 2, . . . , n} sao cho |A| = m. Chứng minh rằng tồn tại 2 tập con B ⊆ A sao cho 0 ≤ ∑ b − M ≤ n − m. b∈B Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 41 CỰC TRỊ TẬP HỢP 3 BÀI TẬP VẬN DỤNG Bài tập 3.15 (China 2007). Cho X là tập hợp gồm 56 phần tử. Tìm số nguyên dương n nhỏ nhất sao cho với bất kỳ 15 tập con tùy ý của X, nếu hợp của 7 tập tùy ý trong 15 tập này chứa ít nhất n phần tử, thì tồn tại 3 tập trong 15 tập này mà giao của chúng khác rỗng. Chứng minh. 1. Giả sử X = {1, 2, . . . , 56}. Nếu n ≤ 40, đặt Ai = {i, i + 7, i + 14, i + 21, i + 28, i + 35, i + 42, i + 49}, i = 1, 2, . . . , 7. Viết tường minh như sau A1 = {1, 8, 15, 22, 29, 36, 43, 50} A2 = {2, 9, 16, 23, 30, 37, 44, 51} A3 = {3, 10, 17, 24, 31, 38, 45, 52} A4 = {4, 11, 18, 25, 32, 39, 46, 53} A5 = {5, 12, 19, 26, 33, 40, 47, 54} A6 = {6, 13, 20, 27, 34, 41, 48, 55} A7 = {7, 14, 21, 28, 35, 42, 49, 56}. Đặt B j = { j, j + 8, j + 16, j + 24, j + 32, j + 40, j + 48}, j = 1, 2, . . . , 8. Viết tường minh như sau B1 = {1, 9, 17, 25, 33, 41, 49} B2 = {2, 10, 18, 26, 34, 42, 50} B3 = {3, 11, 19, 27, 35, 43, 51} B4 = {4, 12, 20, 28, 36, 44, 52} B5 = {5, 13, 21, 29, 37, 45, 53} B6 = {6, 14, 22, 30, 38, 46, 54} B7 = {7, 15, 23, 31, 39, 47, 55} B8 = {8, 16, 24, 32, 40, 48, 56}. 2. Khi đó ta có |Ai | = 8(i = 1, 2, . . . , 7), |B j | = 7( j = 1, 2, . . . , 8), |Ai ∩ A j | = 0(1 ≤ i < j ≤ 7), |Bi ∩ B j | = 0(1 ≤ i < j ≤ 8), |Ai ∩ B j | = 1(1 ≤ i ≤ 7, 1 ≤ j ≤ 8). 3. Khi đó với mọi 3 tập trong 15 tập con này, sẽ có hai tập hoặc thuộc họ Ai , hoặc thuộc họ B j . Do đó giao của ba tập này bằng rỗng. Với 7 tập tùy ý trong 15 tập con trên, giả sử là Ai1 , Ai2 , . . . , Ais , B j1 , B j2 , . . . , B jt , s+t = 7 ta có |Ai1 ∪ Ai2 ∪ . . . ∪ Ais ∪ B j1 ∪ B j2 ∪ . . . ∪ B jt | = |Ai1 | + · · · + |Ais | + |B j1 | + · · · + |B jt | − st Do vậy n ≥ 41. = 8s + 7t − st = 8s + 7(7 − s) − s(7 − s) = (s − 3)2 + 40 ≥ 40. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 42 CỰC TRỊ TẬP HỢP 3 BÀI TẬP VẬN DỤNG 4. Ta chứng minh n = 41 là giá trị nhỏ nhất cần tìm. Giả sử ngược lại, tồn tại 15 tập con của X, sao cho hợp của mọi 7 tập trong số 15 tập con đó chứa ít nhất 41 phần tử, nhưng không tồn tại 3 tập trong số 15 tập này có giao khác rỗng. Do mỗi phần tử của X chỉ có thể thuộc vào tối đa 2 tập trong 15 tập đó, ta có thể giả sử mỗi phần tử của X thuộc vào chính xác 2 trong số 15 tập đó (nếu không, thì ta có thể một số phần tử vào một số tập hợp trong 15 tập đó, thì điều kiện đầu tiên vẫn đảm bảo). Theo nguyên lý Dirichlet, tồn tại một tập hợp trong số 15 tập, ký hiệu là A, mà   2 × 56 |A| ≥ + 1 = 8, 15 và gọi 14 tập còn lại là A1 , A2 , . . . , A14. • Do hợp của mọi 7 tập trong A1 , A2 , . . . , A14 chứa ít nhất 41 phần tử. Do đó tổng số phần tử trong 15 tập này   14 . y ≤ 41 × 7 • Với mỗi a ∈ X, nếu a not
∈ A thì a thuộc vào chính 2 2 tập trong số A1 , A2 , . . . , A14 . Do đó a được tính lặp 14 lần. Nếu a ∈ A, thì A chỉ thuộc vào đúng một tập A1 , A2 , . . . , A14 . Do đó a 7 − binom127
T được tính lặp 147 − 13 7 lần. Do đó   14 ≤y 41 × 7         13 14 12 14 − + |A| − ≤ (56 − |A|) 7 7 7 7         12 13 12 14 − − |A| − ≤ 56 7 7 7 7         14 12 13 12 ≤ 56 − −8 − , 7 7 7 7 từ đây dẫn đến 196 ≤ 195, mâu thuẫn. Định lý 3.1 (Erdos). Cho F là một họ các tập con của tập n phần tử X thỏa mãn 1. |F | ≥ 2 và với mọi A ∈ F thì |A| ≥ 2. 2. Với hai phần tử bất kỳ x, y ∈ X tồn tại duy nhất A ∈ F để {x, y} ⊂ A. Khi đó |F | ≥ n. Bài tập 3.16 (China 2011). Cho n là số nguyên dương và đặt S = {1, 2, . . . , n}. Với hai tập con khác rỗng A, B, hãy tìm giá trị nhỏ nhất của |A∆S| + |B∆S| + |(A + B)∆S|. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 43 CỰC TRỊ TẬP HỢP Chứng minh. Khi đó 3 BÀI TẬP VẬN DỤNG 1. Đặt X = A∩S,Y = B∩S. Khi đó A = X ∪A′ và X ∩A′ = 0, / B = B∪B′ , và B′ ∩Y = 0. / |A∆S| = |A| + |S| − 2|A ∩ S| = |A′ | + |X| + |S| − 2|X| = |A′ | + |S| − |X| |B∆S| = |B| + |S| − 2|B ∩ S| = |B′ | + |Y | + |S| − 2|Y | = |B′ | + |S| − |Y | 2. Ta cũng có với hai tập hợp A, B thì |A + B| ≥ |A| + |B| − 1. 3. Nếu cả hai tập A, B ⊂ S, khi đó A = X, B = Y, A′ = 0, / B′ = 0. / Dễ nhận thấy 1 6∈ A + B, do min(A), min(B) ≥ 1. Từ đây suy ra |(A + B) ∩ S| ≤ n − 1. Ta có |(A + B) ∪ S| = |A + B| + |S| − |(A + B) ∩ S| ≥ (|A| + |B| − 1) + n − (n − 1) = |A| + |B|. Do đó |(A + B)∆S| = |(A + B) ∪ S| − |(A + B) ∩ S| ≥ |A| + |B| − (n − 1). Vậy trong trường hợp này ta được |A∆A| + |B∆S| + |(A + B)∆S| ≥ 2|S| − |X| − |Y | + |A| + |B| − n + 1 = 2|S| − n + 1 = n + 1. 4. Nếu ít nhất một trong hai tập A, B không là tập con của S. Khi đó |(A+B)∆S| = |A+B|+|S|−2|(A+B)∩S| ≥ |A+B|+|S|−2|S| = |A+B|−|S| ≥ |A|+|B|−1−|S|. Do đó |A∆S| + |B∆S| + |(A + B)∆S| ≥ |A′ | + |S| − |X| + |B′| + |S| − |Y | + |A| + |B| − 1 − |S| = |A′ | + |S| − |X| + |B′| + |S| − |Y | + |A′| + |X| + |B′ | + |Y | − 1 − |S| = 2|A′ | + 2|B′ | + |S| − 1 ≥ 2 + |S| − 1 = n + 1. Bất đẳng thức cuối cùng có được do ít nhất một bất đẳng thức |A′ | ≥ 1 hoặc |B′ | ≥ 1 phải xảy ra. Vậy trong cả hai trường hợp, thì GTNN của bài toán là n + 1. Ta chứng minh |A + B| ≥ |A| + |B| − 1. Thật vậy, giả sử các phần tử của tập A là a1 < a2 < . . . < ak và các phần tử của B là b1 < b2 < . . . < bl . Khi đó trong tổng A + B luôn có k + l − 1 số tăng dần trong dãy sau a1 + b1 , a1 + b2 , . . . , a1 + bl , a2 + bl , a3 + bl , a4 + bl , . . . , ak + bl . Điều này chứng tỏ kết quả cần chứng minh. Bài tập 3.17. Cho n là số nguyên dương và S là tập gồm n phần tử, A1 , . . . , Am là m tập con, mỗi tập chứa ít nhất hai phần tử, của S thỏa mãn: với bộ ba chỉ số (i, j, k) mà Ai ∩ A j 6= 0, / A j ∩ Ak 6= 0, / Ak ∩ Ai 6= 0/ n−1 thì sẽ có Ai ∩ A j ∩ Ak 6= 0. / Chứng minh rằng m ≤ 2 − 1. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 44 CỰC TRỊ TẬP HỢP 3 BÀI TẬP VẬN DỤNG Chứng minh. Ta chứng minh bằng quy nạp theo n. Hiển nhiên phát biểu đề bài đúng với n = 2. Giả sử kết luận đúng với mọi số nguyên dương bé hơn n. Xét hai trường hợp 1. Không tồn tại i, j nào trong {1, 2, . . . , m} để Ai ∪ A j = S và |Ai ∩ A j | = 1. Gọi x là phần tử tùy ý thuộc S. Khi đó • Theo giả thiết quy nạp, số tập Ai lớn nhất không chứa x là 2n−2 − 1. • Số các tập con chứa x của S bằng 2n−1 . Nếu x ∈ Ai thì sẽ không có chỉ số j nào để A j = (S\Ai ) ∪ {x}, nếu không sẽ dẫn đến |Ai ∩ A j | = 1, mâu thuẫn. Do vậy, chỉ có cùng lắm là một nửa số tập con chứa x của S xuất hiện dưới dạng các tập Ai . Như thế số lớn nhất các tập Ai là 2n−2 − 1 + 2n−2 = 2n−1 − 1. 2. Tồn tại một phần tử x ∈ S sao cho A1 ∪ A2 = S và A1 ∩ A2 = {x}. Đặt |A1 | = r + 1, |A2 | = s + 1 thì r + s = n − 1. • Theo giả thiết quy nạp, số lớn nhất các tập Ai sao cho Ai ⊂ A1 là 2r − 1. • Theo giả thiết quy nạp, số lớn nhất các tập A j sao cho A j ⊂ A2 là 2s − 1. • Bây giờ đếm tiếp xem có bao nhiêu tập dạng Ai mà không là tập con của A1 , A2 . Nếu Ai không là tập con của A1 , A2 thì A1 ∩ Ai 6= 0, / Ai ∩ A j 6= 0. / Vì A1 ∩ A2 6= 0, / nên theo giả thiết thì A1 ∩ A2 ∩ Ai 6= 0/ ⇒ A1 ∩ A2 ∩ Ai = {x}. Do đó Ai = {x ∪ (Ai \A2 ) ∪ (Ai \A2 )}. Ngoài ra co các tập khác rỗng Ai ∩ A1 và Ai \A2 có thể được chọn tương ứng theo 2s − 1 và 2r − 1 cách, nên số lớn nhất các tập Ai dạng này là (2s − 1)(2r − 1). Từ đó suy ra số lớn nhất các tập dạng này là 2r − 1 + 2s − 1 + (2r − 1)(2s − 1) = 2r+s − 1 = 2n−1 − 1. Bài toán được chứng minh hoàn toàn. TÀI LIỆU THAM KHẢO 1. Một số định lý trong lý thuyết tập hợp cực trị, Vũ Thế Khôi, Bài giảng tại Viện Toán Học dành cho trường hè 2012. 2. Combinatorial Mathematics, Stefan H. M. van Zwam, Princeton University 2013. 3. Khoảng cách Hamming, bài giảng trên mạng. 4. Combinatorics of sets, Po-Shen Loh, June 2013. 5. Combinatorial problems in Mathematical Competitions, Yao Zhang, World Scientific 2011. 6. Đề thi học sinh giỏi các nước trên trang mathlinks.ro. Ths Trần Minh Hiền(0989.541.123) - Trường THPT chuyên Quang Trung 45