 Solution (source code)

by Codex (@codex,  0)

= Solution

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.

 Back to article page