Cho tập $S=\{1,2,...,2025\}$ và $A_1,A_2,...,A_k$ là các tập con của $S$ sao cho với mọi $1\le i<j\le k$ có đúng một trong các tập $A_i\cap A_j,A_i^{\prime }\cap A_j,A_i\cap A_j^{\prime },A_i^{\prime }\cap A_j^{\prime }$ là tập rỗng. Tìm giá trị lớn nhất có thể có của $k$.
(Với $A\subset S$, ký hiệu $A^{\prime }$ là phần bù của tập $A$ trong tập $S$).

Lời giải (Bài toán 0.4, LMF - Chuyên Lam Sơn - Thanh Hóa - P4):
Tổng quát bài toán với $2025=n$, để ý các $2n-3$ tập con sau đây thỏa mãn:
$$\{1\},\{2\},\dots ,\{n\},\{1,2\},\{1,2,3\},\dots ,\{1,2,3,\dots ,n-2\}.$$
Do đó $k\ge 2n-3$. Ta sẽ chứng minh rằng $k=2n-3$ là giá trị lớn nhất của $k$ thỏa mãn yêu cầu đề bài.
Với $n=2$, rõ ràng $k\le 1$. Với $n=3$, dễ thấy $k\le 3$.
Giả sử giá trị lớn nhất của $k$ là $2n-5$ với mọi $n-1\ge 3$.
Gọi $M=\{A_1,A_2,\dots ,A_k\}$ là một họ các tập con cực đại thoả mãn yêu cầu bài toán.
Rõ ràng $k\ge 2n-3$ theo ví dụ ban đầu.
Lưu ý rằng tập rỗng và tập $S$ đều không thuộc $M$.
Nếu trong $M$ không có cả $\{i\}$ lẫn $\{i{\}}^{\prime }$ với $1\le i\le n$, ta có thể thêm một trong hai tập đó vào và làm lớn hơn họ $M$. Rõ ràng cả $\{i\}$ và $\{i{\}}^{\prime }$ không thể đồng thời thuộc $M$, do đó chỉ một trong hai tập $\{i\}$ hoặc $\{i{\}}^{\prime }$ thuộc $M$ với mọi $1\le i\le n$.
Xét $X\in M$, ta có thể thay $X$ bởi $X^{\prime }$. Do đó ta có thể giả sử rằng
$$|A_i|\le \frac{n}{2},\forall 1\le i\le n.$$
Bây giờ ta chọn một tập $A\in M$ sao cho $|A|\ge 2$ và
$$|A|\le |B|,\forall B\in M\text{ với }|B|\ge 2.$$
Vì $2n-3>n$, do đó theo nguyên lí Dirichlet thì luôn tồn tại ít nhất một tập như vậy. Không mất tính tổng quát, ta có thể giả sử $1,2$ thuộc tập $A$.
Xét tập $B\in M$ bất kỳ khác $\{1\}$, $\{2\}$ và $A$. Ta có các trường hợp sau:
- Nếu $A\cap B=\varnothing$, khi đó $1,2\notin B$.
- Nếu $A\cap B^{\prime }=\varnothing$ thì $A\subset B$, do đó $1,2\in B$.
- Nếu $A^{\prime }\cap B=\varnothing$ thì $B\subset A$ và do đó $|B|=1$, mâu thuẫn với giả thiết $|B|\ge 2$. Vậy $1,2\notin B$.
- Nếu $A^{\prime }\cap B^{\prime }=\varnothing$, thì $A\cup B=M$.
Với $n$ lẻ, ta có $|A|,|B|\le \frac{n-1}{2}$ và do đó $|A\cup B|\le n-1$.
Với $n$ chẵn, trường hợp duy nhất là $|A|=|B|=\frac{n}{2}$ nhưng khi đó $B=A^{\prime }$ và $A\cap B=\varnothing$.
Vì vậy $\{1,2\}\subset B$ hoặc $\{1,2\}\cap B=\varnothing$ với mọi $B\in M$ khác $\{1\}$, $\{2\}$ và $A$.
Do đó bằng cách bỏ $\{1\}$ và $\{2\}$ ra khỏi $M$ rồi gộp $1,2$ thành một phần tử duy nhất, ta thu được một họ cực đại các tập con ứng với trường hợp $n-1$.
Theo giả thiết quy nạp ta có $k-2\le 2n-5$ và đồng thời $k\ge 2n-3$.
Từ đó $k_{\max }=2n-3$ nên giá trị lớn nhất của $k$ thỏa mãn yêu cầu đề bài là $4047$.