Odd club problem.

A famous linear algebra puzzle: In a town with $n$ inhabitants, there are $N$ clubs. Each club has an odd number of members, and for any two distinct clubs there is an even number of common members. Prove that $n\ge N$.

Solution: Enumerate the inhabitants by $1,\ldots,n$, as well as the clubs by $1,\ldots,N$. Let $v_1,\ldots,v_N\in\mathbb{Z}_2^n$ be the `club vectors' where for each club one puts a $1$ in the $j$-th entry if $j$ is a member, and $0$ for non-members. We claim that $v_1,\ldots,v_N$ are linearly independent. Thus assume $$(\ast)\ \ \ a_1 v_1+a_2 v_2\ldots +a_N v_N=0,$$ with scalars $a_1,\ldots,a_N\in \mathbb{Z}_2$. For fixed $j$, the dot product $v_i\cdot v_j$ equals the number modulo 2 of common members of clubs $i$ and $j$. It is thus $1$ if $i=j$, and $0$ if $i\neq j$. Hence, taking the dot product of both sides of $(\ast)$ with $v_j$ we obtain $$ a_j=0$$ as required. This shows $v_1,\ldots,v_N$ are linearly independent. Since $\dim(\mathbb{Z}_2^n)=n$, it follows that $N\le n$.

Note: In this solution, we use the dot product of vectors in $F^n$, defined similar to the dot product in $\mathbb{R}^n$: If $u,v$ are vectors with components $$ u=(x_1,\ldots,x_n),\ \ v=(y_1\ldots,y_n)$$ then $$ u\cdot v=x_1y_1+\ldots+x_n y_n.$$