Delving Into The Concepts

Combinatorial Designs.

These three problems are all special cases of the following mathematical concept:

A combinatorial design consists of a set (whose elements are called points), together with a collection of subsets (called blocks), 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.

A 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).

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.

Combinatorial Designs Are Geometries.

In plane geometry, every two points determine a line. In a combinatorial design, every two points determine a block (there's exactly one block containing both of them). In fact, the points and blocks of a combinatorial design satisfy many of the same axioms that the points and lines in a plane do. That's why a combinatorial design is really a kind of abstract geometry (but a very different sort from Euclidean geometry, having only finitely many points instead of infinitely many!). Hence the geometric name "the Fano plane" for the 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.

Resolvable Combinatorial Designs.

The Schoolgirls' Walk Problem is a combinatorial design in which the points are the girls and the blocks are the lines. There are twelve lines in total (three on each of the four days). However, there's an extra feature in this problem: the lines are grouped into three lines per day, and every girl has to be in exactly one of these three lines.

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:

A resolvable combinatorial design is 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.

Resolvable 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.

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:

$(SWITCH TO TEXT-ONLY VERSION)$

Go backward to Three Problems
Go up to Introduction and Contents
Go forward to Kirkman's Schoolgirl Problem
$(SWITCH TO TEXT-ONLY VERSION)$ Switch to text-only version (no graphics)
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