Lời giải bài 6.

Cho mình hỏi ý 7b) tồn tại đúng 1 hay ít nhất 1 câu lạc bộ có k thành viên vậy? Nếu có nhiều hơn 1 câu lạc bộ có k thành viên thì sẽ có phản ví dụ: Mỗi học sinh tham gia tất cả m câu lạc bộ, khi đó k = n và n tùy ý vẫn thỏa mãn.

Bài toán 7. 

Câu a:

Bài toán này sử dùng công thức khá hay trong bài toán đếm bằng 2 cách như sau : 

Cho X={1,2,3,...,n}. Gọi \(A_1,A_2,...,A_k\) là các tập con của X thỏa mãn : với mọi i=1,2,3,...,k thì \(|A_i|=m\). 

Gọi \(d_i\) là số tập con trong k tập con trên mà chứa phần tử i ( với i= 1,2,..,n).

Công thức 1: \(\sum\limits_{i=1}^{n} d_i= \sum\limits_{i=1}^{k} |A_i|\) 

hay: \(d_1+d_2+...+d_n=|A_1|+|A_2|+...+|A_k|\)

Công thức 2: \(\sum\limits_{i=1}^{n} d_i^2=\sum\limits_{1 \leq i < j \leq n} |A_i \cap A_j|\)

Về việc chứng minh các công thức trên:

Ta xét bảng ô vuông n hàng( gọi các hàng là hàng 1,hàng 2,...,hàng n); k cột (cột 1,cột 2,...,cột k).

Nếu phần tử i (với i =1,2,..,n) thuộc \(A_x\) thì tại hàng i cột x ta điền số 1, ngược lại nếu phần tử i (với i =1,2,..,n) không thuộc \(A_x\) ta điền số 0.

Thế thì công thức 1 là việc đếm bằng hai cách: Sô các số 1 xuất hiện trong bảng.

Công thức 2 ta đi đếm tổng số phần tử giao của 2 tập con bất kỳ= số cặp số 1 (không tính thứ tự) cùng nằm trên 1 cột.

Chú ý ở công thức 2, vế phải có: \(C_n^2\) phần tử. Và ở vế trái ta có thể đánh giá bất đẳng thức Bunhiacopxki : \(\sum\limits_{i=1}^{n} d_i^2 \geq \dfrac{(\sum\limits_{i=1}^{n}d_i)^2}{n}\)