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ó phần tử bằng
.
Lời giải. Dùng phương pháp quy nạp theo hoặc chú ý là mỗi tập con sẽ ứng với một xâu nhị phân có độ dài
.
Bài 2. Cho tập hợp
thoả mãn các tính chất sau
a);
b).
Chứng minh rằng .
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ử là số nguyên dương lớn nhất sao cho trong các tập đó ta tìm được
tập có giao khác rỗng. Không giảm tổng quát gọi các tập đó là
và
, cố định
, trong
tập còn lại vì mỗi tập giao với
tại đúng một phần tử và chúng đôi một giao nhau đúng một phần tử, suy ra
thuộc ít nhất
tập trong
tập này, suy ra
. Vì
không thuộc
nên
sẽ không thuộc
tập
, đương nhiên
tập này đôi một rời nhau và là các tập con của
, suy ra
, 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 sao cho
và
.
Lời giải. Mỗi bộ ba như vậy ứng với một xâu , vì mỗi phần tử
chỉ có thể thuộc
và
. Đáp số
.
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 phần tử?
Lời giải. Kí hiệu một cặp nào đó như đầu bài là . Nếu
thì chúng ta sẽ có
cách chọn
, sau khi chọn
rồi thì số cách chọn
bằng số cách chọn một tập con của tập
, tập này có
phần tử (
là tập có
phần tử trong đầu bài), hay số cách chọn
bằng
. Vậy đáp số của bài toán là
.
Cách tiếp cận khác: Mỗi cặp như vậy sẽ ứng với một xâu vì mỗi phần tử của
có thể thuộc
, hoặc
, hoặc không thuộc cả hai tập đó.
Bài 5. Tập có
phần tử. Đối với cặp có thứ tự tập con
của
, ta tính số phần tử của
. Chứng minh rằng tổng các số nhận được bằng
.
Lời giải. Gỉa sử là một cặp tập con của
,
và
. Ta thấy có
cách chọn
, sau khi đã chọn
rồi thì số cách chọn
bằng số cách chọn cặp
các tập con rời nhau của tập
, vì tập này có
phần tử nên số các cặp
bằng
. Vậy đáp số của bài toán là
.
Cách tiếp cận khác: Có cặp tập
, chia các cặp này thành các bộ bốn
, mỗi phần tử của
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
, mà có đúng
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 , tìm số nguyên dương
lớn nhất sao cho trong một tập hợp có
phần tử có thể chọn ra
tập con của nó đôi một giao nhau.
Lời giải. Gọi là một tập có
phần tử và
là một phần tử của nó. Xét
tập con của
có dạng
với
là một tập con của tập
, 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
tập con của
, bao giờ cũng tồn tại hai tập trong cùng một bộ
và hai tập này giao nhau bằng rỗng. Vậy đáp số của bài toán là
.
Bài 7. Gỉa sử trong tập hữu hạn chọn ra
tập hợp con
sao cho mỗi tập này chứa hơn một nửa phần tử của
. Chứng minh rằng tồn tại tập con
của
thoả mãn các điều kiện sau
a), và
b).
Bài 8(APMO ). Cho
là tập tất cả các
-bộ
sao cho mỗi
là một tập con của tập
. Tính
Bài 9(RMC ). Một tập
gồm
số nguyên dương được gọi là liên thông nếu với mỗi
trong
ít nhất một trong các số
thuộc
. Cho
là số các tập con liên thông của tập
.
a)Tính ;
b)Tìm nhỏ nhất để
.
Bài 10(RMC ). Tìm số lớn nhất các tập con của tập
sao cho mỗi hai tập con khác nhau trong chúng có giao là một tập có
phần tử.