N.T.TUAN wrote: Let $m,n$ be positive integers, and let $F$ be a family of $m$-element subsets of $\{1,2,...,n\}$ satisfying $A\cap B \not = \emptyset$ for all $A,B\in F$. Determine the maximum possible number of elements in $F$. After some calculation I got $C_{n}^{m}\cdot \sum_{i=1}^{m-1}C_{n-m}^{m-i}$. Is this correct?

post your solution, please!

There are $C_{n}^{m}$ ways to choose $m$ elements from $\{1,2,...,n\}$ . Supose that we have chosen $m$ elements for the set $A$, and now we want tho choose $m$ elements for the set $B$ in that way that $card(A\cap B )=i$. Then we need $m-i$ elements completing the set $B$, and these elements we choose from the $n-m$ elements remained in the set $\{1,2,...,n\}$. This can be made in $C_{n-m}^{m-i}$ ways. So therefore $cardF=C_{n}^{m}\cdot \sum_{i=1}^{m-1}C_{n-m}^{m-i}$. Is this ok? Forgive my bad english.

Assuming that $m<n$, the answer is: $\binom{n}{m}$ for $2m>n$, and $\binom{n-1}{m-1}$ for $2m \leq n$. If $2m>n$, then $F$ can simply contain all possible $m$-element subsets of $\{1, 2, ..., n\}$: for any two such $A, B$, since they have $2m$ elements in total and this is more than $n$, they must share some element and thus have non-empty intersection. Then we get $\binom{n}{m}$. If $2m \leq n$, first note that it is trivial to get a family $F$ containing $\binom{n-1}{m-1}$ subsets: let all the subsets contain the element $1$, and then pick $m-1$ numbers from the remaining $n-1$ in all possible ways. Now, is it possible to get more? Note that $\binom{n-1}{m-1}=\frac{m}{n}\binom{n}{m}$. If $n=2m$, it's easy to see why $F$ can't contain more than half of all possible subsets: for any $A$, let $A'$ be the only set such that $A \cap A' = \emptyset$. Then the family of all possible subsets is broken up into pairs, and we can take at most one subset from each pair. If $n=lm$, a similar argument should prove that we can take at most one out of $l$ subsets: partition the family of all possible subsets into disjoint sub-families each containing $l$ disjoint subsets, and the result follows. However, it's not obvious that such a partition exists. We can sidestep that problem: first take a sub-family consisting of some $l$ disjoint subsets which form a partition of $\{1, 2, ..., n\}$. Now, rename the elements $1, 2, ..., n$ in all $n!$ possible ways; for each of these ways we will get a new sub-family with $l$ disjoint subsets. In the resulting huge family, each possible subset $A$ is represented many times, but by symmetry arguments every $A$ is represented the same number of times. Now, given any valid $F$, for each of these sub-families each having $l$ subsets, at most one of them can be in $F$. Since all subsets are equally represented, this means that at most one $l$th of all possible subsets are in $F$. If $n$ is not a multiple of $m$, we would like create a sub-family containing $n$ subsets such that any valid $F$ can contain at most $m$ of them. This is easy: take $\{1, 2, ..., m \}, \{2, 3, ..., m+1 \}, ..., \{n, 1, ..., m-1 \}$. This clearly works. Now, as above, rename the elements $1, 2, ..., n$ in all $n!$ possible ways, etc. Then at most $m$ out of every $n$ possible subsets are in $F$.

Erdos-Ko-Rado theorem!

The following short and elegant proof was given by Katona in 1972 and can be found in Alon's and Spencer's book "The probabilistic method", Chapter 1.

Cute problem