March 1997 Presentation Topic (continued)
7 --- = lines
/|\ *** = circle joining 2, 3, 5.
/***\
3 | 5 Not shown (due to limitations of the text-only
/* 6 *\ medium) are two lines: one from 1 to 5 passing
/ *| * \ through 6, and one from 3 to 4 passing through 6.
1-----2-----4
Here the points represent the varieties; the six line segments and one circle represent the fields. This solution can be interpreted as a geometry (the "lines" of this geometry are the six line segments and one circle). In this geometric interpretation, the "points" stand for varieties of wheat and the "lines" stand for fields. There is an interesting duality to this geometry: you could equally well interpret the "lines" as being the varieties of wheat and the "points" as being the fields, and the same properties are preserved.
We can also list the fields and the varieties planted in each one:
field | first | second | third |
# | variety | variety | variety |
------+---------+---------+---------+
1 | 1 | 2 | 4 |
2 | 2 | 3 | 5 |
3 | 3 | 4 | 6 |
4 | 4 | 5 | 7 |
5 | 5 | 6 | 1 |
6 | 6 | 7 | 2 |
7 | 7 | 1 | 3 |
Note the pattern as you go down the table!
Solution to the Schoolgirls' Walk Problem. The following diagram pictorially represents the answer:
Day 1 Day 2 Day 3 Day 4
+-+ +-+
/ | | \
7-8-9 7 8 9 7 8 9 | | 7 8 9
| | | / / / | | \ \ \
4-5-6 4 5 6 / 4 5 6 | \ 4 5 6 \
| | | | / / / \ \ \ |
1-2-3 1 2 3 | 1 2 3 1 2 3 |
| / \ |
+-+ +--+
The blocks, divided up into the four days of walks, are:
---------------------------------------
| day 1 day 2 day 3 day 4 |
------------------------------------------------
| line 1 | 1 2 3 | 1 4 7 | 1 5 9 | 1 6 8 |
| line 2 | 4 5 6 | 2 5 8 | 2 6 7 | 2 4 9 |
| line 3 | 7 8 9 | 3 6 9 | 3 4 8 | 3 5 7 |
------------------------------------------------
Solution to the Tournament Scheduling Problem. If each of the n teams plays every day, then there must be n/2 games each day (as each game involves two teams). In particular, n/2 must be an integer, so no solution is possible if n is odd.
If n=2 the solution is obvious: there is just one game, taking place on one day. If n=4 the following schedule works:
day 1 day 2 day 3
game 1 A vs. B A vs. C A vs. D
game 2 C vs. D B vs. D B vs. C
For n=6 the following schedule works:
day 1 day 2 day 3 day 4 day 5
game 1 A vs. B A vs. C A vs. D A vs. E A vs. F
game 2 C vs. D B vs. E B vs. F B vs. D B vs. C
game 3 E vs. F D vs. F C vs. E C vs. F D vs. E
Many other schedules are possible as well. No pattern is immediately obvious from the particular schedules we've chosen above. For the n=8 case, let's be more careful to choose a schedule in a manner which exemplifies a clear pattern:
day 1 day 2 day 3 day 4 day 5 day 6 day 7
game 1 A vs. H B vs. H C vs. H D vs. H E vs. H F vs. H G vs. H
game 2 B vs. G C vs. A D vs. B E vs. C F vs. D G vs. E A vs. F
game 3 C vs. F D vs. G E vs. A F vs. B G vs. C A vs. D B vs. E
game 4 D vs. E E vs. F F vs. G G vs. A A vs. B B vs. C C vs. D
Notice the patterns going across the table.
To get a general solution for any even number n=2k of teams: on day one, have team 1 playing team 2k, team 2 playing team 2k-1, team 3 playing team 2k-2, and so on, up through team k playing team k+1. For day two, rotate the teams' positions in the schedule, according to the following rotation: 1->2->3->4->...->2k-1->1, with team 2k staying put. (For example, in the above schedule we replaced A with B, B with C, C with D, D with E, E with F, F with G, and G with A, with H staying put, to get the schedule for day two from the schedule for day one). Similarly, perform another rotation to get the third day's schedule, and so on. It is left to you to verify that this gives a valid schedule in which each team plays every other team exactly once.
Answer to Question 1. Pick a point P. Since there are v-1 other points besides P, there are v-1 pairs which involve P. None of these pairs can occur in more than one block. A block that contains P has k-1 of these pairs in it (since that block contains k-1 points besides P). Therefore, if r is the number of blocks in which P occurs, we must have r(k-1)= v-1, so r=(v-1)/(k-1), proving that r is independent of the point P.
Answer to Question 2. The answer to qustion 1 reveals that one condition is that r=(v-1)/(k-1), which also implies that (v-1)/(k-1) has to be an integer.
The other condition is as follows. There are v(v-1)/2 pairs in total. Each block has k(k-1)/2 pairs in it. Since each pair occurs once and only once we get that
total number of pairs v(v-1)/2 v(v-1)
b = --------------------- = -------- = ------ .
pairs in each block k(k-1)/2 k(k-1)
In particular, it is necessary that v(v-1)/k(k-1) be an integer.
In the Farmer's Wheat Problem, v=7. Since (v-1)/(k-1) must be an integer, that means k-1 must be a factor of 6. Since the only factors of 6 are 1, 2, 3, and 6, this means k must be 2, 3, 4, or 7. The case k=4 is impossible since then v(v-1)/k(k-1) would be 42/12 which is not an integer. This leaves only the cases k=2 (the 21-field solution), k=3 (the Fano plane solution), or k=7 (the plant-everything-in-one-field solution which the farmer rejected).
Answer to Question 3. Since we can find a group of blocks (which have k points each) that together represents every one of the v points exactly once, k must divide v. That means v/k must be an integer (it is the number of blocks per group).
Answer to Question 4. Although v/k = 12/3 = 4 is an integer and v(v-1)/k(k-1) = 132/6 = 22 is an integer, (v-1)/(k-1) = 11/2 is not an integer, so this situation fails one of the necessary conditions. It is therefore not possible to find such a schedule of walks.
Answer to Question 5. v(v-1)/k(k-1) = 156/6 = 26 and (v-1)/(k-1) = 6 are both integers so the necessary conditions for a combinatorial design are met. v/k = 13/3 is not an integer so it cannot be resolvable. A non-resolvable combinatorial design with these parameters has the following blocks. It is divided up into sets for convenience and also hoping that you will notice a pattern (that also occurred in the Fano plane).
set 1 | set 2
-----------------------
1 3 9 | 2 5 6
2 4 10 | 3 6 7
3 5 11 | 4 7 8
4 6 12 | 5 8 9
5 7 13 | 6 9 10
6 8 1 | 7 10 11
7 9 2 | 8 11 12
8 10 3 | 9 12 13
9 11 4 | 10 13 1
10 12 5 | 11 1 2
11 13 6 | 12 2 3
12 1 7 | 13 3 4
13 2 8 | 1 4 5
Answer to Question 6. We know that k has to be 3 and v/k has to be an integer, so v must be a multiple of 3. Also (v-1)/(k-1) must be an integer, so v-1 must be a multiple of 2, so v must be odd. Finally, v(v-1)/k(k-1) must be an integer, so v(v-1) must be a multiple of 6; this condition will automatically be satisfied if v is an odd multiple of 3.
Therefore, the next value of of v for which a schedule of walks might be possible is the next odd multiple of three, namely 15 (which corresponds to six more students coming to the school).
Answer to Question 7. Recall that our blocks are of two types, which we can call Fano blocks (blocks from the Fano plane, consisting of numbers from 1 to 7) and mixed blocks (consisting of a tournament game, which is two numbers from 8 to 15, together with one number from 1 to 7 representing the day on which that game was played).
Any pair of points in which both numbers are 7 or below occurs exactly once among the Fano plane blocks, and never in the mixed blocks. Any pair of points in which both numbers are 8 or above occurs exactly once in the tournament schedule, and hence exactly once in the mixed blocks, and never in the Fano plane blocks. Any pair of points in which one number a is 7 or below and the other number b is 8 or above occurs exactly once in the mixed blocks (because team b plays exactly once on date a), and never in the Fano plane blocks.
Therefore, each pair of points occurs exactly once amongst all the blocks.
Answer to Question 8. Note the vertical structure to the Fano plane. The first block (the first row of the table in the answer to the Farmer's Wheat Problem) consists of the numbers 1, 2, and 4. If we add 1 to each number we get the second row. If we add 1 again we get the third row. If we continue to add 1 each time (except that when we are at the number 7 we go back down to 1 instead of up to 8) we eventually generate all the blocks of the Fano plane.
Similarly, if we take the games from one day of the sports tournament and cycle the teams according to the rotation
8->9->10->11->12->13->14->8(with team 15 remaining fixed), we get the next day's games.
That means that if we take one of our "mixed" blocks of girls (where two of the numbers, call them a and b, are from 8 to 15, representing one of the sports games, and the third number is c is from 1 to 7 representing the day on which the a versus b game was played), and cycle the numbers according to
1->2->3->4->5->6->7->1
8->9->10->11->12->13->14->8(with 15 remaining fixed), a and b transform into a pair of numbers representing a game on day c+1, so the transformed triple is also one of our mixed blocks.
Thus, if we start with any one of our 35 blocks (either one from the Fano plane, or one of the mixed blocks), and keep applying the above rotation, we get a cycle of seven blocks.
All we need to do to solve Kirkman's schoolgirl problem is to find a schedule of five blocks which works for day 1, making sure none of these five blocks are in the same cycle. Then, to get the schedule for the second day, simply apply the above rotation to the first day's schedule, and so on for each of the seven days.
The final solution is shown below.
| line 1 | line 2 | line 3 | line 4 | line 5
------+---------+---------+---------+---------+--------
day 1 | 1 2 4 | 3 8 12 | 5 11 13 | 6 9 10 | 7 14 15
day 2 | 2 3 5 | 4 9 13 | 6 12 14 | 7 10 11 | 1 8 15
day 3 | 3 4 6 | 5 10 14 | 7 13 8 | 1 11 12 | 2 9 15
day 4 | 4 5 7 | 6 11 8 | 1 14 9 | 2 12 13 | 3 10 15
day 5 | 5 6 1 | 7 12 9 | 2 8 10 | 3 13 14 | 4 11 15
day 6 | 6 7 2 | 1 13 10 | 3 9 11 | 4 14 8 | 5 12 15
day 7 | 7 1 3 | 2 14 11 | 4 10 12 | 5 8 9 | 6 13 15