Tập hợp và tập hợp con


Trong bài này chúng ta sẽ quan tâm đến các tập hợp nhưng không quan tâm đến tính chất của các phần tử của nó.

Bài 1. Chứng minh rằng số tập con của tập có n phần tử bằng 2^n.

Lời giải. Dùng phương pháp quy nạp theo n hoặc chú ý là mỗi tập con sẽ ứng với một xâu nhị phân có độ dài n.
Bài 2. Cho 1978 tập hợp A_{1},\cdots,A_{1978} thoả mãn các tính chất sau
a)|A_i\cap A_j|=1\forall i<j;
b)|A_i|=40\forall i.
Chứng minh rằng |\cap A_i|=1.
Lời giải. Gỉa sử ngược lại, khi đó giao của các tập hợp phải bằng rỗng. Gỉa sử m là số nguyên dương lớn nhất sao cho trong các tập đó ta tìm được m tập có giao khác rỗng. Không giảm tổng quát gọi các tập đó là A_1,A_2,\cdots,A_m\{x\}=\cap_{i=1}^mA_i, cố định A_1, trong 1977 tập còn lại vì mỗi tập giao với A_1 tại đúng một phần tử và chúng đôi một giao nhau đúng một phần tử, suy ra x thuộc ít nhất [1977/40]+1=50 tập trong 1977 tập này, suy ra m\geq 51. Vì x không thuộc A_{m+1} nên x sẽ không thuộc m tập A_i\cap A_{m+1}, đương nhiên m tập này đôi một rời nhau và là các tập con của A_{m+1}, suy ra m\leq 40, vô lý! Bài toán được giải hoàn toàn.
Bài 3. Tìm số các bộ ba có thứ tự các tập (A,B,C) sao cho A\cup B\cup C=\{1,2,\cdots,2003\}A\cap B\cap C=\emptyset.
Lời giải. Mỗi bộ ba như vậy ứng với một xâu (a_1,a_2,\cdots,a_{2003})\in \{1,2,3,4,5,6\}^{2003}, vì mỗi phần tử i chỉ có thể thuộc A,B,C,A\cap B,B\cap CC\cap A. Đáp số 6^{2003}.
Bài 4. Có bao nhiêu cặp có thứ tự tập hợp con không giao nhau của tập hợp gồm n phần tử?
Lời giải. Kí hiệu một cặp nào đó như đầu bài là (A_1,A_2). Nếu |A_1|=k thì chúng ta sẽ có C_n^k cách chọn A_1, sau khi chọn A_1 rồi thì số cách chọn A_2 bằng số cách chọn một tập con của tập S-A_1, tập này có n-k phần tử (S là tập có n phần tử trong đầu bài), hay số cách chọn A_2 bằng 2^{n-k}. Vậy đáp số của bài toán là \sum_{k=0}^n C_n^k2^{n-k}=(2+1)^n=3^n.
Cách tiếp cận khác: Mỗi cặp như vậy sẽ ứng với một xâu (a_1,a_2,\cdots,a_n)\in\{0,1,2\}^n vì mỗi phần tử của S có thể thuộc A_1, hoặc A_2, hoặc không thuộc cả hai tập đó.

Bài 5. Tập Xn phần tử. Đối với cặp có thứ tự tập con (A_1,A_2) của X, ta tính số phần tử của A_1\cap A_2. Chứng minh rằng tổng các số nhận được bằng n4^{n-1}.
Lời giải. Gỉa sử (A_1,A_2) là một cặp tập con của X, |A_1\cap A_2|=kH=A_1\cap A_2. Ta thấy có C_n^k cách chọn H, sau khi đã chọn H rồi thì số cách chọn (A_1,A_2) bằng số cách chọn cặp (B_1,B_2) các tập con rời nhau của tập X-H, vì tập này có n-k phần tử nên số các cặp (B_1,B_2) bằng 3^{n-k}. Vậy đáp số của bài toán là \sum_{k=0}^nkC_n^k3^{n-k}=n4^{n-1}.
Cách tiếp cận khác: Có 4^n cặp tập (A_1,A_2), chia các cặp này thành các bộ bốn \{(A_1,A_2),(\overline{A}_1,A_2),(A_1,\overline{A}_2),(\overline{A}_1,\overline{A}_2)\}, mỗi phần tử của X sẽ thuộc đúng một trong bốn giao hình thành từ bộ này, do đó tổng đối với bộ này bằng n, mà có đúng 4^{n-1} bộ nên ta có điều phải chứng minh.

Bài 6. Đối với mỗi số nguyên dương n, tìm số nguyên dương k lớn nhất sao cho trong một tập hợp có n phần tử có thể chọn ra k tập con của nó đôi một giao nhau.
Lời giải. Gọi X là một tập có n phần tử và a là một phần tử của nó. Xét 2^{n-1} tập con của X có dạng \{a\}\cup A với A là một tập con của tập X-\{a\}, rõ ràng các tập con này là đôi một giao nhau (cách chọn như vậy là dễ nhất và đây cũng là chìa khoá cho lời giải). Mặt khác với mỗi cách chọn lớn hơn 2^{n-1} tập con của X, bao giờ cũng tồn tại hai tập trong cùng một bộ \{A,\overline{A}\} và hai tập này giao nhau bằng rỗng. Vậy đáp số của bài toán là 2^{n-1}.

Bài 7. Gỉa sử trong tập hữu hạn X chọn ra 50 tập hợp con A_1,A_2,\cdots,A_{50} sao cho mỗi tập này chứa hơn một nửa phần tử của X. Chứng minh rằng tồn tại tập con A của X thoả mãn các điều kiện sau
a)|A|<6, và
b)A\cap A_i\not =\emptyset.

Bài 8(APMO 1998). Cho F_n là tập tất cả các n-bộ (A_1,A_2,\cdots,A_n) sao cho mỗi A_i là một tập con của tập \{1,2,\cdots,2009\}. Tính \sum_{(A_1,A_2,\cdots,A_n)\in F_n}|A_1\cup A_2\cup\cdots\cup A_n|.

Bài 9(RMC 2006). Một tập M gồm 4 số nguyên dương được gọi là liên thông nếu với mỗi x trong M ít nhất một trong các số x-1,x+1 thuộc M. Cho U_n là số các tập con liên thông của tập \{1,2,\cdots,n\}.
a)Tính U_7;
b)Tìm n nhỏ nhất để U_n\geq 2006.

Bài 10(RMC 2006). Tìm số lớn nhất các tập con của tập \{1,2,\cdots,2006\} sao cho mỗi hai tập con khác nhau trong chúng có giao là một tập có 2004 phần tử.

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