Bà i tổ hợp thi Olympic chuyên KHTN năm 2014

[chunggold]

Cho tập $M=\left \{ 1,2,3,...,9,10 \right \}$ và $A_1,A_2,....,A_n$ là dãy các tập con khác rỗng phân biệt của $M$ sao cho $|A_i\setminus A_j|\leq 3$ với mọi $i\neq j$ ( $i,j\in 1,2,...,n$) . Tìm giá trị lớn nhất của $n$.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[chemthan]

Cho tập $M=\left \{ 1,2,3,...,9,10 \right \}$ và $A_1,A_2,....,A_n$ là dãy các tập con khác rỗng phân biệt của $M$ sao cho $|A_i\setminus A_j|\leq 3$ với mọi $i\neq j$ ( $i,j\in 1,2,...,n$) . Tìm giá trị lớn nhất của $n$.

Mình kiểm tra lại đề thì đúng phải sửa lại là $|A_i\bigcup A_j|$.
Giả sử $f(n, k)$ là một dãy các tập con dài nhất của tập $\{a_1, a_2, ..., a_n\}$ mà 2 tập con bất kì của dãy có giao không quá $k$ phần tử.
Ta thấy rằng dãy các tập con của $f(n, k)$ không chứa $a_n$ sẽ là một dãy các tập con của tập $\{a_1, a_2, ..., a_{n - 1}\}$ và hiển nhiên dãy này không có 2 tập con nào có giao quá $k$ phần tử, nên số các tập con này không vượt quá $|f(n - 1, k)|$. (1)
Mặt khác, dãy các tập con của $f(n, k)$ chứa $a_n$ nhưng khác $\{a_n\}$ sau khi bỏ phần tử này đi sẽ là một dãy các tập con $\{a_1, a_2, ..., a_{n - 1}\}$ và dãy này không có 2 tập con nào có giao quá $k - 1$ phần tử, nên số các tập con này không vượt quá $|f(n - 1, k - 1)|$. (2)
Từ (1) và (2) suy ra: $|f(n, k)| \le |f(n - 1, k)| + |f(n - 1, k - 1)| + 1$.
Từ đây dễ thấy $|f(n, k)| \le C_n^1 + C_n^2 + ... + C_n^k$ và đẳng thức xảy ra khi và chỉ khi $f(n, k)$ là dãy tất cả các tập con khác rỗng có không quá $k$ phần tử.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]