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á !)
- hxthanh, bangbang1412, AnnieSally và 1 người khác yêu thích