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.
References
- B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006, p. 163
|Contact| |Front page| |Contents| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny
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
Let F_{k} denote the characteristic function of set A_{k}:
(x_{1}, x_{2}, ..., x_{N}) · (y_{1}, y_{2}, ..., y_{N}) = ∑ x_{k}y_{k} (mod 2), |
with 1 ≤ k ≤ N. The conditions of the problem mean that
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_{m1} + ... + F_{mt} ,
m_{s} ≠ k. Multiply this by F_{k}:
1 = F_{k}·F_{k} = F_{m1}·F_{k} + ... + F_{mt}·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
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.
|Contact| |Front page| |Contents| |Algebra| |Up|
Copyright © 1996-2018 Alexander Bogomolny
72010072