NZ-NZMO 2023 Problem 7

Let $n,m$ be positive integers. Let $A_{1},A_{2},A_{3},\ldots ,A_{m}$ be sets such that $A_{i}\subseteq \{1,2,3,\ldots ,n\}$ and $|A_{i}| = 3$ for all $i$ (i.e. $A_{i}$ consists of three different positive integers each at most $n$ ). Suppose for all $i< j$ we have

$$|A_{i}\cap A_{j}|\leqslant 1$$

(i.e. $A_{i}$ and $A_{j}$ have at most one element in common).

(a) Prove that $m\leqslant \frac{n(n - 1)}{6}$ .

(b) Show that for all $n\geq 3$ it is possible to have $m\geqslant \frac{(n - 1)(n - 2)}{6}$ .