Câu hỏi 57
Cho $n \ge 2$ là một số nguyên dương và $S = \{1, 2, \dots, n\}$.
Với $k = 1, 2, \dots, n-1$, ta gọi hai tập con $k$ phần tử của $S$ là láng giềng nếu chúng có $k-1$ phần tử chung (tức là khác nhau đúng một phần tử). Gọi $f(n,k)$ là số phần tử lớn nhất có thể của một họ các tập con $k$ phần tử của $S$ mà trong đó không có hai tập nào là láng giềng. Chứng minh rằng $f(n,k) \le \binom{n-1}{k-1}$.
Với $k = 1, 2, \dots, n-1$, ta gọi hai tập con $k$ phần tử của $S$ là láng giềng nếu chúng có $k-1$ phần tử chung (tức là khác nhau đúng một phần tử). Gọi $f(n,k)$ là số phần tử lớn nhất có thể của một họ các tập con $k$ phần tử của $S$ mà trong đó không có hai tập nào là láng giềng. Chứng minh rằng $f(n,k) \le \binom{n-1}{k-1}$.