Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Dinner Triplets


Date: 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/   
    
Associated Topics:
College Discrete Math
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/