Clubs in a Vector Space

In a town with population N, every club has an odd number of members and any two clubs have an even number of members in common. Prove that the number of clubs is at most N.

Discussion

References

B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006, p. 163

In a town with population N, every club has an odd number of members and any two clubs have an even number of members in common. Prove that the number of clubs is at most N.

First of all observe that there may be N clubs. In the extreme case where every citizen forms a club by himself there are exactly N clubs.

In mathematical terms, we are looking into the odd subsets of N_N = {1, 2, ..., N}. Let there be M of them: A₁, A₂, ..., A_M. If, as usual, |X| denotes the numer of elements in a finite set X, then the problem tells us that |A_k| is odd and |A_k∩A_m| is even for all 1 ≤ k, m ≤ M, k ≠ m.

Let F_k denote the characteristic function of set A_k: F_k(x) = 1 if x∈ A_k and F_k(x) = 0, otherwise. We'll look at F_k as a binary vector of 0s and 1s. Every such vector has an odd number of non-zero components (each equal to 1 of course). All such vectors form a vector space of dimmension N over the field Z₂ of two elements 0 and 1. Define in this space the scalar product:

(x₁, x₂, ..., x_N) · (y₁, y₂, ..., y_N) = ∑ x_ky_k (mod 2),

with 1 ≤ k ≤ N. The conditions of the problem mean that F_k·F_k = 1, while F_k·F_m = 0, k≠m. We'll show that this is only possible for M ≤ N.

First off, vectors F_k are linearly independent: one of them cannot be a sum of any combination of the others. For, assume to the contrary, that

F_k = F_m₁ + ... + F_{m_t} ,

m_s ≠ k. Multiply this by F_k:

1 = F_k·F_k = F_m₁·F_k + ... + F_{m_t}·F_k = 0 + ... + 0 = 0,

a contradiction. Since the space of F's is N-dimensional, there could not be more than N linearly independent vectors. We conclude that M ≤ N.

Something is definitely wrong with our argument which becomes absolutely transparent,transparent,obscure,adamant,synergetic if you observe that number four played no role whatsoever in the argument. Using one instead of four would sound as legitimate. But therein lies a clue. Verifiably, one weighing does not suffice to find a lighter coin from among four. Putting two coins in a cup does not work; while weighing one against one leaves two coins unweighed. Two leftover coins kill all the hope to solve the problem.

49552084

Amazon.com Widgets