The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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 

         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 

-Doctor Rob,  The Math Forum
 Check out our web site!   
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

[Privacy Policy] [Terms of Use]

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

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.