Associated Topics || Dr. Math Home || Search Dr. Math

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/
```
Associated Topics:
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