Let $n$ be a positive integer. What is the maximum number of triples from $[n] :=\{1,2,\ldots,n\}$ one can pick so that no two elements $a$ and $b$ appear both in more than one triple?
So far, I have $\frac{n(n-1)}{6}$ as an upper bound and $\frac{n(n-3)}{6}$ as a lower bound.
For the upper bound, there are $\frac{n(n-1)}{2}$ pairs of elements whilst each triple contains three pairs (and no pair appears more than once overall).
For the lower bound, the triples $(x,y,z)$ with $x+y+z$ divisible by $n$ satisfy the condition -- and when counting, for $x$ there are $n$ choices, for $y$ there are at least $n-3$ and then $z$ is fixed (and we divide by $3!$ because of permutations).
Any help appreciated!
This is OEIS sequence A001839.
The formula is $$\left\lfloor\frac n3\left\lfloor\frac{n-1}2\right\rfloor\right\rfloor\ \ \ \ \ \ \ \ \ \text{ if }n\not\equiv5\pmod6,$$ $$\ \ \left\lfloor\frac n3\left\lfloor\frac{n-1}2\right\rfloor\right\rfloor-1\ \ \ \ \text{ if }n\equiv5\pmod6.$$
When $n\equiv1\pmod6$ or $n\equiv3\pmod6$ the maximum families are Steiner triple systems and in that case $$\left\lfloor\frac n3\left\lfloor\frac{n-1}2\right\rfloor\right\rfloor=\frac{n(n-1)}6=\frac{\binom n2}3.$$