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

[shinichikudo201]

Cho tập $X$ có $n$ phần tử phân biệt, hai tập $A_{1}; A_{2}$ là hai tập con bất kì của $X$. Ta tính số phần tử của $A_{1}\cap A_{2}$, chứng minh tổng tất cả các số nhận được bằng $n.4^{n-1}$

P/s: Bạn nào có tài liệu gì hay về dạng này cho mình tham khảo nhé. Thanks.

Bài viết đã được chỉnh sửa nội dung bởi ducvipdh12: 09-07-2015 - 18:56

[Zaraki]

Cho tập $X$ có $n$ phần tử phân biệt, hai tập $A_{1}; A_{2}$ là hai tập con bất kì của $X$. Ta tính số phần tử của $A_{1}\cap A_{2}$, chứng minh tổng tất cả các số nhận được bằng $n.4^{n-1}$

P/s: Bạn nào có tài liệu gì hay về dạng này cho mình tham khảo nhé. Thanks.

Hình như công thức bạn đưa không đúng thì phải ?

Ví dụ $X= \{ 1,2 \}$ có tập con $A_1=\{1 \}, A_2= \{ 2 \},A_3= \{1,2 \}$ và $|A_1 \cap A_2|=0,|A_2 \cap A_3|=1,|A_3 \cap A_1|=1$. Khi đó tổng sẽ là $2 \ne n \cdot 4^{n-1}=2 \cdot 4^1=8$.

 

Ý bạn tính số phần tử của $A_1 \cap A_2$ là như thế nào vậy ?

Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 09-07-2015 - 19:30

[Bui Ba Anh]

Cho tập $X$ có $n$ phần tử phân biệt, hai tập $A_{1}; A_{2}$ là hai tập con bất kì của $X$. Ta tính số phần tử của $A_{1}\cap A_{2}$, chứng minh tổng tất cả các số nhận được bằng $n.4^{n-1}$

P/s: Bạn nào có tài liệu gì hay về dạng này cho mình tham khảo nhé. Thanks.

Hình như công thức cuối sai thì phải.

Giải: Xét một số $n_0$ nào đó trong tập $X$, thì số tập con của tập $X$ có chứa $n_0$ là $2^{n-1}$. Sở dĩ có điều này là vì chỉ cần thêm một tập con của tập $n-1$ phần tử còn lại, cộng với $n_0$ ta sẽ được một tập con của tập $X$ có chứa $n_0$

Như vây giao của $2$ tập trong $2^{n-1}$ tập tương ứng với số lần ta đếm $n_0$, vậy thì số lần $n_0$ được đếm là $C_{2^{n-1}}^2$

Cho $n_0$ chạy từ $1-n$ ta có số phần tử của tập là $n.C_{2^{n-1}}^2=\frac{n.4^{n-1}-n.2^{n-1}}{2}$

[Belphegor Varia]

Cho tập $X$ có $n$ phần tử phân biệt, hai tập $A_{1}; A_{2}$ là hai tập con bất kì của $X$. Ta tính số phần tử của $A_{1}\cap A_{2}$, chứng minh tổng tất cả các số nhận được bằng $n.4^{n-1}$

P/s: Bạn nào có tài liệu gì hay về dạng này cho mình tham khảo nhé. Thanks.

Lời giải :

Vì $X$ có $n$ phần tử nên nó có $2^n$ tập con. Vì vậy có tất cả $(2^n)^2=4^n$ cặp tập con 

Ta chia tất cả các cặp tập con thành bộ 4 :
Mỗi cặp $(A,B)$ sinh ra bộ bốn : $[(A,B),(\bar{A},B),(\bar{A},B),(\bar{A},\bar{B})]$

Mỗi cặp $(\bar{A},B)$ sinh ra bộ bốn : $[(\bar{A},B),(\bar{\bar{A}},B),(\bar{A},\bar{B}),(\bar{\bar{A}},\bar{B})]=[(A,B),(\bar{A},B),(\bar{A},B),(\bar{A},\bar{B})]$

Mỗi cặp $(A,\bar{B})$ sinh ra bộ bốn : $[(A,\bar{B}),(\bar{A},\bar{B}),(A,\bar{\bar{B}}),(\bar{A},\bar{\bar{B}})]=[(A,B),(\bar{A},B),(\bar{A},B),(\bar{A},\bar{B})]$

