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