Maths WorkshopMaths problems with full solutions
Exercise 1975Combinatorics › Counting principlesOlympiadAdded 5 Nov 2026

Oddtown

#linear algebra method#parity#set systems#F2

Statement

In a town of nn inhabitants, some clubs are formed (all different) such that every club has an odd number of members and any two different clubs share an even number of members. Prove that there are at most nn clubs. Show that nn clubs are possible.

Hint

Associate to each club its 0/10/1 incidence vector in F2n\mathbb{F}_2^n and prove these vectors are linearly independent over F2\mathbb{F}_2.

Show solutionHide solution

Solution

Idea. The dot product mod 22 of incidence vectors counts the size of the intersection mod 22.

Setup. For clubs A1,…,AmA_1,\dots,A_m let vi∈F2nv_i\in\mathbb{F}_2^n be the incidence vector. Then
vi⋅vj=∣Ai∩Aj∣ mod 2={1i=j,0i≠j.v_i\cdot v_j=|A_i\cap A_j|\bmod2=\begin{cases}1&i=j,\\0&i\ne j.\end{cases}

Independence. Suppose ∑icivi=0\sum_ic_iv_i=0 with ci∈F2c_i\in\mathbb{F}_2. Taking the dot product with vjv_j gives cj=0c_j=0 for all jj. The mm vectors are linearly independent in an nn-dimensional space, hence m≤nm\le n.

Construction. Take the nn clubs {1},{2},…,{n}\{1\},\{2\},\dots,\{n\}.

Remark. In "Eventown" (even sizes, even intersections) the answer is 2⌊n/2⌋2^{\lfloor n/2\rfloor}.

Lesson. Translate set conditions into inner products over F2\mathbb{F}_2 and use dimension counting.