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

[Le Binh Minh]

Cho tập $ S=\begin{Bmatrix} 1,2,3,...,2n \end{Bmatrix} $. Một tập con A của S được gọi là tập cân nếu trong tập đó, số các số chẵn và số các số lẻ bằng nhau. Tập rỗng được coi là tập cân. Gọi $X$ là tập hợp tất cả các tập cân của $S$ và $Y$ là họ tất cả các tập con của $S$ có đúng $n$ phần tử

Hãy thiết lập một song ánh từ $X$ vào $Y$

[nhungvienkimcuong]

Với mỗi tập hợp $M$, kí hiệu $\mathcal{P}(M)$ là họ tất cả tập con của $M$ (như vậy $|\mathcal{P}(M)|=2^{|M|}$).

 

Với mỗi tập con $A$ của $X$, ta phân hoạch $A=C\cup L$, trong đó $C$ gồm các phần tử chẳn và $L$ gồm các phần tử lẻ.

Với tập hợp $C$, ta thiết lập ánh xạ $\mathcal{P}\Big(\{2,4,\dots,2n-2,2n\}\Big)\to \mathcal{P}\Big(\{1,2,\dots,n\}\Big)$ như sau

\[C=\{c_1,c_2,\dots,c_k\}\longmapsto \underbrace{\{2,4,\dots,2n-2,2n\}\setminus\{c_1,c_2,\dots,c_k\}}_{\{d_1,d_2,\dots,d_{n-k}\}}\longmapsto \left \{ \frac{d_1}{2},\frac{d_2}{2},\dots,\frac{d_{n-k}}{2} \right \}.\]

Còn đối với tập $L$, ta thiết lập ánh xạ $\mathcal{P}\Big(\{1,3,\dots,2n-3,2n-1\}\Big)\to \mathcal{P}\Big(\{n+1,n+2,\dots,2n\}\Big)$ như sau

\[L=\{l_1,l_2,\dots,l_k\}\longmapsto \left \{ \frac{l_1+1}{2}+n,\frac{l_2+1}{2}+n,\dots,\frac{l_{k}+1}{2}+n \right \}.\]

Như vậy ta đã xây dựng một ánh xạ $X\to Y$ với

\[A=\{c_1,c_2,\dots,c_k,l_1,l_2,\dots,l_k\}\longmapsto \left \{ \frac{d_1}{2},\frac{d_2}{2},\dots,\frac{d_{n-k}}{2}, \frac{l_1+1}{2}+n,\frac{l_2+1}{2}+n,\dots,\frac{l_{k}+1}{2}+n \right \}.\]

Để chứng minh đây là một song ánh thì chỉ cần chứng tỏ mỗi bước thiết lập là song ánh, hoặc chứng tỏ $|X|=|Y|$ tương đương với

\[\sum_{k=0}^n\binom{n}{k}^2=\binom{2n}{n}.\]

 

 

Ghi chú. Một số bài xây dựng song ánh có thể kể đến GGTH 2017, Ấn Độ 2013 hoặc ở đây.

Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 30-09-2023 - 06:53

[Konstante]

Từ mỗi tập cân $A$, tạo một tập $B$ bằng cách giữ nguyên các số lẻ của $A$, bỏ đi các số chẵn của $A$, và thêm vào các số chẵn không thuộc $A$. Ví dụ khi $S = \{1,2,3,4,5,6\}$, với $A = \{ 1,3,4,6 \}$ thì $B = \{1,3,2\}$.

 

Dễ thấy là $B$ sẽ có đúng $n$ phần tử. Mặt khác từ một tập $B$ có $n$ phần tử, cũng có thể xây dựng lại tâp cân $A$ ban đầu theo cách như trên (tức là giữ nguyên các số lẻ của $B$, bỏ đi các số chẵn của $B$, và thêm vào các số chẵn không thuộc $B$).

 

Do vậy cách xây dựng trên tạo ra một song ánh từ $X \to Y$.

Bài viết đã được chỉnh sửa nội dung bởi Konstante: 01-10-2023 - 19:58