Đối với mỗi giá trị \(n \in \mathbb{N}\), hãy tìm số \(k\) lớn nhất \(k \in \mathbb{N}\) thoả mãn

Câu hỏi số 554351:

Vận dụng cao

Đối với mỗi giá trị \(n \in \mathbb{N}\), hãy tìm số \(k\) lớn nhất \(k \in \mathbb{N}\) thoả mãn tính chất sau: Trong tập hợp gồm \(n\) phần tử có thể chọn ra \(k\) tập hợp con khác nhau, sao cho hai tập con bất kì đều có giao khác rỗng.

Quảng cáo

Xem lời giải

Câu hỏi:554351

Phương pháp giải

Nguyên lý Dirichlet cơ bản: Nếu nhốt \(n\) thỏ vào \(m\) chuồng \(\left( {n > m} \right)\), nghĩa là số thỏ nhiều hơn số chuồng, thì ít nhất cùng có một chuồng nhốt không ít hơn hai thỏ.

Giải chi tiết

+ Cố định phần tử \({a_i}\) của \(X = {a_1};{a_2};{a_3}...;{a_n}\) và xét các tập con chứa phần từ \({a_1}\).

Số các tập hợp như vậy bằng số các tập con của tập \(X\), tức là bằng \(2n - 1\)

\( \Rightarrow k \ge 2n - 1\)

+ Giả sử chọn được hơn \(2n - 1\) tập con của \(X\).

Ta chia tất cả các tập con của \(X\) thành \(2n - 1\) cặp được tạo nên từ một tập con của \(X\) và phần bù của nó.

Theo nguyên Lý Dirichlet có ít nhất hai tập con đã chọn tạo thành một cặp \( \Rightarrow \) chúng không giao nhau.

Vậy \(k = 2n - 1\)

Tham Gia Group Dành Cho 2K13 Chia Sẻ, Trao Đổi Tài Liệu Miễn Phí

Câu hỏi trước Câu tiếp theo

>> Học trực tuyến lớp 6 chương trình mới trên Tuyensinh247.com. Học bám sát chương trình SGK mới nhất của Bộ Giáo dục. Cam kết giúp học sinh lớp 6 học tốt, hoàn trả học phí nếu học không hiệu quả. Phụ huynh và học sinh tham khảo chi tiết khoá học tại: Link