Question 57
Let $n \ge 2$ be a positive integer and let $S = \{1, 2, \dots, n\}$.
For $k = 1, 2, \dots, n-1$, we call two $k$-element subsets of $S$ neighbours, if they have $k-1$ elements in common (i.e. differ by exactly one element). Let $f(n,k)$ be the size of the largest possible collection of $k$-element subsets of $S$, in which no two subsets are neighbours. Prove that $f(n,k) \le \binom{n-1}{k-1}$.
For $k = 1, 2, \dots, n-1$, we call two $k$-element subsets of $S$ neighbours, if they have $k-1$ elements in common (i.e. differ by exactly one element). Let $f(n,k)$ be the size of the largest possible collection of $k$-element subsets of $S$, in which no two subsets are neighbours. Prove that $f(n,k) \le \binom{n-1}{k-1}$.