Combinations of Prisoners

Date: 09/02/97 at 16:10:04
From: Sara
Subject: Combinations

Nine prisoners are taken for their daily exercise handcuffed together 
in threes. How would the warden arrange the men each day so that no 
two men are handcuffed together more than once over a six-day period?
I have tried out different combinations, but each time I get to day 
six there are always two prisoners next to each other again.

Date: 09/10/97 at 12:00:29
From: Doctor Rob
Subject: Re: Combinations

This turns out to be surprisingly hard. 

A combinatorialist friend of mine, Art Drisko, tells me that there is 
a solution which can be constructed from the Steiner triple system on 
nine points and the affine plane of nine points. He supplied this 
example:

         Day 1   Day 2   Day 3   Day 4   Day 5   Day 6
Link 1:  7 0 3   1 3 6   0 6 4   4 0 2   5 1 0   3 2 1
Link 2:  8 1 4   2 4 7   1 7 5   7 3 5   8 4 3   6 5 4
Link 3:  6 2 5   0 5 8   2 8 3   1 6 8   2 7 6   0 8 7

Here the prisoners are numbered from 0 through 8. (If you prefer
numbering them from 1 to 9, replace every 0 with a 9 in the above
diagram.) On each day there are three links of three prisoners, with
the end two prisoners each handcuffed to the middle prisoner, but not 
to each other.

The middle prisoners of each link on each day form a set of six
threesomes with each prisoner appearing exactly twice. Furthermore, no
pair of prisoners can be centers together on two different days. This
is a subset of the Steiner triple system on nine points.

This solution is not unique.  For example, one could permute the 
numbers of the prisoners arbitrarily, and get another such 
arrangement.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/