Dinner TripletsDate: 10/23/2000 at 00:09:58 From: Mike Reagan Subject: Combinations A woman plans to invite 15 friends to dinner. For 35 days she wants to have dinner with exactly three friends a day, and she wants to arrange the triplets in such a way that each pair of friends will come only once. Is this arrangement possible? I've tried several combination formulas but cannot hit upon the right reasoning. Date: 10/23/2000 at 07:10:07 From: Doctor Mitteldorf Subject: Re: Combinations Dear Mike, This is closely related to the "tournament scheduling" problem, where you have people to match up in different rounds so that every player plays with every other player exactly once - or, if that is not possible, minimize the number of times that each player duplicates a pairing. To my knowledge, this is as much an art as a science, and your approach of trying different combinations is probably the best you can do. For small numbers like 15 friends and 35 days, you might write a computer program to automate the search for a good schedule. I'm leaving your question up on the board so that other Math Doctors who might be able to be more helpful can add their comments. - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/ Date: 10/23/2000 at 13:03:40 From: Doctor Anthony Subject: Re: Combinations It is indeed possible. This is an example of a Steiner Triple system associated with Balanced Incomplete Block Design. The background theory is rather convoluted (like many problems in combinatorics) but suffice it to say that if v is the number of varieties (15 in your example) then the number of blocks (days in your example) which allows different triples with no pairs together in the same triple is given by b = v(v-1)/6 = 15 x 14/6 = 35 So 35 days is just sufficient. If we label the friends 0 - 14 (use 0 rather than 1 as the first in the list in this type of work) then the triples are as follows: (0,1,2) (0,3,4) (0,5,6) (0,7,8) (3,7,11) (1,7,9) (1,8,10) (1,11,13) (4,9,14) (2,12,13) (2,11,14) (2,4,5) (5,10,12) (5,8,14) (3,9,13) (3,10,14) (6,8,13) (6,10,11) (4,7,12) (6,9,12) (0,9,10) (0,11,12) (0,13,14) (1,12,14) (1,3,5) (1,4,6) (2,3,6) (2,8,9) (2,7,10) (4,8,11) (4,10,13) (3,8,12) (5,7,13) (6,7,14) (5,9,11) - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/