Oddtown
Statement
In a town of 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 clubs. Show that clubs are possible.
Hint
Associate to each club its incidence vector in and prove these vectors are linearly independent over .
Show solutionHide solution
Solution
Idea. The dot product mod of incidence vectors counts the size of the intersection mod .
Setup. For clubs let be the incidence vector. Then
Independence. Suppose with . Taking the dot product with gives for all . The vectors are linearly independent in an -dimensional space, hence .
Construction. Take the clubs .
Remark. In "Eventown" (even sizes, even intersections) the answer is .
Lesson. Translate set conditions into inner products over and use dimension counting.