Associate to each set $A_i\subseteq[n]$ its <characteristic vector of a set> $v_i\in\mathbb F_2^n$. The hypotheses say
$$
v_i\mathbin\cdot v_i=1,
\qquad
v_i\mathbin\cdot v_j=0\quad(i\ne j).
$$
If $\sum_i c_iv_i=0$, taking the <inner product>[dot product] with $v_j$ gives $c_j=0$. Thus the vectors are <linearly independent vectors>[linearly independent], so $m\leq\dim\mathbb F_2^n=n$. Equality is attained by the $n$ singleton sets.

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 109 / 1 / i / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-109/1/i/solution