Cho tập $S$ có $n$ phần tử và $F=\left \{ A_{1}, A_{2}, ..., A_{m} \right \}$ là các tập con gồm $k$ phần tử của $S,$ $k\leq \frac{n}{2}$ sao cho $\forall i, j\in \left \{ 1, 2, ..., k \right \}; i\neq j$ thì $\begin{vmatrix} A_{i}\cap A_{j} \end{vmatrix} \geq 1.$ Chứng minh rằng: $m\leq C_{n-1}^{k-1}.$
Chứng minh rằng: $m\leq C_{n-1}^{k-1}.$
#2
Đã gửi 10-07-2017 - 19:26
Gọi $A$ là tập các tập con $k$ phần tử của $S$ chứa $n$, $B$ là 1 tập các tập con $k$ phần tử của $S$ mà không chứa $n$ để $2$ tập bất kì trong $B$ có giao khác rỗng.
Lập một đồ thị $2$ phe $A$ và $B$ mà $2$ đỉnh là $2$ tập thuộc $2$ phe nối với nhau nếu giao của chúng bằng rỗng. Ý tưởng là ta sẽ xây dựng $F$ là hợp tập $B$ và $1$ số phần tử tập $A$
Mỗi phần tử tập $B$ nối với đúng $\binom {n-k-1}{k-1}$ phần tử tập $A$ và mỗi phần tử tập $A$ nối với $1$ số tập con của tập có $n-1-(k-1)=n-k$ phần tử, mỗi tập có $k$ phần tử và không có $2$ trong số các tập con đó giao bằng rỗng. Theo quy nạp thì mỗi phần tử tập $A$ nối không quá $\binom{n-k-1}{k-1}$ phần tử tập $B$. Vì vậy số phần tử tập $A$ nối với $1$ trong số các phần tử tập $B$ $\geq |B|$. Khi thêm tập $B$ vào tập $A$ thì phải loại bỏ các phần tử đó từ tập $A$. Vậy $m=|F| \leq |A|+|B|-|B|=|A|=\binom{n-1}{k-1}$
Bài viết đã được chỉnh sửa nội dung bởi JUV: 10-07-2017 - 19:30
- Zz Isaac Newton Zz, redfox và lamNMP01 thích
#3
Đã gửi 10-07-2017 - 23:06
Đây chính là định lý Erdos-Ko-Rado
Bổ đề 1 : Với mỗi $0 <= s<= n-1$ Xét tập con $A_s$ = { s, s+1,...........s+k-1 } mà phép cộng tính trong Zn
Cmr F chứa nhiều nhất k tập con kiểu $A_s$
Áp dụng bổ đề vào cm định lý này :
Xét 1 hoán vị con phi của { 0,1,2,........,n-1 } và i={0,1,.......n-1} được chọn 1 cách ngẫu nhiên và độc lập , và xét tập A chứa các hoán vị phi i , phi i+1,......... phi i+k-1 } và vẫn tính trên Zn
Khi đó ta có Pr[A thuộc F] <= k/n. Nhưng A chọn ngẫu nhiên trong bộ k phần tử nên
k/n >= Pr[A thuộc F]= |F|/ nCk
Nên |F| <=............. ta có đpcm
- IHateMath, Zz Isaac Newton Zz và redfox thích
#4
Đã gửi 20-08-2017 - 09:41
Theo quy nạp thì mỗi phần tử tập $A$ nối không quá $\binom{n-k-1}{k-1}$ phần tử tập $B$.
Chỗ này không đúng lắm, điều kiện quy nạp chỉ áp dụng được cho $k \leq \frac{n}{2}$ mà thôi.
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh