March 1997 Presentation Topic (continued)

AA combinatorial design has four important numbers attached to it: v, the number of points; b, the number of blocks; k, the size of each block; and r, the number of blocks each point occurs in (this happens to be the same number for each point).combinatorial designconsists ofa set(whose elements are calledpoints), together with a collection ofsubsets(calledblocks), such that each block contains the same number of points, and, for each pair of points, there is exactly one block containing both of them.

**Question 1**. Why must it be true that each point occurs in
the same number of blocks?

Any solution to the Farmer's Wheat Problem is a combinatorial design: the points are the varieties of wheat and the blocks are the fields. All solutions have v=7 (seven varieties of wheat). The 1-field solution the farmer rejected has b=1, k=7, and r=1 (1 field, 7 varieties in each, and each variety occurs in 1 field). The overly expensive 21-field solution has b=21, k=2, and r=6 (21 fields, 2 varieties in each, and each variety occurs in 6 fields). It is up to you to find the values of b, k, and r for the Fano plane solution.

Why are there no other solutions? One reason is that not all combinations of numbers (v,b,k,r) are possible in a combinatorial design.

**Question 2**. Find two conditions that the numbers v, b, k
and r have to satisfy, and infer from them that b and r can be
completely determined from v and k.
Also show that because of this there can't be any other solution to the
Farmer's Wheat Problem.

In Euclidean plane geometry there is the important concept of
*parallel lines*. This has no analogous counterpart in the Fano
plane, but it does in the combinatorial designs associated to our
other two examples.

A similar feature is present in the Tournament Scheduling Problem. It is a combinatorial design in which the points are the teams and the blocks are the games. The blocks are grouped into the first day's games, the second day's games, etc. We are asking for each team to play in exactly one of each day's games.

These are each examples of the following concept:

AResolvable combinatorial designs are geometries that do have a counterpart to the "parallel line" concept of Euclidean geometry: blocks in the same group can be thought of as "parallel". The different groups can be thought of as different "slopes". Given any point p and any group, there is exactly one block in that group which contains p. This corresponds to the property in Euclidean geometry that, given any point p and slope m, there is exactly one line of slope m which contains p.resolvable combinatorial designis a combinatorial design in which the blocks can be arranged into groups in such a way that each point occurs exactly once in each group.

Not all combinatorial designs are resolvable. For one thing, there's an extra condition that v and k have to satisfy in a resolvable combinatorial design.

**Question 3**. Find the extra condition that v and k
have to satisfy in a resolvable combinatorial design.

Neither the Fano plane nor the 21-field solution to the Farmer's Wheat Problem satisfies this condition, so neither is resolvable.

Even when v, b, k, and r satisfy all the necessary conditions, there's no guarantee that that there exists a resolvable combinatorial design (or any combinatorial design at all) which has those values.

**Question 4**. Referring back to the Schoolgirls' Walk Problem,
suppose that three more girls come to the school. The necessary condition
of question 3 is still satisfied. Can we now find a similar schedule
for a series of
walks? Why or why not? (Note that the number of walks need no longer
be four, but we still require that on each walk the girls go out in lines of three,
and that every girl has every other girl exactly once as a linemate.)

**Question 5**. What if 4 more girls come instead of 3?

**Question 6**. More generally, what is the smallest number of new girls
that would have to come to the school in order for a similar schedule of
walks to be possible in the sense of satisfying all the necessary conditions?
Does such a schedule actually exist, and can you find it?

We close with an example of a problem in which all the necessary conditions are satisfied, and it turns out that a resolvable combinatorial design does exist, but finding it is a challenge.

Navigation Panel:

Go backward to Three Problems

Go up to Introduction and Contents

Go forward to Kirkman's Schoolgirl Problem

Switch to graphical version (better pictures & formulas)

Access printed version in PostScript format (requires PostScript printer)

Go to SIMMER Home Page

Go to The Fields Institute Home Page

Go to University of Toronto Mathematics Network Home Page