Mỗi cặp $(\bar{A},\bar{B})$ sinh ra bộ bốn : $[(\bar{A},\bar{B}),(\bar{\bar{A}},\bar{B}),(\bar{A},\bar{\bar{B}}),(\bar{\bar{A}},\bar{\bar{B}})]=[(A,B),(\bar{A},B),(\bar{A},B),(\bar{A},\bar{B})]$

Tất cả đều trùng nhau, nên mỗi cặp tập con của $X$ chỉ tham gia 1 bộ $4$. Vậy có $4^{n-1}$ bộ bốn khác nhau

Vì mỗi phần tử của $X$ chỉ thuộc $A$ hoặc $\bar{A}$. Vì vậy phần tử đó sẽ thuộc ít nhất $1$ trong $4$ tập hợp $A\cap B , \bar{A}\cap B,A\cap \bar{B},\bar{A}\cap \bar{B}$ $(1)$

Vì vậy số phần tử của tất cả các tập thuộc bố bốn tùy ý ở $(1)$ là $n$

Mà có $4^{n-1}$ bộ bốn khác nhau (cmt) nên sẽ có $4^{n-1}$ bộ bốn $(1)$

Vậy tổng số phần tử của tất cả các tập $A_1\cap A_2$ là $n.4^{n-1}$ $\square$

 

Spoiler

đề bài đúng rồi đó

 

Bài viết đã được chỉnh sửa nội dung bởi Belphegor Varia: 10-07-2015 - 16:42

[Zaraki]

Lời giải :

Vì $X$ có $n$ phần tử nên nó có $2^n$ tập con. Vì vậy có tất cả $(2^n)^2=4^n$ cặp tập con 

Nếu tính $4^n$ cặp tập hợp con tức là đã tính luôn cả cặp tập hợp mà hai tập hợp đó giống nhau.

Mình nghĩ đề bài nói chọn $A_1,A_2$ tập hợp con bất kì của $X$ thì tức là $A_1,A_2$ khác nhau.

Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 10-07-2015 - 09:34

[Belphegor Varia]

Có lẽ là $A_1$ và $A_2$ có thể giống nhau nhưng $\bar{A_1}$ và $A_2$, $A_1$ và $\bar{A_2}$, $\bar{A_1}$ và $\bar{A_2}$ lại khác nhau, nên 1 bộ 4 kiểu như vậy vẫn xét được. 

[Zaraki]

Có lẽ là $A_1$ và $A_2$ có thể giống nhau nhưng $\bar{A_1}$ và $A_2$, $A_1$ và $\bar{A_2}$, $\bar{A_1}$ và $\bar{A_2}$ lại khác nhau, nên 1 bộ 4 kiểu như vậy vẫn xét được. 

Bạn đếm sai $4^n$ cặp tập hơp con nên cũng sẽ dẫn đến việc đếm sai bộ $4$. Nếu $A_1,A_2$ giống nhau thì hai cặp $(\bar{A_1},A_2)$ và $(A_1,\bar{A_2})$ giống nhau, hai cặp $(A_1,A_2)$ và $(\bar{A_1},\bar{A_2})$ có hai tập con trong mỗi cặp giống nhau nên sẽ không được tính. Do đó ở trường hợp này không phải là bộ $4$ cặp mà chỉ là một cặp duy nhất $(\bar{A_1},A_2)$. Như vậy bạn không thể chia $4$ từ $4^n$ xuống $4^{n-1}$ được vì cách đếm bộ 4 không đúng.

 

Số cặp tập hợp con nên là $\binom{2^n}{2}$. Tuy nhiên, nếu bạn đếm đúng số cặp tập hợp con (thoả mãn hai tập trong mỗi cặp khác nhau) thì cách đếm bộ 4 của bạn cũng sẽ có vấn đề. Lấy ví dụ là hai tập $A,B$ khác nhau thoả mãn $A \cup B=X, A \cap B= \varnothing$, ta sẽ có $\bar{A}=B$. Khi đó cặp $(A,B)$ không thể sinh ra 4 bộ vì bộ $(\bar{A},B)$ và $(A,\bar{B})$ sẽ không thuộc $\binom{2^n}{2}$ cặp tập con ta đã chọn.

Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 10-07-2015 - 11:06

[Johan Liebert]

