Chủ đề này có 3 trả lời

[NTMFlashNo1]

Cho $l\leq k\leq n$ là các số thỏa mãn:

$\Im$ là họ các tập L-phần tử của X={1,2,...,n} nào đó  

thỏa mãn:với mọi tập con A có K-phần tử của X đều chứa ít nhất 1 tập B thuộc $\Im$

C/m:$\left | \Im \right |\geq \frac{\begin{pmatrix} n\\ l \end{pmatrix}}{\begin{pmatrix} 2\\ k \end{pmatrix}}$

[Karl Heinrich Marx]

Cho $l\leq k\leq n$ là các số thỏa mãn:

$\Im$ là họ các tập L-phần tử của X={1,2,...,n} nào đó  

thỏa mãn:với mọi tập con A có K-phần tử của X đều chứa ít nhất 1 tập B thuộc $\Im$

C/m:$\left | \Im \right |\geq \frac{\begin{pmatrix} n\\ l \end{pmatrix}}{\begin{pmatrix} 2\\ k \end{pmatrix}}$

Tại sao lại là $\begin{pmatrix} 2\\ k \end{pmatrix}$? Vậy chỉ xét trường hợp $k \le 2$ thôi sao?

Thực ra không khó để chứng minh giá trị nhỏ nhất của $\left | \Im \right |$ là $\begin{pmatrix} n\\ l \end{pmatrix} - \begin{pmatrix} k\\ l \end{pmatrix}+1$. 

[NTMFlashNo1]

Tại sao lại là $\begin{pmatrix} 2\\ k \end{pmatrix}$? Vậy chỉ xét trường hợp $k \le 2$ thôi sao?

Thực ra không khó để chứng minh giá trị nhỏ nhất của $\left | \Im \right |$ là $\begin{pmatrix} n\\ l \end{pmatrix} - \begin{pmatrix} k\\ l \end{pmatrix}+1$. 

Viết hẳn hoi ra đi bạn

chứ cứ úp mở thế ai pít đc

[Karl Heinrich Marx]

Viết hẳn hoi ra đi bạn

chứ cứ úp mở thế ai pít đc

Bởi vì lâu rồi mình k dùng diễn đàn nên quên cách đánh công thức ngại viết.

Xin lỗi trong lúc suy nghĩ mình hơi nhầm lẫn khái niệm 1 tí, cái mình nói là số nhỏ nhất để với mọi tập có từng đó phần tử sẽ luôn thỏa đề bài.

Còn tập thỏa đề bài có số phần tử nhỏ nhất có vẻ sẽ khó hơn nhưng có thể chứng minh số này không nhỏ hơn $C_n^l/C_k^l = C_n^k/C_{n-l}^{k-l}$

nên có thể thay $C_2^k$ của bạn bằng $C_k^l$.

Chứng minh thì mỗi tập thuộc $J$ có $C_{n-l}^{k-l}$ tập gồm $k$ phần tử là con $X$ và chứa tập này. Như vậy $|J|.C_{n-l}^{k-l}$ không bé hơn số tập con có $k$ phần tử của $X$.

Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 09-11-2016 - 04:05