Đến nội dung

Hình ảnh

Chứng minh rằng: $m\leq C_{n-1}^{k-1}.$

- - - - -

  • Please log in to reply
Chủ đề này có 3 trả lời

#1
Zz Isaac Newton Zz

Zz Isaac Newton Zz

    Sĩ quan

  • Điều hành viên OLYMPIC
  • 392 Bài viết

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}.$


  • JUV yêu thích

#2
JUV

JUV

    Trung sĩ

  • Điều hành viên OLYMPIC
  • 138 Bài viết
Quy nạp theo $n$. Dễ thấy với $n=1,2,3$ thì bài toán đúng.
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


#3
lamNMP01

lamNMP01

    Hạ sĩ

  • Thành viên
  • 96 Bài viết

Đâ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



#4
Donald Trump

Donald Trump

    Binh nhất

  • Thành viên mới
  • 28 Bài viết

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