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/