- Answers to Exercises 281
is (( 111
11
)
111
)
=
(
473239787751081
11
)
> 101448.
One could not check so many possibilities even with the fastest computer
within the lifetime of the universe! Lam, Thiel, and Swiercz had to work
in a much more sophisticated manner.
14.3 Block Designs
14.3.1. 441, 44.
14.3.2. For any two citizensCandD, there areλclubs containing both.
If we add this up for everyD, we count (v−1)λclubs containingC. Each
such club is countedk−1 times (once for every member different fromC,
so the number of clubs containingCis (v−1)λ/k. This is the same for
every citizenC.
14.3.3. (a)v=6,r=3,k= 3 givesb= 6 by (14.1), butλ=6/5by
(14.2). (b)b=8,v= 16,r=3,k=6,λ= 1 (there are many other
examples in both cases).
14.3.4. Takeb=vclubs, and construct for every citizenCa club in which
everybody else is a member exceptC. Thenb=v,k=v−1,r=v−1,
λ=v−2.
14.4 Steiner Systems
14.4.1. LetA, B, Cbe 3 elements that do not form a club. There is a
unique club containingAandB, which has a unique third element; call
thisD. Similarly, there is a unique elementEsuch thatACEis a club,
and a unique elementFsuch thatBCFis a club. The elementsD, E, F
must be distinct, since if (say)D=E, thenAandDare contained in two
clubs (one withBand one withC). Let the seventh element beG. There
is a unique club containingCandD, and the third member of this club
must beG(we can check that any of the other 4 choices would yield two
clubs with two members is common). Similarly,AF GandBEGare clubs.
Similarly, there is a unique club containingDandE, whose third member
must beF. So, apart from the names of the citizens, the club structure is
uniquely determined.
14.4.2. We haver=(v−1)/2 by (14.2), and henceb=v(v−1)/6by
(14.1). Sincev− 1 ≥6, we haveb≥v.
14.4.3. Call a triple contained inSanS-triple. The total number of triples
isb=v(v−1)/6, the number ofS-triples is
b′=v− 1
2(v− 1
2 −^1)
6
=
(v−1)(v−3)
24