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

[HoaiBao]

Cho $n$ là số tự nhiên lớn hơn 1. Xét tập $S = \begin{Bmatrix}1,2,...,n \end{Bmatrix}$ và $A_i$ là $m$ tập con đôi một khác nhau của $S$ thỏa mãn:

 (1) $|A_i|\geq 2$

 (2) $\forall i<j<k$: Nếu $\left |A_i\bigcap A_j \right |\neq 0 ; \left |A_j\bigcap A_k \right |\neq 0 ; \left |A_k\bigcap A_i \right |\neq 0$ thì $\left |A_i\bigcap A_j\bigcap S_k \right |\neq 0$.

Chứng minh rằng $m\leq 2^{n-1}-1$

Bài viết đã được chỉnh sửa nội dung bởi HoaiBao: 12-12-2016 - 23:02

[JUV]

Ta sẽ quy nạp theo $n$, dễ thấy $n=2$ đúng. Giả sử bài toán đúng với $n=k$. Xét $S= \left \{ 1;2;...;k+1 \right \}$. Xét các cặp $(A;S\setminus A)$ với $A\in S, \left | A \right |\geq 2$, nếu tồn tại $M,N$ trong $m$ tập thuộc cùng $1$ cặp thì xét $A_i$ $\forall i=\overline{1,m}$, luôn tồn tại $B_i\in M$ để $A_i\cap M=B_i$. $\forall T\subset M,T\neq \varnothing,T\neq M$, gọi $d_T$ là số các tập $A_i$ để $A_i\cap M=T$ và $A_i\neq T$. Nếu $\exists A_i,A_j: A_i\cap N=A_j\cap N\neq \varnothing, A_i\cap M=T,A_j\cap M=M\setminus T$ thì $3$ tập $(A_i,A_j,M)$ không thoả mãn đề bài. Vậy $A_i\cap N\neq A_j\cap N$ $\forall A_i,A_j:A_i\cap M=T=M\setminus (A_j\cap M)$ $(A_i\neq T,A_j\neq M\setminus T)$. $N$ có $2^{\left | N \right |}-1$ tập con khác rỗng nên $d_T+d_{M\setminus T}\leq 2^{\left | N \right |}-1$.Với $T= \varnothing$, $d_{\varnothing}\leq 2^{\left | N \right |-1}-1$ theo giả thuyết quy nạp, mặt khác với $A_i,A_j$ chứa $M$ và khác $M$ thì $(A_i\cap N)\cap (A_j\cap N)\neq \varnothing$, nếu không thì $(A_i,A_j,N)$ là $3$ tập không thoả mãn. Từ đó suy ra $d_M\leq 2^{\left | N \right |-1}$, vậy $d_M+d_{\varnothing}\leq 2^{\left | N \right |}-1$. Vậy $d_T+d_{M\setminus T}\leq 2{^\left | N \right |}-1\forall T\subset M$ .Gọi $p$ là số tập con $S$ trong $m$ tập mà là tập con của $M$, vì $\left | M \right |<k+1$ nên theo giả thiết quy nạp thì $p\leq 2^{\left | M \right |-1}-1$. Vậy $m=\frac{\sum_{T\subset M}(d_T+d_{M\setminus T})}{2}+p\leq (2^{\left | N \right |}-1)2^{\left | M \right |-1}+2^{\left | M \right |-1}-1=2^{\left | M \right |+\left | N \right |-1}-1= 2^k-1$. Nếu không tồn tại $M,N$ thuộc cùng $1$ cặp, lúc đó $m\leq 2^{n-1}$. Nếu $m=2^{n-1}$, mỗi cặp chỉ có $1$ tập con được chọn. Dễ thấy tất cả tập con có số phần tử bằng $k$ và $k+1$ được chọn, có thể dễ dàng chứng minh nếu tất cả tập con có $i+1$ phần tử được chọn thì tất cả tập con có $i$ phần tử cũng được chọn với $i>\frac{k}{2}$. Vậy tất cả các tập con có $>\frac{k}{2}$ phần tử đều được chọn, dễ suy ra điều vô lí. Vây $m\leq 2^{n-1}-1$ 

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

[Phan Tien Ngoc]

ta chứng minh bằng quy nạp ,ta thấy n=2 đúng .giả sử đúng tới k $<$ n. Ta xét 

TH1:K tồn tại i ,j  để $Ai\bigcup Aj =S$ $\left | Ai\bigcap Aj \right |=1$.Gọi x là phần tử tùy ý thuộc S .ta thấy số tập Ai k chứa x lớn nhất =$2^{n-2}-1$ ( giả thiết ).Số tập con chứa x là $2^{n-1}$.Nếu x $\in Ai$ thì k tồn tại j để $Aj=(S-Ai)\bigcup {x}$.nếu k thì $\left | Ai\bigcap Aj \right |=1$.Nên một nữa tập con chứa x của S xuất hiện dưới dạng các tập Ai.Nên max $\left | Ai \right |=2^{n-2}-1+2^{n-2}=2^{n-1}-1$

TH2: Tồn tại x thuộc S thõa $A1\bigcup A2=S ,A1\bigcap A2=x$ .đặt $\left | A1 \right |=r+1,\left | A2 \right |=s+1 ,r+s = n-1$ .Ta có max $\left | Ai \right |\subseteq A1 = 2^r-1,\left | Ai \right |\subseteq A2=2^s-1$ .NẾU Ai k phải con A1 ,A2  thì .

$A1\bigcap Ai ,A2\bigcap Ai$  không rỗng  suy ra $A1\bigcap A2\bigcap Ai = x$ .suy ra $Ai={x} \bigcup (Ai-A1)\bigcup (Ai-A2)$ ,DO các tập khác rỗng trên được chọn theo $2^s-1,2^r-1$ nên Max các tập này  $= (2^s-1)(2^r-1)$ suy ra Max $\left | Ai \right |= (2^s-1)(2^r-1)+2^s-1+2^r-1=2^n-1 -1$

Bài viết đã được chỉnh sửa nội dung bởi Phan Tien Ngoc: 15-12-2016 - 00:45