User david sevilla - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T00:36:53Z http://mathoverflow.net/feeds/user/4189 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16178/is-there-a-tournament-schedule-for-18-players-17-rounds-in-groups-of-6-which-is Is there a tournament schedule for 18 players, 17 rounds in groups of 6, which is balanced in pairs? David Sevilla 2010-02-23T17:04:21Z 2010-03-04T07:32:36Z <p>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!</p> <blockquote> <p>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.</p> </blockquote> <p>(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)).</p> <p>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).</p> <p>I found the near-solution in my old files, in case anyone wants to tinker a bit.</p> <pre> {{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}} </pre> http://mathoverflow.net/questions/21/finite-extension-of-fields-with-no-primitive-element/18459#18459 Comment by David Sevilla David Sevilla 2010-11-10T12:34:05Z 2010-11-10T12:34:05Z Well, one needs to prove then that such an a^m+b^m is never a primitive element (unless one takes this for granted given the previous answers, but I don't know if that was the idea). http://mathoverflow.net/questions/16178/is-there-a-tournament-schedule-for-18-players-17-rounds-in-groups-of-6-which-is/16182#16182 Comment by David Sevilla David Sevilla 2010-03-01T08:48:09Z 2010-03-01T08:48:09Z 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. http://mathoverflow.net/questions/16178/is-there-a-tournament-schedule-for-18-players-17-rounds-in-groups-of-6-which-is/16182#16182 Comment by David Sevilla David Sevilla 2010-02-26T11:36:01Z 2010-02-26T11:36:01Z 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: <a href="http://www.ams.org/mathscinet-getitem?mr=0345841" rel="nofollow">ams.org/mathscinet-getitem?mr=0345841</a>), 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? http://mathoverflow.net/questions/16178/is-there-a-tournament-schedule-for-18-players-17-rounds-in-groups-of-6-which-is Comment by David Sevilla David Sevilla 2010-02-25T16:13:20Z 2010-02-25T16:13:20Z @Douglas Zare: sorry to surprise you :) , but I got the results file for that query, and there are no resolvable ones there: it does contain 582 lines that say &quot;resolvable&quot; : false and 0 that say true. http://mathoverflow.net/questions/16178/is-there-a-tournament-schedule-for-18-players-17-rounds-in-groups-of-6-which-is Comment by David Sevilla David Sevilla 2010-02-23T17:52:44Z 2010-02-23T17:52:44Z Thanks, we already tried to &quot;find&quot; our problem in <a href="http://nassrat.cs.dal.ca/ddb2/" rel="nofollow">nassrat.cs.dal.ca/ddb2</a> 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 (<a href="http://designtheory.org/software/gap_design/htm/CHAP002.htm" rel="nofollow">designtheory.org/software/gap_design/htm/&hellip;</a>), there is something there about &quot;resolvable&quot; block designs, which seems to fit.