Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}}
share|improve this question
    
Have a look at combinatorial designs. –  Boris Bukh Feb 23 '10 at 17:37
    
Thanks, we already tried to "find" our problem in nassrat.cs.dal.ca/ddb2 but the property of splitting in 3 groups of 6 seemed to be an extra condition not considered there. I have tried to understand the specifications of the DESIGN package (designtheory.org/software/gap_design/htm/CHAP002.htm), there is something there about "resolvable" block designs, which seems to fit. –  David Sevilla Feb 23 '10 at 17:52
    
Yes, you want a resolvable block design with t=2, v=18, k=6, lambda=5 (and b=51, and r=17). The database you mention returns 582 designs with these parameters, but I don't know which ones if any are resolvable. I would be surprised if none of them were resolvable. –  Douglas Zare Feb 23 '10 at 19:24
    
The version with 9 players, 3 alleys and groups of 3 is pretty easy to solve by hand :). I found one possible solution: {(123)(456)(789)},{(168)(249)(357)},{(147)(258)(369)},{(159)(267)(348)},{(167)(2‌​58)(349)},{(138)(279)(456)},{(159)(236)(478)},{(124)(357)(689)} but of course this is much easier. I just used properties of the symmetric group. –  B. Bischof Feb 23 '10 at 20:28
    
For 2-(9,3,1), there is a resolution of the affine plane over the field with 3 elements by the slopes of the lines. Is there a relation between that and your 2-(9,3,2) design? –  Douglas Zare Feb 23 '10 at 20:36

2 Answers 2

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

share|improve this answer
    
Thanks. In the article (bottom of p. 326) it is said that there exists a (18,6,5) code by applying a result in R. C. Mullin, Resolvable designs and geometroids, Utilitas Math. 5 (1974), 137-149 (mathscinet link: ams.org/mathscinet-getitem?mr=0345841), unfortunately I could not access the article in order to try to construct a solution. But yes, it seems that one exists. How does this fit with the negative result in my database search? Is it possible that the definitions used are not exactly the same? –  David Sevilla Feb 26 '10 at 11:36
    
I doubt the definitions differ. It's not easy to determine whether a design is resolvable, so perhaps an example is in there, but "resolvable=false" might mean that it's not known to the database whether the design is resolvable. It could be that the database is incomplete and doesn't contain a resolvable design. –  Douglas Zare Feb 26 '10 at 12:36
    
True. I expected that the database containes all the designs, and testing resolubility seems at first glance something quick for these particular parameters. But yes, I would rather test the article than the database. I will continue searching. –  David Sevilla Mar 1 '10 at 8:48

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

share|improve this answer
    
I think the most natural search would be for a partition of {0,...,16,infinity) into three parts so that the action of the cyclic group of order 17 fixing infinity would give you the rest of the days. Further, I would not be surprised if the sets not containing infinity could be chosen to be multiples of each other. That gives you a search space of size about 10^5, with an easy test for whether a choice works by looking at whether the 40 unsigned differences are evenly split among {+-1,...,+-8}. –  Douglas Zare Feb 24 '10 at 22:16
    
That would be a smaller search. Even stitching together two partitions above does not seem to go quickly. I am trying the subexercise myself (mentioned in the post) without computer and that part looks very brute-force like. –  Gerhard Paseman Feb 25 '10 at 18:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.