Cách tính như của bạn Belphegor Varia mình nghĩ là đúng

 

Do $A_1;A_2$ được chọn 1 cách riêng lẻ mà. Vì được chọn riêng lẻ nên cặp $(A,B);(B,A)$ là 2 cặp khác nhau

[Belphegor Varia]

Bạn đếm sai $4^n$ cặp tập hơp con nên cũng sẽ dẫn đến việc đếm sai bộ $4$. Nếu $A_1,A_2$ giống nhau thì hai cặp $(\bar{A_1},A_2)$ và $(A_1,\bar{A_2})$ giống nhau, hai cặp $(A_1,A_2)$ và $(\bar{A_1},\bar{A_2})$ có hai tập con trong mỗi cặp giống nhau nên sẽ không được tính. Do đó ở trường hợp này không phải là bộ $4$ cặp mà chỉ là một cặp duy nhất $(\bar{A_1},A_2)$. Như vậy bạn không thể chia $4$ từ $4^n$ xuống $4^{n-1}$ được vì cách đếm bộ 4 không đúng.

 

Tiếp tục bào chữa cho lời giải (căng thẳng quá nhỉ  )

Theo trường hợp bạn nêu 2 cặp $(\bar{A_1},A_2)$ và $(A_1,\bar{A_2})$  là 2 cặp khác nhau nên nó vẫn có thể cùng tồn tại trong 1 bộ bốn 

[Zaraki]

Cách tính như của bạn Belphegor Varia mình nghĩ là đúng

 

Do $A_1;A_2$ được chọn 1 cách riêng lẻ mà. Vì được chọn riêng lẻ nên cặp $(A,B);(B,A)$ là 2 cặp khác nhau

Nghĩ lại thì thấy cách Belphegor Varia đúng nếu ta coi cặp $(A,B)$ và $(B,A)$ là phân biệt. Còn cách Bui Ba Anh đúng nếu ta coi $(A,B)$ và $(B,A)$ là giống nhau. 

[Belphegor Varia]

Hôm nay tình cờ đọc được 1 bài toán có cách phát biểu khác nhưng về bản chất thì tương tự như bài này. Cách giải của bài này là ví dụ điển hình cho phương pháp dùng hàm đặc trưng giải toán Tổ hợp :

$\blacksquare$ Cho tập $E=\left \{ 1,2,...,n \right \}$. $F=P(E)$ (Với $P(E)$ là tập hợp tất cả các tập con của $E$ ). Chứng minh:

                                  $S=\sum_{(A,B)\in F^2}\left | A\cap B \right |=n.4^{n-1}$

 

$\texttt{Solution}$

Từ đáp số cho ta cách tiếp cận khác để chứng minh khẳng định này. Thừa số $n$ ở đáp số cho ta gợi ý đến việc đếm số phần tử. Ta sẽ đếm số lần một phần tử $x$ của $E$ xuất hiện trong các tập hợp $A\cap B$. Cụ thể ta có :

     $S=\sum_{(A,B)\in F^2}\left | A\cap B \right |=\sum_{(A,B)\in F^2}\sum _{x\in E}\chi_{A\cap B}(x)=\sum_{x\in E}\sum_{(A,B)\in F^2}\chi_{A\cap B}(x)$

Với mỗi phần tử $x\in E$ cố định, xét tổng $\sum_{(A,B)\in F^2}\chi_{A\cap B}(x)$ ta thấy $\chi _{A\cap B}(x)=1$ khi và chỉ khi $x\in A\cap B$

Như vậy $\sum_{(A,B)\in F^2}\chi_{A\cap B}(x)=\left | \left \{ (A,B)\in F^2|x\in A\cap B \right \} \right |$, tức là tổng này bằng tổng số bộ $A,B$ sao cho $A\cap B$ chứa $x$. Có tất cả $2^{n-1}$ tập con của $E$ chứa $x$. Do đó theo quy tắc nhân thì số bộ $(A,B)$ để $A\cap B$ chứa $x$ là $(2^{n-1})^2=4^{n-1}$. 

Từ đó $S=\sum_{x\in E}\sum_{(A,B)\in F^2}\chi_{A\cap B}(x)=\sum _{x\in E}4^{n-1}=n.4^{n-1}\square$

Bài viết đã được chỉnh sửa nội dung bởi Belphegor Varia: 17-07-2015 - 21:17