Cho tập hợp $S=\{1;2;3;\dots ;2025;2026\}$.

a) Có bao nhiêu tập con khác rỗng của $S$ thỏa mãn tổng các phần tử của tập con đó chia hết cho 4.

b) Xét $n$ $(n\in \mathbb{N},n\ge 2)$ tập hợp con $S_1,S_2,\dots ,S_n$ của $S$ thỏa mãn đồng thời các điều kiện sau:

1. $S_i\ne \varnothing$ với $i=1,2,\dots ,n$.

2. $\left|S_i\setminus S_j\right|\ne 0,\forall i\ne j,1\le i,j\le n$.

3. $\left|S_i\right|\ne \left|S_j\right|,\forall i\ne j,1\le i,j\le n$.

Tìm giá trị lớn nhất của $n$ (kí hiệu $|S|$ là số phần tử của tập hợp $S$).

Lời giải (nguồn: CLB Toán Lim - LIM Olympic):

(1) Với mỗi tập con $T\subset \{3,4,\dots ,2026\}$, xét bốn tập $T$, $T\cup \{1\}$, $T\cup \{2\}$ và $T\cup \{1,2\}$.
Giả sử tổng các phần tử của $T$ có số dư là $r$ khi chia cho 4. Khi đó tổng các phần tử của bốn tập trên lần lượt có số dư $r,r+1,r+2,r+3$ (mod 4).
Do đó trong bốn tập trên có đúng một tập có tổng các phần tử chia hết cho 4.
Khi $T$ chạy qua tất cả các tập con của $\{3,4,\dots ,2026\}$, các nhóm gồm bốn tập trên tạo thành một phân hoạch của tập hợp tất cả các tập con của $S$. Có $2^{2024}$ cách chọn $T$, nên có đúng $2^{2024}$ tập con của $S$ có tổng các phần tử chia hết cho 4 (kể cả tập rỗng).
Giờ trừ đi tập rỗng (có tổng bằng 0) ta được số tập con cần tìm là $2^{2024}-1$.

(2) Điều kiện $|S_i\setminus S_j|\ne 0$ với mọi $i\ne j$ tương đương với $S_i\not\subset S_j$ với mọi $i\ne j$.
Như vậy các tập $S_1,S_2,\dots ,S_n$ đôi một không chứa nhau.
Trước hết ta chứng minh $n\le 2024$.
Để ý với $n\ge 2$ thì ta không thể có $S_i=S$, do đó $1\le |S_i|\le 2025$ với mọi $i$.
Vì các $|S_i|$ đôi một khác nhau nên trước hết ta có $n\le 2025$.
Giả sử $n=2025$. Khi đó các số $|S_i|$ phải nhận đủ các giá trị $1,2,\dots ,2025$.
Gọi $A,B,C$ là 3 tập $S_i$ bên trên thỏa mãn $|A|=1$, $|B|=2025$, $|C|=2$. Viết $A=\{a\}$.
Do $A\not\subset B$ nên $a\notin B$. Mà $|B|=2025$, suy ra $B=S\setminus \{a\}$.
Mặt khác, từ $A\not\subset C$ ta cũng có $a\notin C$. Vì thế $C\subset S\setminus \{a\}=B$, mâu thuẫn với điều kiện $C\not\subset B$.
Vậy $n\le 2024$. Giờ ta sẽ chứng minh giá trị $n=2024$ đạt được.
Ta chứng minh bằng quy nạp rằng với mọi số chẵn $m\ge 4$, tồn tại một họ ${\mathcal{F}}_m$ gồm $m-2$ tập con của $\{1,2,\dots ,m\}$ sao cho các tập đôi một không chứa nhau và có kích thước lần lượt là $1,2,\dots ,m-2$.
Với $m=4$, lấy ${\mathcal{F}}_4=\{\{1\},\{2,3\}\}$. Rõ ràng họ này thỏa mãn yêu cầu.
Giả sử đã xây dựng được ${\mathcal{F}}_m$. Xét họ
$${\mathcal{F}}_{m+2}=\{A\cup \{m+1\}:A\in {\mathcal{F}}_m\}\cup \{[m],\{m+2\}\},$$
trong đó $[m]=\{1,2,\dots ,m\}$.
Các tập $A\cup \{m+1\}$ có kích thước lần lượt là $2,3,\dots ,m-1$, còn $\{m+2\}$ có kích thước $1$ và $[m]$ có kích thước $m$. Vậy ${\mathcal{F}}_{m+2}$ có đúng một tập ở mỗi kích thước $1,2,\dots ,m$.
Hai tập dạng $A\cup \{m+1\}$ đôi một không chứa nhau vì các tập $A$ ban đầu đôi một không chứa nhau. Mỗi tập $A\cup \{m+1\}$ chứa phần tử $m+1$, trong khi $[m]$ không chứa $m+1$, nên $A\cup \{m+1\}\not\subset [m]$. Ngược lại, $|A\cup \{m+1\}|\le m-1<m=|[m]|$, nên $[m]\not\subset A\cup \{m+1\}$.
Cuối cùng, $\{m+2\}$ không chứa trong bất kì tập nào còn lại vì các tập đó không chứa $m+2$; đồng thời các tập còn lại đều có ít nhất hai phần tử nên không thể chứa trong $\{m+2\}$.
Vậy ${\mathcal{F}}_{m+2}$ cũng thỏa mãn yêu cầu.
Lấy $m=2026$, ta thu được 2024 tập con của $S$ thỏa mãn tất cả các điều kiện của bài toán.
Do đó $n_{\max }=2024$