222 14. Finite Geometries, Codes,Latin Squares,and Other Pretty Creatures
(k=v,b=r=λ= 1). This is so uninteresting that we exclude it from
further consideration and don’t call it a block design.
Parameters of block designs.Are there any relations among the num-
bersb, v, r, k, λ? One equation can be derived from the following. Suppose
that every club gives a membership card to every one of its members; how
many membership cards do they need? There arebclubs and every club
haskmembers, so altogether there arebkmembership cards. On the other
hand, the town hasvinhabitants and everybody hasrmembership cards,
so counting this way we getvrmembership cards. In counting the number
of membership cards two ways we have to get the same number, so we get
bk=vr. (14.1)Let us find another relation. Imagine that the clubs want to strengthen the
friendship among their members, so they require that every member should
have a dinner one-on-one with each of his/her fellow club members in the
clubhouse. How many dinners will a citizenCeat? We can count this in
the following two ways:
First reasoning: There arev−1 other citizens in the town, and each
of them is inλclubs jointly withC, so with every one of the otherv− 1
citizens,Cwill have to eatλdinners in the different clubhouses. This means
altogetherλ(v−1) dinners.
Second reasoning:Cis a member inrclubs. Every club hask−1 further
members, so in every clubCis a member of,Chas to eatk−1 dinners.
Altogether this meansr(k−1) dinners.
The result of the two counts must be equal:
λ(v−1) =r(k−1). (14.2)14.3.1If a town has 924 clubs, each club has 21 members, and any 2 persons
belong to exactly 2 clubs jointly, then how many inhabitants does the town have?
How many clubs does each person belong to? (Don’t be surprised: This is a very
small town, and everybody belongs to many clubs!)
14.3.2Show that the assumption that every person is in the same number of
clubs is superfluous: It follows from the other assumptions we made about the
clubs.
It follows that among the numbersb, v, r, k, λwe can specify at most
three freely, and the other two are already determined by the relations
(14.1) and (14.2). In fact, we cannot arbitrarily specify even three. Is it
possible, for instance, that in a town of 500 people all the clubs have 11
members, and everybody belongs to 7 clubs? The answer is no; please don’t
read on, but try to prove it yourself (it is not too hard).