Drexel dragonThe Math ForumDonate to 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 
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

[Privacy Policy] [Terms of Use]

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

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/