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

- 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
Math Forum Home || Math Library || Quick Reference || Math Forum Search