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$.
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$.
#1
Đã gửi 20-10-2013 - 08:26
#2
Đã gửi 20-10-2013 - 19:03
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.
- hxthanh, bangbang1412, AnnieSally và 1 người khác yêu thích
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh