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

[phong than]

Chứng minh rằng với mọi $2^{n-2}+1$ tập con phân biệt của tập $(1,2,. . .,n)$ luôn tồn tại 4 tập mà hợp của chúng chứa nhiều hơn $n-2$ phần tử.

[Mashimaru]

Giả sử ngược lại, ta xét các tập con $A_1,A_2,...,A_k$ của $S=\{1,2,...,n\}$ sao cho $|A_i_1\cap A_i_2 \cap A_i_3 \cap A_i_4| \leq n-2$ với mọi $1\leq i_1 < i_2 < i_3 < i_4 \leq k$. Ta sẽ chứng minh rằng $k\leq 2^{n-2}$.
Thật vậy, ta gọi một tập hợp $H\subset S$ là đẹp nếu tồn tại $i,j$ sao cho $1 \leq i \leq j \leq k$ và $H \subset A_i\cup A_j$. Bây giờ xét $H$ là tập con đẹp của $S$ có số phần tử ít nhất. Thế thì phải tồn tại $i,j$ sao cho $1\leq i < j \leq k$ và $H=A_i\cup A_j - \{m\}$ với $m\in S$ nào đó.
Xét $H^* = \{H\cap A_i | 1\leq i \leq k\}$. Ta sẽ chứng minh rằng với mọi tập hợp $H'\subset H$, nếu $H'\in H^*$ thì $H-H'\not \in H^*$. Thật vậy, giả sử ngược lại, thế thì tồn tại $i,j$ sao cho $H'=H\cap A_i$, $H - H' = H\cap A_j$, do đó $H=(H\cap A_i)\cup(H\cap A_j)\subset A_i\cup A_j$, mâu thuẫn với định nghĩa của $H$. Mặt khác, $H$ có $2^{|H|}$ tập con nên $|H^*|\leq 2^{|H|-1}$.
Lại xét tập hợp $T=S - H$ và đặt $T^* = \{T\cap A_i | i=1,2,...,k\}$. Ta cũng sẽ chứng minh điều tương tự với $T^*$. Thật vậy, giả sử tồn tại $T'\subset T$ sao cho $T',T-T'\in T^*$. Ta có $T'=T\cap A_k$ và $T - T' = T\cap A_l$, nên $T\subset(A_k \cup A_l)$, suy ra $|A_k \cup A_l|\geq |T|$. Mặt khác dựa vào nhận xét ở phần đầu: tồn tại $i,j$ sao cho $1\leq i < j \leq k$ và $H=A_i\cup A_j - \{m\}$ với $m\in S$ nào đó, ta thu được: $|A_k \cup A_l \cup A_i \cup A_j|\geq |T|+(|H|-1) = |T|+(n-|T|-1)\geq n-1>n-2$, mâu thuẫn. Vậy với mọi tập $T'\subset T$ thì $T'$ và $T - T'$ không cùng thuộc $T^*$, hơn nữa $T$ có $2^{|T|}$ tập con nên $|T^*|\leq 2^{|T|-1}$.
Mặt khác, mỗi tập $A_i$ được xác định một cách duy nhất bởi phần giao của nó với $T$ và $H$ cho nên $k \leq |T^*|\cdot |H^*| \leq 2^{|T|+|H|-2} = 2^{n-2}$, kết thúc chứng minh!

Ở chỗ ấy bây giờ thế nào rồi? Thời gian đang khoác chiếc áo thu lên từng khoảng trời Thành phố Hồ Chí Minh, khiến nỗi nhớ ấy cứ đau đáu trong lòng tớ hơn bao giờ hết. Tớ nhớ ấy thật nhiều, người xa xôi ạ!

Bài viết đã được chỉnh sửa nội dung bởi Mashimaru: 18-08-2009 - 23:31

[tanlsth]

Nhìn quen quen, IRAN năm nào đó thì phải .

[Mashimaru]

Nhìn quen quen, IRAN năm nào đó thì phải .

Đề thi đội dự tuyển trường em ạ

[tanlsth]

Cũng là đề TST IRAN luôn đấy . Anh nhớ ngày xưa có làm rồi