Problem about subsets of $\{1, 2,\dots,n\}$

Solution 1:

This is a well known type of problem in combinatorics. (Try googling "exact intersections".) The (slight) generalisation of your claim, in which we require $|A\cap B|=\ell>0$ whenever $A\neq B$, is apparently due to Fisher.

Let $\mathcal{A}$ be a family of subsets of $\{1,2,\dots,n\}$ such that for every two distinct $A,B\in\mathcal{A}$ we have $|A\cap B|=\ell$. We claim $|\mathcal{A}|\leq n$. Certainly we're done if some $A\in\mathcal{A}$ has size $\ell$ (this is where we use $\ell>0$), so assume otherwise.

For each $A\in\mathcal{A}$ consider the "indicator vector" $1_A\in\mathbf{R}^n$ given by $1_A(x)=1$ if $x\in A$ and $0$ otherwise. I claim that $\{1_A : A\in\mathcal{A}\}$ is a linearly independent set, so $|\mathcal{A}|\leq n$.

Suppose $\lambda_A\in\mathbf{R}$ are some coefficients such that

$$\sum_{A\in\mathcal{A}} \lambda_A 1_A = 0.$$

Taking the scalar product with $1_B$, noting $1_A\cdot 1_B = \ell$ when $A\neq B$, we have

$$\lambda_B |B| + \sum_{A\neq B} \lambda_A \ell = 0.$$

Rearranging slightly,

$$\lambda_B (|B| - \ell) = - \ell\sum_{A\in\mathcal{A}} \lambda_A.$$

Conclusion: either $\sum\lambda_A = 0$, in which case every $\lambda_B=0$ (since $|B|>\ell$ for all $B\in\mathcal{A}$), or $\sum\lambda_A\neq 0$, in which case all $\lambda_B$ are nonzero and opposite in sign to $\sum\lambda_A$, impossible.

Solution 2:

Hint: For a set of length $i > 2$, no other set can have any subset of that set $i \ge 2$ as a subset.