$2)$
Ta chứng minh bằng phản chứng.
Giả sử trong $n$ tập đã cho, bất kỳ tập nào cũng chứa ít nhất $1$ tập trong số các tập còn lại (ta tạm gọi đây là điều giả sử (1))
Gọi $m$ là số phần tử tối đa của $n$ tập đó.Xét tập $A_{p}$ là tập có $m$ phần tử ($A_{p}$ là một trong $n$ tập đã cho)
Giả sử $A_{p}$ chứa $A_{q}$ ($A_{p}\supset A_{q}$).Vì $A_{p}\neq A_{q}$ nên suy ra $\left | A_{p} \right |> \left | A_{q} \right |$
$A_{q}$ chứa $A_{r}$ ($A_{q}\supset A_{r}$).Vì $A_{q}\neq A_{r}$ nên suy ra $\left | A_{q} \right |> \left | A_{r} \right |$
$A_{r}$ chứa $A_{s}$ $\Rightarrow \left | A_{r} \right |> \left | A_{s} \right |$ ...
Cuối cùng ta có : $\left | A_{p} \right |> \left | A_{q} \right |> \left | A_{r} \right |> \left | A_{s} \right |> ...> \left | A_{i} \right |$
Vì $A_{i}$ là tập có ít phần tử nhất nên nó không chứa bất kỳ tập nào trong các tập còn lại.Vậy điều giả sử (1) sai $\Rightarrow$ đpcm.
$1)$
$a)$ Nếu $k\leqslant \frac{n+1}{2}$ :
+ Nếu $\bigcap_{H\in H_{k}}P_{H}=\varnothing$, ta có đpcm.
+ Nếu $\bigcap_{H\in H_{k}}P_{H}$ không phải tập rỗng.Gọi $a$ là một phần tử của nó.
$a\in \bigcap_{H\in H_{k}}P_{H}\Rightarrow$ $a\in P_{H},\forall H\in H_{k}$ ($\left | H_{k} \right |=k$) $\Rightarrow$ trong $k$ tập bất kỳ (thuộc $n$ tập $X_{i}$ đã cho) luôn có ít nhất $1$ tập có chứa $a$.
Xét $n$ tập $X_{i}$ đã cho, gọi số tập có chứa $a$ là $C$, số tập không chứa $a$ là $K$, ta có :
$K\leqslant k-1\leqslant \frac{n-1}{2}\Rightarrow C\geqslant \frac{n+1}{2}\geqslant k\Rightarrow \exists Q_{H}$ ($H\in H_{k}$) sao cho $N\in Q_{H}\Rightarrow N\in \bigcup_{H\in H_{k}}Q_{H}$ (đpcm)
$b)$ Nếu $k\geqslant \frac{n+1}{2}$ :
+ Nếu $\bigcup_{H\in H_{k}}Q_{H}=\varnothing$, ta có đpcm.
+ Nếu $\bigcup_{H\in H_{k}}Q_{H}$ không phải tập rỗng.Gọi $a$ là một phần tử của nó.
$a\in \bigcup_{H\in H_{k}}Q_{H}\Rightarrow$ $\exists H\in H_{k}:a\in Q_{H}\Rightarrow$ số tập có chứa $a$ (trong $n$ tập $X_{i}$) là $C\geqslant k\geqslant \frac{n+1}{2}$
$\Rightarrow$ số tập không chứa $a$ là $K\leqslant \frac{n-1}{2}\leqslant k-1$
$\Rightarrow a\in P_{H},\forall P_{H}$ ($H\in H_{k}$) $\Rightarrow a\in \bigcap_{H\in H_{k}}P_{H}$ (đpcm)
Bài viết đã được chỉnh sửa nội dung bởi chanhquocnghiem: 01-08-2014 - 22:09
