Kirkman's Schoolgirls

I find this to be a fascinating problem. Kirkman in 1850 poses this problem:

Fifteen young ladies of a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk abreast more than once.

I find it interesting that he refers to breasts, but that's for another blog. I want to see how to solve this problem.

To solve this problem, I look to elementary binary groups (EBGs). These are groups that are products of copies of Z₂, the group whose elements are {0,1}, and 0 plus any element is that element back again, and 1 + 1 = 0. Let's take products of 0 though 4 of these:

0. Identity. Product of no Z₂s. This is the identity group. Only one element. Not much of interest.

1. Binary. Product of one Z₂; i.e., Z₂ itself. This is the 0-1 group. The subgroups are Z₂ itself and the identity group. This is the group of off and on, back and forth, 0 and 1, something and nothing, and so forth.

2. Klein triples. Product of two Z₂s; i.e., Z₂xZ₂ or Z₂². This is called the Klein 4-group. Suppose its elements are {0, a, b, c}. Then 0 + anything is that something back again. An element plus itself is 0; for example b + b = 0. If you take two non-equal non-zero elements and add them, you get the third one. For example, b + c = a, and a + c = b.

We shall meet this group later, and so I will give it a special name. I shall call the non-zero elements of an instance of this group a Klein triple. So {a, b, c} is such a triple, as is {3, 5, 6} with the operation of (logical) AND. 3 AND 5 = 6, since in binary, if we and 011 and 101, we get 110 (add the components as in Z₂).

3. The Fano Plane. Product of three Z₂s. This is a group of 8 elements, with 7 non-zero elements. How many Z₂xZ₂ subgroups does it have? How many Klein triples does it have? You can select any of 7 elements for the first element. You can't select that one again, but you can select any other for your second element, giving you 6 choices, but then that forces your third element, which is the AND of the first two elements. That's 42 possibilities. But each Klein triple occurs 6 times in this enumeration, so we have only 7 subgroups. Since subgroups isomorphic to Z₂ are essentially the same as elements of order 2, there are 7 of these. So which of these 7 4-element groups contains which of the 2 element groups?

What if you intersect two Klein triples, or Z₂xZ₂s? They have to intersect in a Z₂. This is similar to two planes in 3-space intersecting in a line. So each of seven 3-sets intersect each other in exactly one element. If you try to construct a set of 7 elements like this, you get something like:

123
145
167
246
257
347
356

This is called a Fano Plane. Fano planes have interesting properties. For example, each pair of triples intersects in a single element, and if you name two elements, one and only one triple has both of them. This makes it a magic pattern, similar to magic squares, and some cultures must have worshipped this plane. A Fano Plane is also a (7, 3, 1) design - read a book on combinatorics to find what that is.

4. Kirkman Schoolgirls. Now let's look at Z₂⁴. This has 15 elements of order 2, forming 15 subgroups of order 2. I shall call these elements schoolgirls. Linear algebra tells us that there are then 15 subgroups isomorphic to the Fano group above (Z₂³). How many groups isomorphic to Z₂xZ₂ are there, or what is the same thing, how many Klein triples are in the Kirkman group?

Number the girls 1 through 15. Pick one girl. There are 15 possibilities. Then pick another one. 14 choices. Your choice of the third girl is now forced. You must take the AND of their numbers and find that girl. So there are 14*15 or 210 triples, but each triple occurs 6 times in that total, so there are really only 35 such triples. Here are these triples, arranged in 7 columns to represent the 7 days. Given in this form, these triples solve the Kirkman problem (this arrangement is due to Brown and Mellinger):

RANK/DAY	S	U	N		M	O	N		T	U	E		W	E	D		T	H	U		F	R	I		S	A	T
1	1	2	3		1	4	5		2	4	6		1	6	7		3	4	7		3	5	6		2	5	7
2	4	10	14		2	13	15		1	8	9		2	9	11		2	12	14		2	8	10		1	14	15
3	7	8	15		3	9	10		3	12	15		4	8	12		1	10	11		4	11	15		4	9	13
4	5	9	12		6	8	14		5	11	14		3	13	14		5	8	13		1	12	13		3	8	11
5	6	11	13		7	11	12		7	10	13		5	10	15		6	9	15		7	9	14		6	10	12

The Kirkman Schoolgirls bring up some interesting problems. For example, each day consists of one even-even-even triple and four triples with two odd girls and one even one. If you divide by 2 and take the quotients in one table and the remainders in the other one, you find a lot of structure. In particular, the first table contains clusters of elements from 1 through 7, and if you look through these, you will see the Fano plane in disguise. The Fano plane also appears in the top row of the schedule above.

The most interesting problem is whether there is a solution to the Kirkman Schoolgirls essentially different from this one. Here is an idea that may shed some light on this. Suppose someone hands you a 7-day Kirkman schoolgirl schedule. Let us attempt to form a group of order 16, consisting of these girls and the number 0. I shall define an addition + on these girls like this:

1. 0 + 0 = 0.
2. 0 + any girl = that girl again.
3. Any girl + herself = 0.
4. Compute the sum of two girls as follows. These are two separate girls. By the Kirkman property, there is one and exactly one line in the Kirkman schedule that contains both these girls. The sum of these girls is defined to be the third girl in that line.

It is easy to prove that the sum of two girls is a girl, that 0 is the identity, and each girl is her own inverse. The tricky part is to show that + is associative, that is, for all elements of the group a, b, and c, a + (b + c) = (a + b) + c. If any of a, b, and c are equal to each other or to 0, that is easy to prove. The tricky one is for different non-zero a, b, and c. a + (b + c) means go to the line contain Betty and Carol and find, say Doris in the same line with them, then find the line with Doris and Anne and take the third girl in this line. (a + b) + c means go to the line containing Anne and Betty and find, say Ethyl in their line, then find the line with Ethyl and Carol in it and take the third girl in that.

Are these two third girls the same? If one can prove that is always the case, then 0, the girls and + form an abelian group isomorphic to Z₂⁴. Further, taking the 4-element subgroups of this group gives you back the original Kirkman design. But maybe one can't prove this. Is it possible to find a Kirkman schoolgirl arrangement where this set is not a group? If so, there are at least two distinct solutions to the Kirkman Schoolgirl Problem.