|
|
|
Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé ! * Quy định về việc viết bài trong diễn đàn MathScope * Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây |
| Ðiều Chỉnh | Xếp Bài |
03-05-2015, 10:26 AM | #1 |
+Thành Viên+ Tham gia ngày: Mar 2015 Đến từ: Hà Nội Bài gởi: 16 Thanks: 4 Thanked 6 Times in 2 Posts | 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$. |
08-05-2015, 09:06 PM | #2 | |
Administrator Tham gia ngày: Mar 2009 Bài gởi: 349 Thanks: 0 Thanked 308 Times in 161 Posts | 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ử. thay đổi nội dung bởi: chemthan, 08-05-2015 lúc 09:18 PM | |
Bookmarks |
Ðiều Chỉnh | |
Xếp Bài | |
|
|