Đề tài Hàm đặc trưng của tập hợp và Ứng dụng

x) = 0, A(x) = 1. Lúc đó, do (1) thì B(x) = 0. Từ bất đẳng thức D ≤ B suy ra D(x) = 0. Nhưng điều này mâu thuẫn với (2). Bài tập 4. Cho E là một tập hợp, X, Y, Z, X’, Y’, Z’  P(E). Giả thiết rằng: X  Y  Z = E, X  Y = X’  Y’, X  Z = X’  Z’, Y  Z = Y’  Z’, X  X’, Y  Y’, Z  Z’. Chứng minh rằng X = X’, Y = Y’, Z = Z’. 4. Ứng dụng hàm đặc trưng trong các bài toán đếm Một trong những ứng dụng đẹp đẽ và có chiều sâu nhất của hàm đặc trưng là ứng dụng trong các bài toán đếm. Và cơ sở của ứng dụng này là công thức hiển nhiên sau:    Ex A xA )(||  Trước hết, ta sẽ ứng dụng công thức này để chứng minh lại một số nguyên lý cơ bản của phép đếm. Nguyên lý cộng Nếu A  B =  thì |A  B| = | A | + | B | Nguyên lý nhân |A x B| = | A |.| B | Nguyên lý trừ |||||| AEA  Nguyên lý bù trừ |A  B| = | A | + | B | - |A  B| Chứng minh Rõ ràng nguyên lý cộng và nguyên lý trừ là hệ quả của nguyên lý bù trừ, do đó ta chỉ cần chứng minh nguyên lý bù trừ là suy ra hai nguyên lý còn lại. Ta có A  B = A + B - A.B = A + B - AB Từ đó suy ra A  B(x) = A(x) + B(x) - AB(x) Cho x chạy qua khắp E rồi cộng lại, ta được         Ex Ex BAB Ex A Ex BA xxxx )()()()(  Nhưng điều này, theo công thức cơ bản ở trên, có nghĩa là |A  B| = | A | + | B | - |A  B| Ta có điều phải chứng minh. Theo định nghĩa thì AxB(x, y) = A(x).B(y). Ta có       Ex By BA FEyx BA FEyx BA BAyxyxyxBA ||.||)(.)()().(),(|| ),(),(  Như vậy quy tắc nhân đã được chứng minh. Bài tập 5. Cho A, B, C là các tập hợp bất kỳ, chứng minh rằng | A  B  C | = | A | + | B | + | C | - (|A  B| + | A  C| + |B  C|) + |A  B  C|. 6. Chứng minh công thức bao hàm và loại trừ (Nguyên lý bù trừ) tổng quát.        n i niii n n iii nji jii n i i AAAAAAAAA 1 1 1 1 11 321 321 |...|)1(...||||1|||| Tiếp theo, ta sẽ ứng dụng công thức này để giải thích phương pháp đếm theo phần tử. Ta minh họa phương pháp này qua bài toán sau. Ví dụ 5. Cho E = {1, 2, , n}. F = P(E). Hãy tính    2),( || FBA BAS Giải. Bài này có thể giải bằng hai cách, cách 1 là đếm theo tập hợp và cách hai là đếm theo phần tử. Với cách 1, ta gọi s(k) là số tất cả các bộ (A, B)  F2 sao cho |A  B| = k. Thế thì rõ ràng    n k kskS 0 )(. Như vậy ta chỉ cần đi tìm s(k). Với mỗi k cố định, có knC cách chọn ra một tập con gồm k phần tử. Giả sử đó là C. Nếu ta cho A  B = C thì |A  B| = k. Để đảm bảo điều này, sau đó mỗi phần tử thuộc E \ C có thể: a) Không thuộc A, không thuộc B; b) Thuộc A, không thuộc B; c) Thuộc B, không thuộc A. Tức là có 3 cách chọn. Từ đó suy ra knknCks  3.)( . Cuối cùng 1 00 43.)(.       nn k knk n n k nCkkskS (Tại sao?) Lời giải trên là khá phức tạp, bao gồm 2 bước lý luận khó: 1) Tính được s(k); 2) Rút gọn tổng   n k knk nCk 0 3. . Tuy nhiên, đáp số bài toán lại khá đơn giản: n4n-1. Ta thử tìm một cách tiếp cận khác cho ra thẳng đáp số này. Và thừa số n ở đáp số gợi cho chúng ta đến phương pháp đếm theo phần tử, tức là đếm số lần một phần tử x xuất hiện trong các tập hợp A  B. Cụ thể ta có            2 22 ),( ),(),( )()(|| FBA Ex FBA BA Ex BA FBA xxBAS  Ở đây ta đã đảo thứ tự lấy tổng. Với một phần tử x  E = {1, 2, , n} cố định, xét tổng    2),( )( FBA BA x . Ta thấy 1)(  xBA   khi và chỉ khi A  B chứa x. Như vậy    2),( )( FBA BA x |{(A, B)  F2| x  A  B}|, tức là tổng trên bằng số bộ (A, B) sao cho cả A và B đều chứa x. Có 2n-1 tập con của E chứa x. Do đó, theo quy tắc nhân, số bộ (A, B) để A  B chứa x bằng 2n-1 x 2n-1 = 4n-1. Từ đó .4.4)( 11 ),( 2          n Ex n Ex FBA BA nxS  Ghi chú. Từ kết quả bài toán này ta suy ra kết luận sau: “Nếu lấy ngẫu nhiên hai tập con A, B thuộc E = {1, 2, , n} thì giá trị kỳ vọng của |A  B| là . 4 n Ví dụ 6. (APMO 1998). Xét tập hợp E = {1, 2, , 1998} và F là tập hợp tất cả các tập con của E. Hãy tính tổng    n n FAAA nAAAS ),...,,( 21 21 |...| Giải. Nếu giải bài này bằng phương pháp đếm theo tập hợp sẽ gặp khá nhiều khó khăn. Tuy nhiên, phương pháp đếm theo phần tử cho ta kết quả một cách nhanh chóng            Ex FAAA AAA FAAA Ex AAA FAAA n xxAAA n n n n n n n n )()(|...| ),...,,( ... ),...,,( ... ),...,,( 21 21 21 21 21 21  Tổng bên trong đúng bằng số các bộ (A1, A2, , An) mà A1  A2   An chứa x. Ta có tổng số các bộ (A1, A2, , An) bằng (21998)n (21998 là số các tập con của E). Tổng số các bộ (A1, A2, , An) mà A1  A2   An không chứa x bằng (21997)n (21997 là số các tập con của E không chứa x). Từ đó suy ra số các bộ (A1, A2, , An) mà A1  A2   An chứa x bằng (21998)n – (21997)n. Từ đó suy ra S = 1998((21998)n – (21997)n) = 1998(2n-1)21997.n. Bài tập 7. Cho E = {1, 2, , n}. Với mỗi k = 0, 1, 2, , n đặt Fk = {A  E| |A| = k} (tức là tập hợp tất cả các tập con có k phần tử của E). Hãy tính tổng    qp FFBA BA ),( || 8. (VMO 2002, bảng B) Cho tập hợp S gồm tất cả các số nguyên trong đoạn [1; 2002]. Gọi T là tập hợp tất cả các tập hợp con không rỗng của S. Với mỗi tập con X thuộc T, ký hiệu m(X) là trung bình cộng của tất cả các số thuộc X. Đặt || )( T Xm m  , ở đây tổng lấy theo tất cả các tập hợp X thuộc T. Hãy tính giá trị của m. 5. Một số ứng dụng khác của phương pháp đếm theo phần tử Phương pháp đếm theo phần tử được trình bày ở mục 4 có thể được tổng quát hóa như sau: Cho F là họ các tập con của X. Với x thuộc x, ta gọi d(x) là số phần tử của F chứa x. Định lý 2. Cho F là họ các tập con của tập hợp X. Khi đó Chứng minh. Xét ma trận kề M = (mx,A) của F. Nghĩa là M là ma trận 0-1 với |X| dòng đánh số bởi các điểm x  X và |F| cột đánh số bởi tập A  F sao cho mx,A = 1 khi và chỉ khi x  A. Để ý rằng d(x) bằng số số 1 trên dòng thứ x còn |A| là số số 1 trên cột thứ A. Như vậy cả vế trái và vế phải đều biểu diễn số số 1 của M. Nếu ta xét đồ thị G = (V, E) trên tập đỉnh V như một họ các tập con 2 phần tử của V thì ta có định lý Euler. Định lý 3. (Euler, 1736) Trong mọi đồ thị, tổng bậc các đỉnh của nó bằng hai lần số cạnh của nó và như thế, luôn là một số chẵn. Định lý sau có thể được chứng minh bằng cách tương tự Định lý 4. với mọi Y  X. (Hai tổng ở đẳng thức đầu ứng với số số 1 trên các hàng Y. Các tổng ở đẳng thức thứ hai đếm số lần xuất hiện của x trong các tập có dạng A ∩ B). Trường hợp đặc biệt khi F = E là tập con 2 phần tử, ta có Định lý 5. Với đồ thị G = (V, E), ta có Định lý sau đây của hình học tổ hợp có nhiều ứng dụng hiệu quả trong các bài toán đánh giá diện tích và được chứng minh dựa trên ý tưởng của công thức bao hàm và loại trừ, cũng như phương pháp đếm theo phần tử (dù ở đây chúng ta không làm việc với tập hợp hữu hạn). Định lý 6. Trên mặt phẳng cho n hình. Gọi kii S ...1 là diện tích phần giao của các hình với chỉ số i1, , ik. S là diện tích phần mặt phẳng được phủ bởi các hình trên; Mk là tổng tất cả các kii S ...1 . Khi đó: a) S = M1 – M2 + M3 - + (-1)n+1Mn; b) S ≥ M1 – M2 + M3 - + (-1)m+1Mm khi m chẵn và S ≤ M1 – M2 + M3 - + (-1)m+1Mm khi m lẻ. Chứng minh. a) Gọi Wm là diện tích phần mặt phẳng được phủ bởi đúng m hình. Phần mặt phẳng này tạo thành từ các mẩu, mỗi một mẩu được phủ bởi m hình xác định nào đó. Diện tích mỗi một mẩu như vậy khi tính Mk được tính kmC lần, vì từ m hình có thể thiết lập được kmC phần giao của k hình. Vì vậy n k nk k kk k kk WCWCWCM   ...11 Suy ra     ,... ......)1(... 21 321 2 2 2 1 21 1 1 1 321 n nnnnn n WWW WCCCWCCWCMMMM    vì .11)11(1...)1()1(... 21321  mmmmmmmmm CCCCCC Cuối cùng, chú ý rằng S = W1 + W2 + + Wn, ta suy ra điều phải chứng minh. b) Chứng minh phần b) xin được dành cho bạn đọc. Ta xem xét một ứng dụng trực tiếp của định lý 6. Ví dụ 7. a) Trong hình vuông diện tích 6 có ba hình đa giác có diện tích mỗi hình bằng 3. Chứng minh rằng trong chúng tồn tại hai hình đa giác có diện tích phần chung không nhỏ hơn 1. b) Trong hình vuông diện tích 5 có chín hình đa giác có diện tích mỗi hình bằng 1. Chứng minh rằng trong chúng tồn tại hai đa giác có diện tích phần chung không nhỏ hơn 1/9. Giải. a) Theo định lý 6, phần a) thì ta có 6 = 9 – (S12 + S23 + S13) + S123. Từ đó suy ra S12 + S23 + S13 = 3 + S123 ≥ 3 Suy ra một trong các số S12, S23, S13 không nhỏ hơn 1. b) Theo định lý 6, phần b) thì 5 ≥ 9 – M2, tức là M2 ≥ 4. Vì từ 9 hình đa giác có thể tạo ra 9.8/2 = 36 cặp, nên diện tích phần trong của một trong các cặp như vậy không nhỏ hơn M2/36 ≥ 1/9. Bài tập 9. Trong hình chữ nhật diện tích 1 có 5 hình có diện tích mỗi hình bằng 1/2. a) Chứng minh rằng tồn tại hai hình có diện tích phần chung không nhỏ hơn 3/20. b) Chứng minh rằng tồn tại hai hình có diện tích phần chung không nhỏ hơn 1/5. c) Chứng minh rằng tồn tại ba hình có diện tích phần chung không nhỏ hơn 1/20. 10. (Olympic toàn Nga, 1996) Trong Duma có 1600 đại biểu, tạo thành 16000 ủy ban, mỗi ủy ban có 80 người. Chứng minh rằng tồn tại hai ủy ban có chúng ít nhất 4 thành viên. 6. Tài liệu tham khảo [1]. Đoàn Quỳnh (chủ biên), Doãn Minh Cường, Trần Nam Dũng, Đặng Hùng Thắng, Tài liệu giáo khoa chuyên toán, Đại số 10, NXB Giáo dục Việt Nam, 2009. [2]. Nguyễn Hữu Anh, Toán rời rạc, Nhà xuất bản Giáo dục, 1999. [3]. Jean-Marie Monier, Giáo trình Toán, Tập 5, Đại số 1, Nhà xuất bản Giáo dục, 1999. [4]. Trần Nam Dũng, Kỹ thuật đếm bằng hai cách ứng dụng trong giải toán, Kỷ yếu Hội nghị khoa học, Các chuyên đề chuyên toán – Bồi dưỡng HSG THPT, Nam Định, 11/2010. [5]. Alfutova N.B., Ustinov A.V., Đại số và Lý thuyết số, NXB MCCME 2002. [6]. Prasolov V.V., Các bài toán hình học, NXB MCCME 2001.