Is there a tournament schedule for 18 players, 17 rounds in groups of 6, which is balanced in pairs?

Question

We are interested in a solution to the following scheduling problem, or any information about how to find it or its existence. This one comes from real life, so you will not only be helping a mathematician quench his thirst of knowledge!

We have 18 players playing a certain sport (let's say curling) on 3 different alleys (6 players per alley) at the same time. They play 17 games and we want that every combination of 2 players play exactly 5 times together.

(As Douglas Zare points out in a comment below, this is known as a resolvable block design with t=2, v=18, k=6, lambda=5 (and b=51, and r=17)).

We asked around and someone came up with a near solution: almost every pair playing 5 times except for a few 6's and 4's. Brute force seemed too slow so we tried with a genetic algorithm, to no avail (being complete beginners in this, we could not even get close to the near-solution that we had, so we do not draw conclusions from our experiments).

I found the near-solution in my old files, in case anyone wants to tinker a bit.

{{1, 2, 3, 4, 5, 6}, {7, 8, 9, 10, 11, 12}, {13, 14, 15, 16, 17, 18}},
{{1, 6, 10, 12, 14, 16}, {2, 3, 8, 11, 15, 17}, {4, 5, 7, 9, 13, 18}},
{{1, 5, 7, 8, 15, 16}, {2, 4, 10, 11, 13, 14}, {3, 6, 9, 12, 17, 18}},
{{1, 4, 8, 9, 14, 17}, {2, 6, 7, 10, 15, 18}, {3, 5, 11, 12, 13, 16}},
{{1, 6, 8, 11, 13, 18}, {2, 4, 9, 12, 15, 16}, {3, 5, 7, 10, 14, 17}},
{{1, 2, 7, 12, 13, 17}, {3, 4, 8, 10, 16, 18}, {5, 6, 9, 11, 14, 15}},
{{1, 3, 9, 10, 13, 15}, {2, 5, 8, 12, 14, 18}, {4, 6, 7, 11, 16, 17}},
{{1, 5, 10, 11, 17, 18}, {2, 6, 8, 9, 13, 16}, {3, 4, 7, 12, 14, 15}},
{{1, 2, 9, 11, 16, 18}, {3, 6, 7, 8, 13, 14}, {4, 5, 10, 12, 15, 17}},
{{1, 4, 8, 12, 15, 18}, {2, 3, 7, 9, 11, 14}, {5, 6, 10, 13, 16, 17}},
{{1, 3, 7, 14, 16, 18}, {2, 5, 8, 9, 10, 17}, {4, 6, 11, 12, 13, 15}},
{{1, 5, 6, 9, 12, 14}, {2, 3, 10, 13, 15, 18}, {4, 7, 8, 11, 16, 17}},
{{1, 3, 10, 11, 12, 16}, {2, 4, 5, 8, 13, 14}, {6, 7, 9, 15, 17, 18}},
{{1, 2, 3, 4, 6, 17}, {5, 7, 11, 12, 13, 18}, {8, 9, 10, 14, 15, 16}},
{{1, 4, 7, 9, 10, 13}, {2, 12, 14, 16, 17, 18}, {3, 5, 6, 8, 11, 15}},
{{1, 2, 5, 7, 15, 16}, {3, 8, 9, 12, 13, 17}, {4, 6, 10, 11, 14, 18}},
{{1, 11, 13, 14, 15, 17}, {2, 6, 7, 8, 10, 12}, {3, 4, 5, 9, 16, 18}}

Answer 1

A collection of $6$-tuples on 18 points with the property that each pair is covered $5$ times is a balanced incomplete block design with $(v,k,\lambda) = (18,6,5)$ and $t=2$. The condition that you can schedule the matches to occur simultaneously in $17$ rounds is that the design is resolvable.

This article claims to construct resolvable block designs with parameters including $(18,6,5)$.

Answer 2

Others have posted that a resolvable block design will help answer the question. If you want to chew up some computer cycles, consider the following approach.

There are 122 ways to divide a set of 6 elements into at most 3 sets. Consider how a solution to your problem looks on the first 6 elements: each of the 17 sessions produces a division of the 6 set in one of the 122 ways. If the first session has 6 individuals together, then each of the remaining sessions produces one of the 122 partitions mentioned above. Because of the restriction that each pair occurs in exactly five of the sessions, in the remaining 16 sessions, you will have no more than four instances of the same partition. (If you do an analysis similar to one below based on pairs, you will find that at most one more instance of the trivial partition will be allowed.)

Now generate a list of combinations of partitions that can occur while keeping the restriction on pairs. This involves choosing 16 items from a multiset of (at most) 488 partitions, many of which will be imadmissible because of the pair restriction.

If we look at how many pairs are made by a partition, we have the trivial partition making 15 pairs, 6 others making 10 pairs, 15 others making 7 pairs, 25 others making 6 pairs, on down to 15 making 3 pairs. Since you want 60 pairs from the remaining 16 partitions, it will happen that you will need at least 4 partitions which make 3 pairs, at most 3 partitions which make 7 or more pairs, and at most 4 partitions which will make 6 or more pairs. So of the 16 items chosen from the above multiset, at most 4 will come from a multiset of at most 204 elements, at least 4 will come from a multiset of 60 elements, and the remainder will still have some restrictions on it. The idea is that a simple algorithm can check a partial combination and quickly weed it out, so that your search space is much smaller than (488 choose 16) items.

An exhaustive list of all such combinations of 16 partitions may be small, or it may be large; for the next step, I recommend starting with a not too large sublist: Pick 3 candidates from the sublist and see if they can be "stitched" together. As an example, suppose I choose a combination of 16 partitions, one of those which is the trivial partition. Then in order to stitch a solution together, I need another combination which has a partition with at most two parts, because I can't use a combination in which all 16 items have 3 or more parts.

As you attempt a stitching, you can see which attempts violate the condition of producing more than 5 pairs among the twelve or 18 elements used for the stitching. As a subexercise, consider the combination consisting of the trivial partition followed by each of the 15 partitions of 6 elements into 2 element sets. See if you can stitch 3 copies of that combination together.

Gerhard "Ask Me About System Design" Paseman, 2010.02.23