Một ứng dụng bất ngờ của xích và đối xích

Đề bài: 

Cho $n > 1$ là một số tự nhiên. Đặt $U = \{ 1,2,...,n \}$ và $A\Delta B$ là tập hợp tất cả các phần tử của $U$ mà chỉ thuộc về đúng một tập $A$ hoặc $B$.

Chứng minh rằng: $ |\mathcal{F}|\le 2^{n-1} $.

Ở đó $\mathcal{F}$ là họ các tập con của $U$ sao cho bất kì hai tập phân biệt $A,B$ của $\mathcal{F}$, ta luôn có $|A\Delta B |>2$

Lời giải:

Ta giải bài này bằng tư tưởng xích và đối xích

Cho 2 tập hợp con của $U$ là $A$ và $B$. $A$ và $B$ có quan hệ so sánh khi và chỉ khi $\left | A\Delta B \right |\geq 2$

Gọi họ tập con lớn nhất của $U$ sao cho với bất kì hai tập phân biệt $A,$ thì  $\left | A\Delta B \right |\geq 2$ là $K$

Khi đó theo định lí Dilworth, $\left | K \right |$ bằng số phân hoạch nhỏ nhất của các đối xích hợp thành họ các tập hợp con của $U$

Gọi $T$ là số phân hoạch của  các đối xích hợp thành họ các tập hợp con của $U$

Ta sẽ xây dựng một số $T$ sao cho $T=2^{n-1}$

Với $n=2$ thì tồn tại $T$

Giả sử  với $n=k$, tồn tại $T=2^{k-1}$

Xét $n=k+1$

Khi đó có $2^{n-1}$ tập con của $U$ chứa phần tử $n+1$ và nếu ta bỏ phần tử $n+1$ đi, theo giả thiết quy nạp, ta có thể lập thêm $2^{n-1}$ phân hoạch của họ tập hợp con của $U$ chứa $n+1$

Theo nguyên lý quy nạp, suy ra đpcm

Vì $\left | K \right |$ bằng số phân hoạch nhỏ nhất của các đối xích hợp thành họ các tập hợp con của $U$ nên $\left | K \right |\leq 2^{n-1}$

Vậy $\left | \mathcal{F} \right |\leq 2^{n-1}$