Round Robin Tournament Scheduling
Schedules - You must register to Post and Download => Mathematics => Topic started by: Bill Daly on August 18, 2009, 04:03:06 PM
-
[Part I] (https://www.devenezia.com/round-robin/forum/index.php?topic=278.0)
(https://www.devenezia.com/round-robin/forum/index.php?topic=278.0)
Here is a simple Howell movement written in the form of a CHM:
[r,k] = [2,2]
| Row | Pair 1 | Pair 2 | Pair 3 |
| 1 | 5-0 | 4-1 | 3-2 |
| 2 | 5-1 | 0-2 | 4-3 |
| 3 | 5-2 | 1-3 | 0-4 |
| 4 | 5-3 | 2-4 | 1-0 |
| 5 | 5-4 | 3-0 | 2-1 |
The permutation which generates this matrix is (01234)(5). There are a lot of equivalent patterns generated by symmetry, but I'll leave that aside for now. Here are the salient points:
- The column labeled Pair_1 accounts for all the pairs that involve 5 (I'll use the lexically highest digit to represent the fixed digit, in all cases);
- The 'difference' between the digits in the column labeled Pair_2 is either 2 or 3; assuming that both possible differences are used for each pair modulo 5 (= 2*2+1), in other words, if x-y is a pair, then the corresponding differences are x-y mod 5 and y-x mod 5, then the differences are all the possible pairs with differences 2 and 3;
- Similarly, the differences between the digits in the Pair_3 column represent all the possible pairs with differences 1 and 4.
It follows that every pair appears exactly once in the matrix.
Here is a solution to the Kirkman 15-Schoolgirl Problem written in the form of a CHM:
[r,k] = [2,3]
| Row | Triple_1 | Triple_2 | Triple_3 | Triple_4 | Triple_5 |
| 1 | E-0-1 | 2-4-8 | A-3-D | 6-5-B | C-7-9 |
| 2 | E-2-3 | 4-6-A | C-5-1 | 8-7-D | 0-9-B |
| 3 | E-4-5 | 6-8-C | 0-7-3 | A-9-1 | 2-B-D |
| 4 | E-6-7 | 8-A-0 | 2-9-5 | C-B-3 | 4-D-1 |
| 5 | E-8-9 | A-C-2 | 4-B-7 | 0-D-5 | 6-1-3 |
| 6 | E-A-B | C-0-4 | 6-D-9 | 2-1-7 | 8-3-5 |
| 7 | E-C-D | 0-2-6 | 8-1-B | 4-3-9 | A-5-7 |
The permutation which generates this matrix is (02468AC)(13579BD)(E). I'll refer to the two cycles as the even cycle and the odd cycle.
- All of the pairs of two even digits are generated in the column Triple_2;
- All of the pairs of the fixed symbol E with other symbols are in the column Triple_1;
- There is one pair of odd digits in each of Triple_3, Triple_4 and Triple_5;
- There is one set of even-odd pairs in Triple_1, namely the pairs 2k-(2k+1) for k = 0..6;
- There are two even-odd pairs in each of Triple_3, Triple_4 and Triple_5.
Don't worry too much about verifying that this matrix satisfies the rules (it does). I'm about to change notations, which will make it much easier to study.
I'll leave further analysis of this case to the next post.