Bài tổ hợp thi Olympic chuyên KHTN năm 2014 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$. |
Trích:
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ử. |
Múi giờ GMT. Hiện tại là 02:56 AM. |
Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.