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

Let $A=\{1, 2,\dots,n\}$ What is the maximum possible number of subsets of $A$ with the property that any two of them have exactly one element in common ?

I strongly suspect the answer is $n$, but can't prove it.

-
I think answer should be n but i m not sure – kalpeshmpopat Mar 20 '13 at 15:33
Well, {1}, {1,2}, {1,3}....{1,n} form such a collection of n subsets. The subsets don't have to have the same cardinality. – Cosmonut Mar 20 '13 at 15:35
I would like to point out that most of the answers are missing the case $\{1, 2\}, \{2, 3\}, \{3, 1\}$, so there is an error in their logic. – Calvin Lin Mar 20 '13 at 16:14
@Inceptio No, but as Thomas mentioned, you can for $n = 13$. I.e. the projective plane of order 3. – Calvin Lin Mar 20 '13 at 16:24
@Thomas I've undeleted it. – Thomas Andrews Mar 20 '13 at 21:10

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.

-
Yes, I mean the {scalar,dot,inner,...}-product. – Sean Eberhard Mar 20 '13 at 21:13
Wait, $\lambda_B$ are not all equal, but rather $\lambda_B=\frac{1}{|B|-\ell}C$? If all the $|B|$ are equal, clearly it is true that the $\lambda_B$ are equal, but we can't conclude that here, can we? – Thomas Andrews Mar 20 '13 at 21:15
Ah, thanks, correcting now. – Sean Eberhard Mar 20 '13 at 21:16
What we really know is that they are all the same sign, since $|B|>\ell$, which is enough. – Thomas Andrews Mar 20 '13 at 21:17
nice proof .... – wece Mar 20 '13 at 21:19

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

-