View Single Post
 ebaines Posts: 10,033, Reputation: 5529 Expert #4 Apr 4, 2012, 12:59 PM
This is a very interesting problem, and I wonder if it's really for homework or perhaps for setting up a bridge tournament or a tennis doubles round robin?

For twenty people A through T this will work - each row represents an event, where 20 people are grouped into 5 sets of 4 each:

ABCD, EFGH, IJKL, MNOP, QRST
AFKP, BGLQ, CHMR, DINS, EJOT
AGNT, BHIO, CJPQ, DEKR, FLMS
AHJS, BKMT, CELN, DFOQ, GIPR
ALOR, BEPS, CFIT, DGJM, HKNQ

Note that there are no repeats in any of the groupings.

The method I used was to start with a matrix like this for the first event, where each row is a group of 4:

$
\text{
\begin{matrix}
A & B & C & D \\
E & F & G & H \\
I & J & K & L \\
M & N & O & P \\
Q & R & S & T \\
\end{matrix} }
$

This is s 5x4 matrix, and we want to make it a square matrix 5 x 5, so add a 5th column noted with letter x:

$
\text{
\begin{matrix}
A & B & C & D & x\\
E & F & G & H & x\\
I & J & K & L & x\\
M & N & O & P & x\\
Q & R & S & T & x\\
\end{matrix} }
$

Now start taking diagonals, starting with A in the upper left and and continuing down to the right. The rule we use is this: whenever you hit an 'x' continue on from the next row, left hand column. So the first diagonal is:

AFKPx

Now take the next diagonal starting with 'B': BGLxQ. Note how the letter after the x is the first letter of the next row,
The next, starting with C: CHxMR
The next, starting with D: DxINS
And the last starting with the x in the first row: xEJOT

If you write all these out as a matrix you get:

$
\text{
\begin{matrix}
A&F&K&P&x\\
B&G&L&x&Q\\
C&H&x&M&R\\
D&x&I&N&S\\
x&E&J&O&T
\end{matrix} }
$

Ignore the x's and this is the groupings for the second event.

For the third event we follow a similar rule using the original matrix, but this time take a more slanted diagonal, where for each row that we move down we jump two letters to the right, using the same rule that when you fall off the right side of the matrix you jump back in on the left. So the first group is: AGxNT. Continuing on, you get the full matrix:

$
\text{
\begin{matrix}
A&G&x&N&T\\
B&H&I&O&x\\
C&x&J&P&Q\\
D&E&K&x&R\\
x&F&L&M&S\\
\end{matrix} }
$

For the fourth event we repeat the process but this time jump 3 columns to the right for each row we move down. You get:

$
\text{
\begin{matrix}
A&H&J&x&S\\
B&x&K&M&T\\
C&E&L&N&x\\
D&F&x&O&Q\\
x&G&I&P&R
\end{matrix} }
$

And finally for the last event we jump 4 columns to the right for each row we move down:

$
\text{
\begin{matrix}
A&x&L&O&R\\
B&E&x&P&S\\
C&F&I&x&T\\
D&G&J&M&x\\
x&H&K&N&Q
\end{matrix} }
$

Now ignore all the x's and you have your 5 events with people in groups of 4 with no repeats.