Combinations of PrisonersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/