Prove that at least one of the subsets is at most size $\sqrt{n}+1$ Let $X$ be an $n$-element set, and let $S_1, ..., S_n$ be subsets of $X$ such that $\mid S_i \cap S_j \mid \leq 1$ whenever $1 \leq i < j \leq n$. Prove that at least one of the sets $S_i$ has size at most $\sqrt{n}+1$
I was thinking of taking an approach by contradiction by assuming for every $S_i$ we have $\mid S_i \mid \geq \sqrt{n}+1$.
I know $\mid S_i \cap S_j \mid = \mid S_i \mid + \mid S_j \mid - \mid S_i \cup S_j \mid$. But I have no further idea about how to go about proving the claim. 
 A: Let $Y$ be a random variable uniformly distributed on $X$, and let $N$ be the number of subsets $S_i$ that $Y$ is in. (Using indicator functions, $N=\sum 1_{S_i}$).
Let $f=x^2-x$, a convex function.
Then we know via Jensen's inequality that $$\mathbb E[f(N)]\ge f(\mathbb E[N]).$$
The left hand side of this is just $$\frac1n\left(\sum_{i=1}^n\sum_{j=1}^n|S_i\cap S_j|-\sum_{i=1}^n|S_i|\right).$$ Cancelling the $S_i\cap S_i$ terms with the $S_i$ gives us a trivial upper bound of $\frac1nn(n-1)=n-1$.
On the other hand, if we let $S=\sum_{i=1}^n|S_i|$, then the RHS is equal to $S(S-1)$.
Therefore we know that $n-1\ge S(S-1)$ so $$\frac12+\sqrt{n-1+\frac14}\ge S$$
But the total number of elements across all sets is $Sn$ and there are $n$ sets, so one set has at most $S$ things in it. Thus it remains to show that $$\sqrt{n}+1\ge\sqrt{n-\frac34}+\frac12$$
which is trivial as every term on the left is greater than the corresponding term on the right.
An interesting thing to note is that equality (the minimum size of a set being $\sqrt{n-\frac34}+\frac12$, not your one) is actually attainable, if you make the elements points in a finite projective plane, and sets correspond to lines containing the points they are in. Thus this shows that this bound is in fact tight :)
A: Let $X:=\{1,2,\dots,n\}$ and let's assume that the element $i\in X$ is in $d_i$ subsets of the list $S_1,\dots,S_n$. Then, by  the assumption $\mid S_i \cap S_j \mid \leq 1$ whenever $1 \leq i < j \leq n$, it follows that
$$\frac{1}{n}\binom{n}{2}\geq \frac{1}{n}\sum_{i=1}^n \binom{d_i}{2}\geq 
\binom{\frac{N}{n}}{2}.$$
where
$$N=\sum_{i=1}^nd_i=\sum_{i=1}^n |S_i|.$$
Assume by contradiction that $|S_i|> \sqrt{n}+1$ for all $i$. Then $N>n(\sqrt{n}+1)$ and, by the above inequality, we have
$$\frac{n-1}{2}=\frac{1}{n}\binom{n}{2}\geq 
\binom{\frac{N}{n}}{2}> \frac{1}{2}\left(\frac{N}{n}-1\right)^2>\frac{n}{2}$$
which is a contradiction.
