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

  1. 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 NN = {1, 2, ..., N}. Let there be M of them: A1, A2, ..., AM. If, as usual, |X| denotes the numer of elements in a finite set X, then the problem tells us that |Ak| is odd and |Ak∩Am| is even for all 1 ≤ k, m ≤ M, k ≠ m.

Let Fk denote the characteristic function of set Ak: Fk(x) = 1 if x∈ Ak and Fk(x) = 0, otherwise. We'll look at Fk 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 Z2 of two elements 0 and 1. Define in this space the scalar product:

  (x1, x2, ..., xN) · (y1, y2, ..., yN) = ∑ xkyk (mod 2),

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

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

Fk = Fm1 + ... + Fmt ,

ms ≠ k. Multiply this by Fk:

1 = Fk·Fk = Fm1·Fk + ... + Fmt·Fk = 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.

|Contact| |Front page| |Contents| |Algebra| |Up|

Copyright © 1996-2018 Alexander Bogomolny

71493897