Let $S_1, S_2, \dots , S_m$ be distinct subsets of $\{1, 2, \dots , n\}$ such that $|S_i \cap S_j | = 1$ for all $i \ne j$. Prove that $m \le n$.
I got this problem from the double counting handout ( here).
Progress: Well define $X_i$ as the set of sets which contain $i$ as an element. So note that $X_1+\dots +X_n=|S_1|+|S_2|+\dots+|S_m|$.
Also if $\{S_i\}=\{a_1,\dots,a_k\}$ then we have $(X_{a_1}-1)+(X_{a_2}-1)+\dots+(X_{a_k}-1)=m-1$ as every element $a_j$ is there in $X_{a_j}$ sets including $S_i$. So we get that $X_{a_1}+X_{a_2}+\dots+X_{a_k}-|S_i|=m-1$.
Well, let's write it as $X_{a_1}+X_{a_2}+\dots+X_{a_k}=m-1+ |S_i|$. And now sum, so we get RHS as $m(m-1)+|S_1|+\dots+|S_m|= m(m-1)+X_1+\dots +X_n$. And then $a_i$ appears in $X_{a_i}$ sets. So we have LHS as $(X_1)^2+\dots (X_n)^2$.
So we have $(X_1)^2+\dots (X_n)^2= m(m-1)+X_1+\dots +X_n\implies (X_1)(X_1-1)+\dots (X_n)(X_n-1)= m(m-1)$
Any solutions?
I can't think of any combinatorial proof of this, I doubt that there is a simple one which does not somehow interpret the following argument.
Assume that $|S_i|>1$. If not (say $|S_1|=1$), the family forms a sunflower, $(S_i\setminus S_1)$ partitions $[n]$, and the proposition follows trivially.
Assuming now that $|S_i|>1$, form the incidence matrix of the family and call it $M_{n\times m}$. Clearly for $u\in\{0,1\}^n$ interpreted as a subset $U\subseteq [n]$, $(uM)_i$ counts $|S_i\cap U|$. Then it follows that for $V=M^TM$, $$V_{ij} = |A_i\cap A_j|$$ It is easy to verify that the columns of $V$ are all linearly independent, and so the rank of $V$ is $m$. But since $\mathsf{rank}(V)\leq\mathsf{rank}(M)\leq n$, the proposition follows.