Discrete Mathematics: Elementary and Beyond

14.4 Steiner Systems 225

How many inhabitants must a town have to allow a system of clubs that
is a Steiner system? In other words, what conditions do we get forvif
our block design is a Steiner system? We use equations (14.1) and (14.2),
substituting the valuesk= 3 andλ= 1. We get

3 b=vr and 2 r=v− 1 ,

and hence

r=

v− 1

2

(14.6)

and

b=

v(v−1)

6

. (14.7)

The numbersrandvmust be integers, which imposes some conditions on
v. Since the denominator in (14.7) is 6 and that in (14.6) is a divisor of
6, the condition imposed concerns the remainder ofvupon division by 6.
From (14.6) it follows thatvmust be an odd number, so if we divide it by
6, the remainders can be 1, 3, or 5. This means thatvcan be written in
the forms 6j+1, 6j+3, or 6j+ 5, wherejis an integer. Furthermore,v
can not be of the form 6j+ 5, because then by (14.7) we get

b=

(6j+ 5)(6j+4)

6

=6j^2 +9j+3+

1

3

,

which is not an integer.
Sovmust be of the form 6j+ 1 or 6j+ 3. Taking into consideration that
we must havev>k= 3, we see that one can have a Steiner system only
in towns where the number of inhabitants isv=7, 9 , 13 , 15 , 19 , 21 ,...etc.
For these numbers one can construct Steiner systems indeed. In the case
v= 7 we already have seen the Fano plane, and forv= 9, the Tictactoe
plane. The general construction is quite involved, and we don’t describe it
here.

14.4.1Show that for forv= 7, the Fano plane is the only Steiner system. (Of
course, 7 citizens can set up their clubs in many different ways, by “switching
identities.” We can think of 7 chairs, with triples forming the clubs specified. The
citizens can choose chairs in many different ways.)

14.4.2Does the Fisher inequality give any further condition on the number of
elements in a Steiner system?

Representing the clubs.Imagine that in a town ofvpeople, where the
clubs form a Steiner system, people become unhappy about the membership
fees, and they create a committee whose task is to protest these high fees.
The committee needs at least one member from every club. How many
members does this protest committee need to have?