Question 112
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 \lt 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}$.
$$|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}$.