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

[AnnieSally]

Tập hợp $X$ có $2^n$ phần tử được chia thành các tập con đôi một không giao nhau. Xét quy tắc chuyển phần tử như sau: nếu $A,B$ là các tập con của $X$ và số phần tử của $A$ không nhỏ hơn số phần tử của $B$ thì ta được phép chuyển từ tập $A$ vào tập $B$ số phần tử bằng số phần tử của $B$. Chứng minh rằng sau một số hữu hạn các bước chuyển ta nhận được tập $X$.

[chanhquocnghiem]

Gọi $M$ là tập hợp các tập con ban đầu.

Ta chia $M$ thành $2$ tập : Tập $P=\{x | x\mod 2=0, x\in M \}$ và tập $Q=\{x | x\mod 2=1, x\in M \}$

Gọi số phần tử của $Q$ là $q$.

Dễ thấy là $q$ chẵn.

1)Nếu $q=0$ ta có các tập của $M$ đều có số phần tử là bội của 2.

2)Nếu $q=2k>0$ ta chọn 2 tập bất kỳ thuộc $Q$ và thực hiện phép chuyển.

$\quad$ a)Nếu 2 tập đó có số phần tử bằng nhau thì chúng sẽ hợp thành 1 tập có số phần tử là bội của 2

$\quad$ b)Nếu 2 tập đó có số phần tử là $2m+1$ và $2n+1;\; (m>n)$ thì sau phép chuyển ta có 2 tập có số p tử là $2(m-n)$ và $4n+2$ đều là bội của 2.

Như vậy sau $k$ phép chuyển $(k ge 0)$, ta nhận được các tập con có số phần tử đều là bội của 2.

Gọi $M_1$ là tập các tập con đó.

Ta lại chia $M_1$ thành 2 tập : Tập $P_1$ gồm các tập con có số p tử là bội của $2^2$; tập $Q_1$ gồm các tập con có số p tử là bội của $2^2$ cộng thêm 2.

Gọi $q_1$ là số p tử của $Q_1$.

Dễ thấy là $q_1$ chẵn. Giả sử $q_1=2k_1$.Ta chọn 2 tập bất kỳ thuộc $Q_1$ và thực hiện phép chuyển.

$\quad$ a)Nếu 2 tập đó có số p tử bằng nhau thì chúng sẽ hợp thành 1 tập có số p tử là bội của $2^2$.

$\quad$ b)Nếu 2 tập đó có số p tử là $4m_1 + 2$ và $4n_1 + 2$ thì sau phép chuyển ta có 2 tập có số p tử là $4(m_1-n_1)$ và $8n_1 + 4$ đều là bội của $2^2$. Vậy sau $k_1$ phép chuyển ta nhận đc các tập con có số p tử đều là bội của $2^2$.

Gọi $M_2$ là tập các tập con đó.

Tiếp tục chia $M_2$ thành 2 tập $P_2$ và $Q_2$, ...

Cứ làm mãi như thế, đến một lúc nào đó ta nhận đc các tập con có số p tử đều là bội của $2^{n-1}$. Dễ thấy rằng khi đó ta có đúng 2 tập con như thế, mỗi tập đều có đúng $2^{n-1}$ p tử. Thực hiện phép chuyển cuối cùng ta được tập $X$.

 

(Muốn viết các công thức dưới dạng LATEX nhưng sao khung soạn thảo ko hiện ra, bức xúc quá !)

Bài viết đã được chỉnh sửa nội dung bởi hxthanh: 20-10-2013 - 22:26
Đã sửa $\LaTeX$ hộ anh.