How many different groups can coexist under rules that seem almost harmless? Parity conceals a surprisingly rigid limit.
The Incompatible Clubs
Riddle statement
A city has 100 inhabitants, and several clubs have been formed.
Each club has an odd number of members, while any two distinct clubs have an even number of members in common.
What is the greatest possible number of clubs?
Show solution
Solution
Answer: there can be at most 100 clubs.
Represent each club by a vector of 100 zeros and ones: write 1 when a person belongs to the club and 0 when they do not. We work modulo 2, so only parity matters.
The dot product of each vector with itself is 1, because the club has an odd number of members. By contrast, the dot product of two distinct club vectors is 0, because the clubs have an even number of members in common.
Suppose that a nonempty sum of these vectors were the zero vector. Choose one of the vectors in the sum and take the dot product with it. Its product with itself contributes 1, while all the others contribute 0, so the result is 1.
But the dot product of the zero vector with any vector is 0. This contradiction shows that the club vectors are linearly independent.
Since they lie in a vector space of dimension 100, there can be no more than 100 of them.
The bound is attainable: form 100 one-person clubs. Each club has one member, and two distinct clubs have no members in common.
Therefore, the maximum is 100 clubs.