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

[Lesfeuillesmortes]

$n\in \mathbb{N}, n\geq 2$. Chứng minh rằng trong mọi họ gồm ít nhất $2^{n-1}+1$ tập con không rỗng của tập ${1,2,3,...,n}$ đều tìm được $3$ tập hợp mà $1$ trong chúng là hợp của $2$ tập kia.

[JUV]

Chứng minh quy nạp: Bài toán hiển nhiên đúng với $n=2$, giả sử bài toán đúng với $n=k$, xét $n=k+1$ và $2^k+1$ tập con trong tập $\left \{ 1;2;...;k+1 \right \}$ được chọn. Gọi $A$ là tập các tập con được chọn mà không chứa $k+1$, $B$ là tập các tập con chứa $k+1$. Vì $\left | A \right |+\left | B \right |=2^k+1$ nên $1$ trong $2$ tập $A$ và $B$ chứa ít nhất $2^{k-1}+1$ phần tử. Nếu là tập $A$ thì tồn tại $3$ tập con $M$, $N$, $P$ thuộc $A$ mà $M=N\cup P$ theo nguyên lí quy nạp (do $A$ là tập con của tập các tập con của $\left \{ 1;2;...;k \right \}$). Nếu tập $B$ chứa ít nhất $2^{k-1}+1$ phần tử thì bỏ $k+1$ trong mỗi phần tử của $B$ ,gọi tập các phần tử của $B$ mà bỏ đi $k+1$ là $C$ .Lập luận tương tự ta tìm được $3$ tập $M$,$N$,$P$ của $C$ thỏa mãn $M=N\cup P$, nên $M\cup \left \{ k+1 \right \}=(N\cup\left \{ k+1 \right \})\cup(P\cup \left \{ k+1 \right \})$.Vậy tồn tại $3$ tập của $B$ mà tập này bằng hợp $2$ tập còn lại. Vì vậy trong mọi trường hợp, ta có dpcm

Bài viết đã được chỉnh sửa nội dung bởi JUV: 13-09-2016 - 12:41

[nhungvienkimcuong]

$n\in \mathbb{N}, n\geq 2$. Chứng minh rằng trong mọi họ gồm ít nhất $2^{n-1}+1$ tập con không rỗng của tập ${1,2,3,...,n}$ đều tìm được $3$ tập hợp mà $1$ trong chúng là hợp của $2$ tập kia.

lời giải sau đây là ý tưởng dẫn đến $2^{n-1}+1$