CHAPTER IX.

kirkman's school-girls problem.
The Fifteen School-Girls Problem — first enunciated b}' T. P. Kirkman, and commonly known as Kirhnans Problem — consists in arranging fifteen things in ditferent sets of triplets. It is usually presented in the form that a school- mistress was in the habit of taking her girls for a daily walk. The girls were fifteen in number, and were arranged in five row^s of three each so that each girl might have two companions. The problem is to dispose them so that for seven consecutive days no girl will walk with any of her school-fellows in any triplet more than once.
In the general problem, here discussed, we require to arrange n girls, where n is an odd multiple of 3, in triplets to walk out for y days, where y = (n — l)/2, so that no girl will walk with any of her school-fellows in any triplet more than once.
The theory of the formation of all such possible triplets in the case of nine girls is comparatively easy, but the general theory involves considerable difficulties. Before describing any methods of solution, I will give briefly the leading facts in the history of the problem. For this and much of the material of this chapter I am indebted to 0. Eckenstein. Detailed refer- ences to the authorities mentioned are given in the bibliography mentioned in the footnote*.
* The problem was first published in the Lady's and Gentleman's Diary for 1850, p. 48, and has been the subject of numerous memoirs. A bibliography of the problem by 0. Eckenstein appeared in the Messenger of Mathematics, Cambridge, July, 1911, vol. xli, pp. 33—36,
B. R. 13
194 KIRKMAN*S SCHOOL-GIRLS PROBLEM [CH. IX
The question was propounded in 1850, and in the same year solutions were given for the cases when n = 9, 15, and 27 ; but the methods used were largely empirical.
The first writer to subject it to mathematical analysis was R. E,. Anstice who, in 1852 and 1853, described a method for solving all cases of the form 12m + 3 when 6m +1 is prime. He gave solutions for the cases when n=15, 27, 89. Sub- stantially, his process, in a somewhat simplified form, is covered by that given below under the heading Analytical Methods.
The next important advance in the theory was due to B. Peirce who, in 1860, gave cyclical methods for solving all cases of the form 12?7i + 8 and 24??i + 9. But the processes used were complicated and partly empirical.
In 1871 A. H. Frost published a simple method applicable to the original problem when ?i = 15 and to all cases when n is of the form 2""* — 1. It has been applied to find solutions when 71 = 15 and ?i = 63.
In 1883 E. Marsden and A. Bray gave three-step cyclical solutions for 21 girls. These were interesting because Kirkman had expressed the opinion that this case was insoluble.
Another solution when n = 21, by T. H. Gill, was given in the fourth edition of this book in 1905. His method though empirical appears to be applicable to all cases, but for high values of n it involves so much preliminary work by trial and error as to be of little value.
A question on the subject which I propounded in the Educational Times in 1906, attracted the attention of L. A. Legros, H. E. Dudeney and 0. Eckenstein, and I received from them a series of interesting and novel solutions. As illustra- tions of the processes used, Dudeney published new solutions for 71= 27, S3, 51, 57, 69, 75, 87, 93, 111 ; and Eckenstein for 71= 27, 38, 39, 45, 51, 57, 69, 75, 93, 99, 111, 123, 135.
I now proceed to describe some of the methods applicable to the problem. We can use cycles and combinations of them. I confine my discussion to processes where the steps of the cycles do not exceed three symbols at a time. It will be con- venient to begin with the easier methods, where however a
CH. ix] kirkman's school-girls problem 195
certain amount of arrangement has to be made empirically, and then to go on to the consideration of the more general method.
One-Step Cycles. As illustrating solutions by one-step cyclical permutations I will first describe Legros's method. Solutions obtained by it can be represented by diagrams, and their use facilitates the necessary arrangements. It is always applicable when n is of the form 24??! + 3, and seems to be also applicable when n is of the form 24??i + 9. Somewhat similar methods were used by Dudeney, save that he made no use of geometrical constructions.
We have ?i = 2y -f 1 = 24??i + 3 or n= 2y -[-1 - 24m + 9. We may denote one girl by k, and the others by the numbers 1, 2, 3, ... 2y. Place k -at the centre of a circle, and the numbers 1, 2, 3, ... 2y at equidistant intervals on the circum- ference. Thus the centre of the circle and each point on its circumference will indicate a particular girl. A solution in which the centre of the circle is used to denote one girl is termed a central solution.
The companions of k are to be different on each day. If we suppose that on the first day they are 1 and y+1, on the second 2 and y + 2, and so on, then the diameters through k will give for each day a triplet in which k appears. On each day we have to find 2{y — l)/3 other triplets satisfying the conditions of the problem. Every triplet formed from the remaining 2?/ — 2 girls will be represented by an inscribed triangle joining the points representing these girls. The sides of the triangles are the chords joining these 2^—2 points. These chords may be represented symbolically by [1], [2], [3], ... [i/— 1]; these numbers being proportional to the smaller arcs subtended. I will denote the sides of a triangle so repre- sented by the letters p, q, r, and I will use the term triad or grouping to denote any group of p, q, r which determines the dimensions of an inscribed triangle. I shall place the numbers of a triad in square brackets. If p, q, r are proportional to the smaller arcs subtended, it is clear that ii p -\- q is less than y, we have p -\-q = r', and if ^ 4- ^^ is greater than y we have p + q-\-r= 2y. If we like to use arcs larger than the
13—2
196 kirkman's school-girls problem [ch. IX
semi-circnmference we mav confine ourselves to the relation 'p-\-q — r. In the geometrical methods described below, we usually first determine the dimensions of the triangles to be used in the solution, and then find how they are to be arranged in the circle.
If (y — l)/3 scalene triangles, whose sides are jt?, g, r, can be inscribed in the circle so that to each triangle corresponds an equal complementary triangle having its equal sides parallel to those of the first and with its vertices at free points, then the system of 2 (3/ — l)/3 triangles with the corresponding diameter will give an arrangement for one day. If the system be per- muted cyclically 3/ — 1 times we get arrangements for the other y — \ days. No two girls will walk together twice, for each chord occupies a different position after each permutation, and as all the chords forming the (3/ — 1)/.3 triangles are unequal the same combination cannot occur twice. Since the triangles are placed in complementary pairs, one being y points in front of the other, it follows that after y — \ permutations we shall come to a position like the initial one, and the cycle will be completed. If the circle be drawn and the triangles cut out to scale, the arrangement of the triangles is facilitated. The method will be better understood if I apply it to one or two of the simpler cases.
The first case is that of three girls, a, 6, c, walking out for one day, that is, w = 3, m = 0, 3/ = 1. This involves no discussion, the solution being (a. 6. c).
The next case is that of nine girls walking out for four days, that is, ?i = 9, m = Oj 3/ = 4. The first triplet on the first day is (1. h. 5). There are six other girls represented by the points 2, 3, 4, 6, 7, 8. These points can be joined so as to form triangles, and each triangle will represent a triplet. We want to find one such triangle, with unequal sides, with its vertices at three of these points, and such that the triangle formed by the other three points will have its sides equal and parallel to the sides of the first triangle.
The sides of a triangle are p, q, r. The only possible values are 1, 2, 3, and they satisfy the condition p + 5 = r. If a
I
CH. IX]
KIPKMANS SCHOOL-GTRLS PROBLEM
197
triangle of this shape is placed with its vertices at the points 3, 4, 6, we can construct a complementary equal triangle, four points further on, having 7, 8, 2 for its vertices. All the points in the figure are now joined, and form the three triplets for the first day, namely (k. 1. 5), (3. 4. 6), (7. 8. 2). It is only necessary to rotate the figure one step at a time in order to obtain the triplets for the remaining three days. Another similar solution is obtained from the diameter (1. k. 5), and the triangles (2. 3. 8), (6. 7. 4). It is the reflection of the former solution.
Figure i.
The next case to which the method is applicable is when n — 27, m= 1, y = 13. Proceeding as before, the 27 girls must be arranged with one of them, k, at the centre and the other 26 on the cu'cumference of a circle. The diameter (1. k. 14) gives the first triplet on the first day. To obtain the other triplets we have to find four dissimilar triangles which satisfy the con- ditions mentioned above. The chords used as sides of these trianoles may be of the lengths represented symbolically by [1], [2], ... [12]. We have to group these lengths so that p-{-q = rovp-\-q-^r=2y; if the first condition can be satis- fied it is the easier to use, as the numbers are smaller. In this instance the triads [3, 8, 11], [5, 7, 12], [2, 4, 6], [1, 9, 10] will be readily found. Now if four triangles with their sides of these lengths can be arranged in a system so that all the vertices fall on the ends of different diameters (exclusive of the ends of the diameter 1, k, 14), it follows that the opposite ends of those diameters can be joined by chords giving a series of equal triangles, symmetrically placed, each liaving its sides parallel to those of a triangle of the first system. The following arrangement
198 kirkman's schooL'GIRls problem [CH. IX
of triangles satisfies the conditions: (4?. 11. 25), (5. 8, 23), (6. 7. 16), (9. 13. 15). The complementary system is (17. 24. 12), (18. 21. 10), (19. 20 3), (22. 26. 2). These triplets with {k. 1. 14) give an arrangement for the first day; and, by rotating the system cyclically, the a,rrangements for the re- maining 12 days can be found immediately.
I proceed to give one solution of this type for every remaining case where n is less than 100. From the result the triads or gi'oupings used can be obtained. It is sufficient in each case to give an arrangement on the first day, since the arrangements on the follov.iug days are at once obtainable by cyclical per- mutations.
I take first the three cases, 33, 57, 81, where n is of the form 24m + 9. In these cases the arrangements on the other days are obtained by one-step cyclical permutations.
For 33 girls, a solution is given by the system of triplets (2. 11. 16), (4. 6. 10), (5. 13. 30), (7. 8. 19), (9. 28. 31), and the complementary system (18. 27. 32), (20 22. 26), (21. 29. 14), (23. 24. 3), (25. 12. 15). These 10 triplets, together with that represented by (fc. 1. 17), will give an arrangement for the first day.
For 67 girls, a possible arrangement of triplets is (18. 13. 50), (20. 11. 28), (21. 62. 3), (8. 10. 51), (4. 25. 26), (2. 6. 12), (7. 19. 33), (27. 43. 16), (37 14. 17). These, with the 9 complementary triplets, and the diameter triplet (1. k. 29), give an arrangement for the first day.
For 81 girls an arrangement for the first day consists of the diameter triplet (1. ft. 41), the 13 triplets (3. 35. 42), (4. 10. 29), (5. 28. 56), (6. 26. 39), (7. 15. 17), (8. 11. 32), (13. 27 49), (14. 19. 30), (20. 37- 38), (21. 25. 52), (24. 36. 62), (18. 33. 63), (31. 40. 74), and the 13 complementary triplets.
I take next the three cases, 51, 75, 99, where n is of the form 24??i + 3. In these cases the arrangements on the other days are obtained either by one-step or by two-step cyclical permutations.
For 51 girls, an arrangement for the first day consists of the diameter triplet (fc. 1. 26), the 8 triplets (2. 9. 36), (4. 7. 25), (6. 10. 19), (8. 14. 22), (12. 17. 45), (13. 24. 48), (15. 16. 46), (18. 28. 30), and the 8 complementary triplets
For 75 girls, an arrangement for the first day consists of the diameter triplet (k. 1. 38), the 12 triplets (2. 44. 55), (4. 11. 19), (5. 50. 66), (6. 52. 57), (8. 46. 58), (10. 59. 65), (12. 60. 64), (14 24. 68), (16 25. 72), (17. 3. 74), (33. 34. 73), (30. 32. 63), and the 12 complementary triplets.
For 99 girls an arrangement for the first day consists of the diameter triplet (1. k. 50), the 16 triplets (2. 17. 47), (3. 9. 68), (4. 44. 82), (5. 12. 75), (6. 32. 42), (7. 23. 97), (8. 21. 30), (15. 20. 76), (16. 35. 85), (18. 45. 62), (22. 40. 63), (25. 37. 92), (28. 29. 80), (34. 38. 59), (39. 41. 73), (46. 49. 60), and the 16 complementary triplets.
It is also possible to obtain, for numbers of the form 24m + 3, solutions which are uniquely two-step, but in these the complementary triangles are not
CH. ix] kirkman's school-girls problem 199
placed symmetrically to each other. I give 27 girls as an instance, ueing the same triads as in the solution of this case given above. The triplets for the first day are {k. 1. 14), (2. 12. 3), (21. 5. 22), (20. 24. 26), (11. 15. 17), (8. 16. 19), (25. 7. 10), (6. 18. 13), and (23. 9. 4). From this tlie arrangements on the other days can be obtained by a two-step (but not by a one-step) cyclical permutation.
It is uDnecessary to give more examples, or to enter on the question of how from one solution others can be deduced, or how many solutions of each case can be obtained in this way. The types of the possible triangles are found analytically, but their geometrical arrangement is empirical. The defect of this method is that it may not be possible to arrange a given grouping. Thus when n = 27, we easily obtain 24 different groupings, but two of them cannot be arranged geometrically to give solutions ; and whether any particular grouping will give a solution can, in many cases, be determined only by long and troublesome empirical work. The same objection applies to the two-step and three-step methods which are described below.
Tiuo-Step Cycles. The method used by Legros was extended by Eckenstein to cases where n is of the form 127?i-f 3. When n is of this form and m is odd we cannot get sets of comple- mentary triangles as is required in Legros's method ; hence, to apply a similar method, we have to find 2(3/ — l)/3 different dissimilar inscribed triangles having no vertex in common and satisfying the condition p-\- q = r or p -\- q-\- r = 2y. These solutions are also central. Since there are 2y points on the cii'cumference of the circle the permutations, if they are to be cyclical, must go in steps of two numbers at a time. In Legros's method we represented one triplet by a diameter. But obviously it will answer our purpose equally well to represent it by a triangle with k as vertex and two radii as sides, one drawn to an even number and the other to an odd number: in fact this will include the diameter as a particular case.
I begin by considering the case where we use the diameter (1. k. y) to represent one triplet on the first day. Here the chords used for sides of the triangles representing the other triplets must be of lengths [1], [2], ... [y - !]• Also each given
200
kirkman's school-girls problem
[CH. IX
length must appear twice, and the two equal lines so repre- sented must start one from an even number and the other from an odd number, so as to avoid the same combination of points occurring again when the sj^stem is rotated cyclically. Of course a vertex cannot be at the point 1 or y, as these points will be required for the diameter triplet (1. k. y).
These remarks will be clearer if we apply them to a definite example. I take as an instance the case of 15 girls. As before we represent 14 of them by equidistant points numbered 1, 2, 3, ... 14 on the circumference of a circle, and one by a point h at its centre. Take as one triplet the diameter (1. k. 8). Then the sides p, q, r may have any of the values [1], [2], [3], [4], [5], [6], and each value must be wsed twice. On examination it will be found that there are only two possible groupings, namely [1, 1, 2], [2, 4, 6], [3, 3, 6], '[5, 5, 4], and [1, 2, 3], [1, 4, 5], [3, 5, 6], [2, 4, 6]. One of the solutions to which the first set of groupings leads is defined by the diameter (1. k. 8) and the four triplets (9. 10. 11), (4. 6. 14), (2. 5. 13), (3. 7. 12); see figure ii, below : of the four triangles used three are isosceles. The
Figure ii.
Figure iii.
second set leads to solutions defined by the triplets {k. 1. 8), (4. 5. 7), (13. 14. 9), (3. 6. 11), (10. 12. 2), or by the triplets {k. 1. 8), (6. 7. 9), (3. 4. 13), (5. 11. 14), (10. 12. 2): in these solutions all the triangles used are scalene. If any one of these three sets of triplets is rotated cyclically two steps at
CH. TX] KIRKMAN'S SCHOOL-GIRLS PROBLEM 201
a time, we get a solution of the problem for the seven cla3^s required. Each of these solutions b^ reflection and inversion gives rise to three others.
Next, if we take {k. 1. 2) for one triplet on the first day we shall have the points 3, 4,... 14 for the vertices of the four triangles denoting the other triplets on that day. The sides must be of the lengths [1], [2], ... [7], of which [2], ... [6] must be used not more than twice and [1], [7] must be used only once. The [1] used must start from an even number, for otherwise the chord denoted by it would, when the system was rotated, occupy the position joining the points 1 and 2, which has been already used. The only possible groupings are [2, 4, 6], [2, 3, 5], [3, 4, 7], [1, 5, 6] ; or [2, 4, 6], [2, 5, 7], [1, 4, 5], [3, 3, 6] ; or [2, 4, 6], [2, 5, 7], [1, 3, 4], [3, 5, 6]. Each of these groupings gives rise to various solutions. For instance the first grouping gives a set of triplets {k. 1. 2), (3. 7. 10), (4. 5. 13), (6. 9. 11), (8. 12. 14). From this by a cyclical two-step per- mutation we get a solution. This solution is represented in figure iii. If we take {k. 1. 4) or {k. 1. 6) as one triplet on the first day, we get other sets of solutions.
Solutions involving the triplets {k. 1. 2), {k. 1. 4), {k. 1. 6), {k. 1. 8), and other analogous solutions, can be obtained from the solutions illustrated i*n the above diagrams by re-arranging the symbols denoting the girls. For instance, if in figure iii, where all the triangles used are scalene, we replace the numbers 2, 8, 3, 13, 4, 6, 5, 11, 7, 9, 10, 14 by 8, 2, 13, 3, 6, 4, 11, 5, 9, 7, 14, 10, we get the solution {k. 1. 8), (4. 5. 7), etc., given above. Again, if in figure iii we replace the symbols 1, 2, 3, 4, 5, 6, 7,^8, 9, 10, 11, 12, 13, 14, k by 12, 2, 10, G, 1, 14, 5, 13, 9, 15, 4, 3, 11, 8, 7, we obtain a solution equivalent to that given by T. H. Gill and printed in the last edition of this book. In this the arrangement on the first day is (1. 6. 11), (2. 7. 12), (3. 8. 13), (4. 9. 14), (5. 10. 15). Tlie arrangements on the other days are obtained as before by rotating the system so de- lineated round 7 as a centre two steps at a time. Gill's arrangement is thus presented in its canonical form as a central two-stop cyclical jsolution.
202 KIRKMAN's school-girls problem [cH. IX
I proceed to give one solution of this type for every remaining case where n is less than 100. In each case I give an arrangement on the first day; the arrangements for the other days can be got from it by a two-step cyclical permutation of the numbers.
In the case of 27 girls, one arrangement on the first day is (fc. 1. 14), (19. 21. 20), (3. 9. 6), (13. 23. 18), (5. 17. 24), (7. 25. 16), (11. 15. 26), (10. 4. 2), (12. 22. 8).
In the case of 39 girls, one arrangement for the first day is (fc. 1. 20), (35. 37. 36), (7. 13. 10), (19. 29. 24), (11. 25. 18), (3. 21. 12), (17. 33. 6), (15. 27. 2), (23. 31. 8), (5. 9. 26), (4. 16. 32), (14. 34. 38), (22. 28. 30).
In the case of 51 girls, one arrangement for the first day is {k. 1. 26), (21. 23. 22), (11. 17. 14), (35. 45. 40), (25. 39. 32), (15. 33. 24), (13. 41. 2), (5. 31. 18), (19. 49. 34), (27. 43. 10), (9. 47. 28), (29. 37. 8), (3. 7. 30), (4. 20. 46), (6. 36. 42), (12. 16. 44), (38. 48. 50).
In the case of 63 girls, one arrangement for the first day is (&. 1. 32), (57. 59. 58), (23. 29. 26), (37. 47. 42), (5. 53. 60), (17. 61. 8), (3. 43. 54), (7. 33. 20), (9. 39. 24), (27. 55. 10), (21. 45. 2), (11. 31. 52), (35. 51. 12), (13. 25. 50), (41. 49. 14), (15. 19. 48), (16. 18. 36), (6. 34. 38), (46. 56. 62), (22. 30. 44), (4. 28. 40).
In the case of 75 girls, one arrangement for the first day is (fc. 1. 38), (23. 25. 24), (3. 9. 6), (29. 39. 34), (7. 21. 14), (51. 69. 60), (33. 55. 44), (11. 59. 72), (35. 65. 50), (37. 71. 54), (27. 63. 8), (15. 57. 36), (13. 41. 64), (43. 67. 18), (19. 73. 46), (31. 47. 2), (5. 17. 48), (53. 61. 20), (45. 49. 10), (30. 32. 52), (22. 26. 66), (56. 62. 70), (12.. 28. 74), (16. 40. 58), (4. 42. 68).
In the case of 87 girls, one arrangement for the first day is (ft. 1. 44), (61. 63. 62), (73. 79. 76), (35. 45. 40), (11. 83. 4), (25. 43. 34), (59. 81. 70), (7. 33. 20), (41. 71. 56), (23. 75. 6), (27. 65. 46), (13. 57. 78), (5. 51. 28), (3. 39. 64), (15. 47. 74), (9. 67. 38), (31. 55. 86), (19. 85. 52), (21. 87. 72), (17. 29. 66), (69. 77. 30), (49. 53. 8), (10. 12. 24), (22. 26. 84), (18. 54. 60), (2. 50. 80), (32. 42. 58), (14. 36. 82), (16. 48. 68).
In the case of 99 girls, one arrangement for the first day is {k. 1. 50), (47. 49. 48), (53. 59. 56), (55. 65. 60), (57. 71. 64), (23. 41. 32), (17. 39. 28), (63. 89. 76), (5. 35. 20), (3. 67. 84), (9. 69. 88), (29. 85. 8), (27. 79. 4), (25. 73. 98), (33. 77. 6), (21. 61. 90), (45. 81. 14), (51. 83. 18), (15. 43. 78), (13. 37. 74), (11. 31. 70), (75. 91. 34), (7. 19. 62), (87. 95. 42), (93. 97. 46), (58. 94. 96), (40. 44. 66), (10. 16. 26), (30. 38. 82), (68. 80. 2), (22. 36. 92), (24. 54. 72), (12. 52. 86).
This method may be also represented as a one-step cycle. For if we denote the girls by a point k at the centre of the circle, and points aj, 6i, a^, h.^, a^, 63, ... placed in that order on the circumference, we can re- write the solutions in the suffix notation, and then the cyclical permutation of the numbers denoting the suffixes is by one step at a time.
The one-step and two-step methods described above cover
CH. ix] kirkman's school-gtrls problem 203
all cases except those where n is of the form 24m + 21. These I have failed to bring undt^r analogous rules, but we can solve them by recourse to the three-step cycles next described.
Three-Step Cycles. The fact that certain cases are soluble by one-step cycles, and others by two-step cycles, suggests the use of three-step cycles, and the fact that n is a multiple of 3 points to the same conclusion. On the other hand, if we denote the n girls by 1, 2, 3, ... n, and make a cyclical permutation of three steps at a time (or if we denote the girls by cti, 6i, Ci, a^, h., Ca, ..., and make a cyclical permutation of the suffixes one step at a time), we cannot get arrangements for more than 7i/3 days. Hence there will remain (n — l)/2 — ??/3 days, that is, (n — 3)/6 days, for which we have to find other arrangements. In fact, however, we can arrange the work so that in addition to the cyclical arrangements for n/S days we can find (n — 3)/6 single triplets from each of which by a cyclical permutation of the numbers or suffixes an arrangement for one of these remaining days can be obtained ; other methods are also sometimes available.
For instance take the case of 21 girls. An arrangement for the first day is (1. 4. 10), (2. 5. 11), (3. 6. 12), (7. 14. 18), (8. 15. 16), (9. 13. 17), (19. 20. 21). From this by cyclical permutations of the numbers three steps at a time, we can get arrangements for 7 days in all. The arrangement for the 8th day can be got from the triplet (1. 6. 11) by a three-step cyclical permutation of the numbers in it. Similarly the arrangement for the 9th day can be got from the triplet (2. 4. 12), and that for the 10th day from the triplet (3, 5. 10), by three-step cyclical permutations.
This method was first used by A. Bray in 1883, and was subsequently developed by Dudeney and Eckenstein. It gives a solution for every value of n except 15, but it is not so easy to use as the methods already described, partly because the solution is in two parts, and partly because the treatment varies according as n is of the form 18??i-}-3, or 18m 4-9, or 18m + 15. Most of the difficulties in using it arit^e in the case when n is of the form 18m -f- 15.
204 KIRKMAN'S school-girls problem [CH. IX
The geometrical representation is sufficiently obvious. In the methods used by Legros and Eckenstein, previously de- scribed, the girls were represented by 2y equidistant points on the circumference of a circle and a point at its centre. It is evident that we may with equal propriety represent all the girls by symbols placed at equidistant intervals round the circumference of a circle : such solutions are termed non- central. The symbols may be 1, 2, 3, ... n, or letters a,, 6i, Ci, o^2> &2> C.2, — Any triplet will be represented by a triangle whose sides are chords of the circle. The arrangement on any day is to include all the girls, and therefore the triangles re- presenting the triplets on that day are n/o in number, and as each girl appears in only one triplet no two triangles can have a common vertex.
The complete three-step solution will require the determina- tion of a system of {n— l)/2 inscribed triangles. In the first part of the solution ?i/3 of these triangles must be selected to form an arrangement for the first day, so that by rotating this arrangement three steps at a time we obtain triplets for njZ days in all. In the second part of the solution we must assure ourselves that the remaining {n — 3)/6 triangles are such that from each of them, by a cyclical permutation of three steps at a time, an arrangement for one of the remaining {n — 3)/6 days is obtainable.
As before we begin by tabulating the possible differences [1], [2], [3], ... [(?i — l)/2], whose values denote the lengths of the sides p, q, r of the possible triangles, also, we have either p + q — r OY p + q + r — n. From these values of p, q, r are formed triads, and in these triads each difference must be used three times and only three times. Triangles of these types must be then formed and placed in the circle so that the side denoting any assigned difference p must start once from a number of the form 3m, once from a number of the form 3m-f-l, and once from a number of the form Sm + 2. Also an isosceles triangle, one of whose sides is a multiple of three, cannot be used : thus in any particular triad a 3, 6, 9, ... cannot appear more than once. Save in some exceptional cases of high values of n, every triangle, one of whose
CH. iX] KIRKMA.N*S SCHOOL-GIRLS PROBLEM 205
sides is a multiple of 3, must be used in the first part of the solution. In the whole arrangement every possible difference will occur n times, and, since any two assigned numbers can occur together only once, each diiference when added to a number must start each time from a different number. I will not go into further details as to how these trianoles are determined, but I think the above rules will be clear if I apply them to one or two easy examples.
For 9 girls, the possible differences are [1], [2], [3], [4], each of which must be used three times in the construction of four triangles the lengths of whose sides p, q, r are such that p -^q z=,r OT p + q + r = 9. One possible set of triads formed from these numbers is [1, 2, 3], [1, 2, 3], [2, 3, 4], and [1, 4, 4]. Every triangle with a side of the length [3] must appear in the first part of the solution ; thus the triplets used in the first part of the solution must be obtained from the first three of these triads. Hence we obtain as an arrangement for the first day the triplets (1. 3. 9), (2. 4. 7), (5. 6. 8). From this, three-step cyclical permutations give arrangements for other two days. The remaining triad [1, 4, 4] leads to a triplet (1. 2. 6) which, by a three- step cyclical permutation, gives an arrangement for the remaining day.
If we use the suffix notation, an arrangement for the first day is a^b^a^, hiC^h^, CiOfaCg. From this, by simple cyclical per- mutations of the suffixes, we get arrangements for the second and third days. Lastly, the triplet UibiCi gives, by cyclical permutation of the suffixes, the arrangement for the fourth day, namely, (ii&iCi, a^b^c^, a^biCz.
For 15 girls, the . three-step process is inapplicable. The explanation of this is that two triads are required in the second part of the solution, and in neither of them may a 3 appear. The triads are to be formed from the differences [1], [2], ... [7], each of which is to be used three times, and the condition that in any particular triad only one 3 or one 6 ma}^ appear necessitates that six of the triads shall involve a 3 or a 6. Hence only one triad will be available for the second part pf the solution.
206 kirkman's school-girls problem [ch. IX
I proceed to give one solution of this type for every remaining case where n is less than 100. I give some in the numerical, others in the suffix notation. The results will supply an indication of the process used.
First, I consider those cases where n is of the form 18m + S. In these cases it is always possible to find 2m triads each repeated thrice, and one equilateral triad, and to use the equilateral and m triads in the first part of the solution, the 3 triplets representing any one of these m triads being placed in the circle at equal intervals from each other in the first day's arrangement. From this, three-step or one- step cyclical permutations give arrangements for 6m -l- 1 days in all. In the second part of the solution each of the m remaining triads is used thrice ; it suffices to give the first triplet on each day, since from it the other triplets on that day are obtained by a three-step cyclical permutation.
For 21 girls an arrangement for the first day, for the first part of the solution, is (1. 4. 10), (8. 11. 17), (15. 18. 3), (2. 6. 7), (9. 13. 14), (16. 20. 21), (5. 12. 19). From this, three-step or one-step cyclical permutations give arrangements for 7 days in all. The first triplets used in the second part of the solution are (1. 3. 11), (2. 4. 12), (3. 5. 13). Each of these three triplets gives by a three- step cyclical permutation an arrangement for one of the remaining 3 days.
For 39 girls, arrangements for 13 days can be obtained from the following arrangement of triplets for the first day: (1. 4. 13), (14. 17. 26), (27. 30. 39), (2. 8. 23), (15. 21. 36), (28. 34. 10), (7. 11. 12), (20. 24. 25), (33. 37. 38), (3. 5. 19), (16. 18. 32), (29. 31. 6), (9. 22. 35). From each of the 6 triplets (1. 8. 18), (2. 9. 19), (3. 10. 20), (1. 9. 20), (2. 10. 21), (3. 11. 22), an arrangement for one of the remaining 6 days is obtainable.
For 57 girls, arrangements for 19 days can be obtained from the following arrangement of triplets for the first day: (1. 4. 25), (20. 23. 44), (39. 42. 6), (2. 8. 17), (21. 27. 36), (40. 46. 55), (3. 15. 33), (22. 34. 52), (41. 53. 14), (18. 19. 26), (37. 38. 45), (56. 57. 7), (13. 30. 35), (32. 49. 54), (51. 11. 16), (9. 29. 43), (28. 48. 5), (47. 10. 24), (12. 31. 50). From each of the 9 triplets (1. 3. 14), (2. 4. 15), (3. 5. 16), (1. 5. 30), (2. 6. 31), (3. 7. 32), (1. 11. 27), (2. 12. 28), (3. 13. 29), an arrangement for one of the remaining 9 days is obtainable.
For 75 girls, arrangements for 25 days can be obtained from the following arrangement of triplets for the first day : (1. 4. 10), (26. 29. 35), (51. 54. 60), (3. 15. 36), (28. 40. 61), (53. 65. 11), (2. 17. 41), (27. 42. 66), (52. 67. 16), (13. 31. 58), (38. 56. 8), (63. 6. 33), (14. 21. 22), (39. 46. 47), (64. 71. 72), (7. 18. 20), (32. 43. 45), (57. 68. 70), (5. 9. 37), (30. 34. 62), (55. 59. 12), (19. 24. 50), (44. 49. 75), (69. 74. 25), (23. 48. 73). From each of the 12 triplets (1. 11. 30), (.2. 12. 31), (3. 13. 32), (1. 15. 35), (2. 16. 36), (3. 17. 37), (1. 17. 39), (2. 18.40), (3. 19. 41), (1. 18. 41), (2. 19. 42), (3. 20. 43), an arrangement for one of the remaining 12 days is obtainable.
For 93 girls, arrangements for 31 days can be obtained from the following arrangement of triplets for the first day : (1. 76. 79), (32. 14. 17), (63. 45. 48), (13. 25. 55), (44. 56. 86), (75. 87. 24), (29. 50. 74), (60. 81. 12), (91. 19. 43), (20. 26. 59), (51. 57. 90), (82. 88. 28), (3. 30. 39), (34. 61. 70), (65. 92. 8), (27. 64. 71), (58. 2. 9), (89. 33. 40), (35. 36. 52), (66. 67. 83), (4. 5. 21), (11. 15. 37), (42. 46. 68), (73. 77. 6), (16. 18. 41), (47. 49. 72), (78. 80. 10),
CH. ix] kirkman's school-girls problem 207
(23. 31. 69), (54. 62. 7), (85. 93. 38), (22. 53. 84). From each of the 15 triplets (1. 14. 42), (2. 15. 43), (3. 16. 41), (1. 33. 44), (2. 34. 45), (3. 35. 46), (1. IT. 30), (2. 12. 31), (3. 13. 32), (1. 6. 41), (2. 7. 42), (3. 8. 43), (1. 15. 35), (2. 16. 36), (3. 17. 37), an arrangement for one of the remaining 15 days is obtainable by a three- step cyclical permutation.
Before leaving the subject of numbers of this type I give two other solutions of the case when n = 21, one to illustrate the use of the suffix notation, and the other a cyclical solution which is uniquely three-step.
If we employ the suffix notation, the suffixes, with the type here used, are somewhat trying to read. Accordingly hereafter I shall write al, a2, ... , instead
of aj, a.j, In the case of 21 girls, an arrangement for the first day is
(al. a2. a4), (61. 62. 64), (cl. c2. c4), (a3. 66. c5), (63. c6. a5), (c3. a6. 65), (al. 67. cl). From this, by one-step cyclical permutations of the suffixes, we get arrangements for the 2nd, 3rd, 4th, 5th, 6th and 7th days. The arrange- ment for the 8th day can be obtained from the triplet (al. 62. c-i) by permuting the suffixes cyclically one step at a time. Similarly the arrangement for the 9th day can be obtained from the triplet (61. c2. a4) and that for the 10th day from the triplet (cl. rt2. 64). Thus with seven suffixes we keep 7 for each symbol in one triplet, and every other triplet depends on one or other of only two arrangements, namely, (1. 2. 4), or (3. 6. 5). If the solution be written out at length the principle of the method used will be clear.
Cyclical solutions which are uniquely three-srep can also be obtained for numbers of the form 18»i-f3; in them the same triads can be used as before, but they are not placed at equal intervals in the circle. I give 21 girls as instance. The arrangements on the first 7 days can be obtained from the arrangement (1. 4. 10), (2. 20. 14), (15. 18. 3), (16. 17. 21), (8. 9. 13), (6. 7. 11), (5. 12. 19) by a three-step (but not by a one-step) cyclical permutation. From each of the triplets (1. 3. 11), (2. 4. 12), (3. 5. 13), an arrangement for one of the remaining 3 days is obtainable.
Next, I consider those cases where n is of the form 18j7H-9. Here, regular solutions in the suffix notation can be obtained in all cases except in that of 27 girls, but if the same solutions are expressed in the numerical notation, the triads are irregular. Accordingly, except when n = 27, it is better to use the suffix notation. I will deal with the case when n = 27 after considering the cases when n = 45, 63, 81, 99.
For 45 girls, an arrangement for the first day consists of the 5 triplets (al. al2. al3), (a2. a9. all), (a5. alO. 615), (a4. 63. c7), (a8. 66. cl4), and the 10 analogous triplets, namely, (61. 612. 613), (cl. cl2. cl3), (62. 69. 611), (c2. c9. ell), (65. 610. cl5), (c5. clO. al5), (64. c3. a7), (c4. a3. 67), (68. c6. al4), (c8. a6. 614). From these, by one-step cyclical permutations of the suffixes, the arrangements for 15 days can be got. Each of the 2 triplets (c4. 63. a7), (c8.66.al4), the 4 analogous triplets, namely, (a4.c3.67), (64.a3.c7), («8.c6.614), (68. a6. cl4), and the triplet (al. 61. cl), gives, by a one-step cyclical permuta- tion of the suffixes, an arrangement for one of the remaining 7 days.
For 63 girls, an arrangement for the first day consists of the 7 triplets (al. alO. «9), (a5. a8. a3), (a4. al9. alo), (a7. al4. 621), (a20. 611. cl2), (al6. 613. cl8), (al7. 62, c6), and the 14 analogous triplets. From these, by
208 kirkman's school-girls problem [CH. IX
one-step cyclical permutations of the suffixes, the arrangements for 21 days can be got. Each of the 10 triplets, consisting of the 3 triplets (c20. &11. al2), (cl6. 613, al8), (cl7. 62. a6), the 6 analogous triplets, and the triplet (al. 61. cl), gives, by a one-step cyclical permutation of the suffixes, an arrangement for one of the remaining 10 days.
For 81 girls, an arrangement for the first day consists of the 9 triplets (a5. al. aS), (a3. alO. ali), {all. a21. a26), (a4. al2. a25), (a9. alS. 627), {a22. 620. cl9), {a24. 617. cl3), (al6. 66. cl), (a23. 615. c2), and the 18 analogous triplets. From these, by cyclical permutations of the suffixes, the arrangements for 27 days can be got. Each of the 13 triplets consisting of the 4 triplets (c22. 620. al9), (c24. 617. al3), (cl6. 66. al), (c23. 615. a2), the 8 analogous triplets, and the triplet (al. 61. cl), gives, by a cyclical permutation of the suffixes, an arrangement for one of the remaining 13 days.
For 99 girls, an arrangement for the first day consists of the 11 triplets (al. a3. alO), (a2. a6. a20), (a4. al2. a7), (a8. a24. al4), (al6. al5. a28), (all. a22. 633), (a32. 630. c23), (rt31. 627. cl3), (a29. 621. c26), (a25. 69. cl9), (al7. 618. c5), and the 22 analogous triplets. From these, by cyclical permuta- tions of the suffixes, the arrangements for 33 days can be got. Each of the 16 triplets consisting of the 5 triplets (c32. 630. a23), (c31. 627. al3), (c29. 621. a26), (c25. 69. al9), (cl7. 618. a5), the 10 analogous triplets, and the triplet (al. 61. cl), gives, by a cyclical permutation of the suffixes, an arrangement for one of the remaining 16 days.
For 27 girls, an arrangement of triplets for the first day is (1. 7. 10), (14. 17. 8), (27. 6. 9), (13. 20. 25), (11. 23. 18), (12. 16. 24), (21. 2. 4), (15. 22. 26), (19. 3. 5). From this, three-step cyclical permutations give arrangements for 9 days in all. The first triplets on the remaining 4 days are (1. 2. 3), (1. 6. 20), (1. 11. 15), (1. 17. 27), from each of which, by a three-step cyclical permutation, an arrange- ment for one of those days is obtainable.
Regular solutions in the numerical notation can also be obtained for all values of n, except 9, where n is of the form 18??i-i-9. I give 27 girls as an instance. The first day's arrangement is (1. 2. 4), (10. 11. 13), (19. 20. 22), (8. 15. 23), (17. 24. 5), (26. 6. 14), (3. 25. 9), (12. 7. 18), (21. 16. 27); from this, arrangements for 9 days in all are obtained by one-step cyclical permutations. Each of the three triplets (1. 5. 15), (2. 6. 16), (3. 7. 17) gives an arrangement for one day by a three-step cyclical permutation. Finally the triplet (1. 10. 19), represented by an equilateral triangle, gives the arrangement on the last day by a one-step cyclical permutation.
Lastly, I consider those cases where n is of the form 18ni-|-15. As before, the solution is divided into two parts. In the first part, we obtain an arrange- ment of triplets for the first day, from which arrangements for Qm + 5 days are obtained by three-step cyclical permutations. In the second part, we obtain the first triplet on each of the remaining Sm -f 2 days, from which the other triplets on that day are obtained by three-step cyclical permutations.
For 33 girls, an arrangement in the first part is (1. 13. 19), (23. 11. 5), (3. 15. 21), (2. 4. 7), (12. 14. 17), (28. 30. 33), (6. 16. 25), (10. 20. 29), (8. 18. 27), (24. 31. 32), (9. 22. 26). The triplets in the second part are (25. 32. 33), (26. 33. 1), (10. 23. 27), (11. 24. 28), (1. 12. 23).
CH. ix] kirkman's school-girls problem 209
For 51 girls, an arrangement in the first part is (17. 34. 51), (49. 16. 10), (11. 44. 50), (15. 33. 27), (19. 4. 46), (2. 38. 20), (21. 36. 45), (22. 25. 24), (5. 8. 7), (39. 42. 41), (43. 13. 20). (26. 47. 3), (9. 30. 37), (1. 14. 6), (35. 48. 40), (18. 31. 23), (28. 32. 12). The triplets in the second part are (29. 33. 13), (30. 34. 14), (1. 26. 12). (2. 27. 13), (3. 28. 14), (1. 11. 30), (2. 12. 31), (3. 13. 32).
For 69 girls, an arrangement in the first part is (23. 46. 69), (31. 34. 43), (11. 8. 68), (54. 57. 66), (58. 52. 28), (35. 29. 5), (45. 51. 6), (16. 1. 49), (62. 47. 26), (39. 24. 3), (4. 55. 42), (50. 32. 19), (27. 9. 65), (40. 67. 18), (17. 44. 64), (63. 21. 41), (10. 14. 15), (33. 37. 38), (56. 60. 61), (25. 53. 36), (2. 30. 13), (48. 7. 59), (22. 20. 12). The triplets in the second part are (23. 21. 13), (24. 22. 14), (1. 8. 33), (2. 9. 34), (3. 10. 35), (1. 17. 36), (2. 18. 37), (3. 19. 38), (1. 41. 15), (2. 42. 16), (3. 43. 17).
For 87 girls, an arrangement in the first part is (29. 58. 87), (76. 82. 73), (47. 53. 44), (15. 9. 18), (70. 1. 18), (41. 59. 71), (12. 30. 42), (4. 67. 31), (2. 26. 62), (60. 84. 33), (40. 79. 25), (11. 50. 83), (69. 21. 54), (43. 64. 63), (14. 35. 34), (72. 6. 5), (61. 16. 77), (32. 74. 48), (3. 45. 19), (28. 68. 66), (37. 86. 39), (10. 8. 57), (46. 80. 36), (22. 65. 75), (7. 17. 51), (85. 23. 78), (52. 20. 27). (49. 56. 81), (55. 38. 24). The triplets in the second part are (56. 39. 25), (57. 40. 26), (1. 5. 42), (2. 6. 43), (3. 7. 44), (1. 29. 6), (2. 30. 7), (3. 31. S), (1. 9. 20), (2. 10. 21), (3. 11. 22), (1. 14. 36), (2. 15. 37), (3. 16. 38).
Before proceeding to the consideration of other methods I should add that it is also possible to obtain irregular solutions of cases where n is of any of these three forms. As an instance I give a three-step solution of 33 girls. A possible arrangement in the first part is (1. 4. 10), (14. 23. 26), (9. 15. 30), (3. 28. 33), (2. 6. 8), (11. 18. 27), (13. 24. 25), (5. 16. 20), (7. 17. 22), (21. 29. 31), (12. 19. 32). The triplets in the second part are (1. 2. 21), (1. 8. 30), (1. 3. 26), (1. 15. 20), (1. 17. 18). I describe this solution as irregular, since all, save one, of the triads used are different.
The Focal Method. Another method of attacking the problem, comparatively easy to use in practice, is applicable when n is of the form 24?m + Sp, where p = 6g + 3. It is due to Eckeustein. Here it is convenient to use a geometrical repre.sentation by denoting 24;/i + 2p girls by equidistant numbered points on the circumference of a circle, and the remaining p girls by lettered points placed inside the circle; these p points are termed foci. The solution is in two parts. In the first part, we obtain an order from which the arrange- ments for 12m-\-p days are deducible by a two-step cycle of the numbers: in none of these triplets does more than one focus appear. In the second part, we find the arrange- ments for the remaining Sq + 1 days ; here the foci and the numbered points are treated separately, the former being
a R. 14
210 kirkman's school-girls problem [CH. IX
arranged by any of the methods used for solving the case of 6g + 3 girls, while of the latter a typical triplet is used on each of those days, from which the remaining triplets on that day are obtained by cyclical permutations.
This method covers all cases except when n=15, 21, 39; and solutions by it for all values of n less than 200 have been written out. Sets of all the triplets required can be definitely determined. One way of doing this is by finding the primitive roots of the prime factors of 4m •}-2q + l, though in the simpler cases the triplets can be written down empirically without much trouble. An advantage of this method is that solutions of several cases are obtained by the same work. Suppose that we have arranged suitable triangles in a circle, having on its circumference 12m + p or 3c equidistant points, and let y be the greatest integer satisfying the indeterminate equation 2a; + 4^/ + 1 = c, where x = 0 or a) = l, and a the highest multiple of 6 included in x + y, then sokitions of not less than y-hl—a cases can be deduced. Thus from a 27 circle arrangement where c = 9, y = 2, x = 0, a = 0, we can by this method deduce three solutions, namely when n = 57, 69, 81 ; from a 39 circle arrangement where c=13, 2/ = 3, ^ = 0, a = 0, we can deduce four solutions, namely when n = 81, 93, 105, 117.
I have no space to describe the method fully, but I will give solutions for two cases, namely for 33 girls (?i = 33, m = 1, p = 3) where there are 3 foci, and for 51 girls (?i = 51, m = 1, p = 9) where there are 9 foci.
For 33 girls we have 3 foci which we may denote by a, b, c, and 30 points which we may denote by the numbers 1 to 30 placed at equidistant intervals on the circumference of a circle. Then if the arrangement on the first day is (a. 5. 10), (b. 20. 25), (c. 15. 30), (1. 2. 14), (16. 17. 29), (4, 28. 2G), (19. 8. 11), (9. 7. 3), (24. 22. 18), (6. 27. 13), (21. 12. 28), a two-step cyclical per- mutation of the numbers gives arrangements for 15 days; that on the second day being (a. 7. 12), (6. 22. 27), &c. The arrangement on the 16th day is (a. 6. c), (1. 11. 21), (2. 12. 22), (3. 13. 23), . .(10 20.30).
For 51 girls we have 9 foci which we may denote by a, b, c,
CH. ix] kirkman's school-girls problem 211
d, e,f, g, h,j, and 42 points denoted by 1, 2, ... 42, placed at equidistant intervals on the circumference of a circle. Then if the arrangement on the first day is (a. 5. 6), (6. 26, 27), (c. 3. 10), {d. 24. .SI), (e. 19. 34), (/. 40. 13), (g. 39. 16), {k 18. 37), (j. 21. 42), (9. 11. 22), (30. 32. 1), (35. 41. 2), (14. 20. 23), (17. 29. 12), (38. 8. 33), (7. 15. 25), (28. 36. 4), a two-step cyclical per- mutation of the numbers gives arrangements for 21 days. Next, arrange the 9 foci in triplets by any of the methods already given so as to obtain arrangements for 4 days. From the numbers 1 to 42 we can obtain four typical triplets not already used, namely (1. 5. 21), (2. 6. 22), (3. 7. 23), (14. 28. 42). From each of these triplets we can, by a three- step cyclical permutation, obtain an arrangement of the 42 girls for one day, thus getting arrangements for 4 days in all. Combining these results of letters and numbers we obtain arrangements for the 4 days. Thus an arrangement for the first day would be (a. c.j), (b. d. g), {e.f. h), (1. 5. 21), (4. 8. 24), (7. 11. 27), (10. 14. 30), (13. 17. 33), (16. 20. 36), (19. 23. 39), (22. 26. 42;, (25. 29. 3), (28. 32. 6), (31. 35. 9), (34. 38. 12), (37. 41. 15), (40. 2. 18). For the second day the corresponding arrangement would be (d. f. c), (e. g. a), {h. j. b), (2. 6. 22), (5. 9. 25), &c.
Analytical Methods. The methods described above, under the headings One-Step, Two-Step and Three-Step Cycles, involve some empirical work. It is true that with a little practice it is not difficult to obtain solutions by them when n is a low number, but the higher the value of n the more troublesome is the process and the more uncertain its success. A general arithmetical process has, however, been given by which it is claimed that some solutions for any value of n can be always obtained. Most of the solutions given earlier in this chapter can be obtained in this way.
The essential feature of the method is the arrangement of the numbers by which the girls are represented in an order such that definite rules can be laid down for grouping them in pairs and triplets so that the differences of the numbers in each pair or triplet either are all different or are repeated as often as
14—2
212 KIRKMAN's school-girls problem [cH. IX
may be required. The process depends on finding primitive roots of the prime factors of whatever number is taken as the base of the solution. When (ri — 1)/2 is prime, of the form 6u + l, and is taken as base, the order is obtainable at once, and the rules for grouping the numbers are easy of application ; owing to considerations of space I here confine myself to such instances, but similar though somewhat longer methods are applicable to all cases.
I use the geometrical representation already explained. We have n—2y + l, and 3/ is a prime of the form 6u + 1. In forming the triplets we either proceed directly by arranging all the points in threes, or we arrange some of them in pairs and make the selection of the third point dependent on those of the two first chosen, leaving only a few triplets to be obtained otherwise. In the former case we have to arrange the numbers in triplets so that each difference will appear twice, and so that no two differences will appear together more than once. In the latter case we have to arrange the numbers so that the differences between the numbers in each pair comprise con- secutive integers from 1 upwards and are all different. In both cases, we commence by finding a primitive root of y, say cc. The residues to the modulus y of the 6w successive powers of oc form a series of numbers, el, e2, e3, . . . , comprising all the integers from 1 to 6w, and when taken in the order of the successive powers, they can be arranged in the manner required by definite rules.
I will apply the method to the case of 27 girls from which the general theory, in the restricted case where y is a prime of the form 6u+l, will be sufficiently clear. In this case we have n=27, 3/= 13, u=2, and x = 2. I take 13 as the base of the analysis. I will begin by pairing the points, and this being so, it is convenient to represent the girls by a point k at the centre of a circle and points al, 61, a2, b2, ... at equidistant intervals on the circumference. We reserve k, al3, 613 for one triplet, and we have to arrange the other 24 points so as to form 8 triangles of certain types. The residues are in the order 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, and these may be taken as the suffixes of the remaining ' a 's and ' 6 's.
CH. ix] kirkman's school-girls problem 213
First arrange these residues in pairs so that every difference between the numbers in a pair occurs once. One rule, by which this can be effected, is to divide the residues into two equal sections and pair the numbers in the two sections. This gives (2. 11), (4. 9), (8. 5), (3. 10), (6. 7), (12. 1) as possible pairs. Another such rule is to divide the residue into six equal sections, and pair the numbers in the first and second sections, those in the third and fourth sections, and those in the fifth and sixth sections. This gives (2. 8), (4. 3), (6. 11), (12. 9), (5. 7), (10. 1) as possible pairs. Either arrangement can be used, but the first set of pairs leads only to scalene triangles. In none of the pairs of the latter set does the sum of the numbers in a pair add up to 13, and since this may allow the formation of isosceles as well as of scalene triangles, and thus increase the variety of the resulting solutions, I will use the latter set of pairs. We use these basic pairs as suffixes of the ' a 's, and each pair thus determines two points of one of the triangles required. We have now used up all the ' a 's. The third point associated with each of these six pairs of points must be a ' b' and the remaining six ' h 's must be such that they can be arranged in suitable triplets.
Next, then, we must arrange the 6u residues el, e2, eS, ... in possible triplets. To do this arrange them cyclically in triplets, for instance, as shown in the first column of the left half of the annexed table. We write in the second column the differences between the first and second numbers in each triplet, in the third column the differences between the second and third numbers in each triplet, and in the fourth column the differences between the third and first numbers in each triplet. If any of these differences d is greater than Su we may replace it by the complementary number y — d: that this is permissible is obvious from the geometrical representation. By shifting cyclically the symbols in any vertical line in the first column we change these differences. We can, however, in this way always displace the second and third vertical lines in the first column so that the numbers in the second, third, and fourth columns include the numbers 1 to Sa twice over. This can be effected
214
KIRKMAN S SCHOOL-GIRLS PROBLEM
[CH. IX
thus. If any term in the residue series is greater than Su re- place it by its complementary number y — e. In this way, from the residue series, we get a derivative series dl, cZ2, c?3, ... such that any Su consecutive terms comprise all the integers from 1 to Su. The first half of this series may be divided into three equal divisions thus: (1) dly d^, dl, ... ; (2) d2, do, d8, ...; (3) dS, d6, d9, .... If the displacement is such that the first numbers in the second, third, and fourth columns are contained in different divisions, each difference must occur twice, and it will give a possible solution. Other possible regular arrange- ments give other solutions. Applying this to our case we have the residue series, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1. The derivative series is 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1. The three divisions are (i) 2, 3 ; (ii) 4, 6 ; (iii) 5, 1. The cyclical arrange- ment we started wdth and the consequent differences are shown in the left half of the accompanying table. A cyclical change
2. 4. 8
2
4
6
2. 6. 5
4
1
3
3. 6. 12
3
6
4
8. 9. 1
6
5
2
11. 9. 5
2
4
6
11. 7. 8
4
1
3
10. 7. 1
3
6
4
10. 4. 12
6
5
2
as described above of the vertical lines of the symbols in the first column gives the arrangement in the right half of the table. Here each difference occurs twice and accordingly this gives a possible arrangement of the triplets, namely, 2, 6, 5 ; 3, 9, 1 ; 11, 7, 8; 10, 4, 12. These are the sufBxes of the '6's. We have now to use six of these 'b's in connection with the basic * a 's already determined, keeping the other six ' b s for the remaining two triangles.
For instance we may obtain a scalene solution by taking as a suffix of the * h ' associated with any pair of * a 's, a number equal to the sum of the suffixes of the ' a 's. We thus get as a solution (a2. aS. 610), (a4>. aS. 67), (a6. all. 64), (al2. a9. 68), (ao. al. 612), (alO. al. 611), (62. 66. 6 5), (6 3. 69. 61), {k al3. 613). Or we might take as a suffix of the '6 ' associated with any pair of ' a's, the number midway between the suffixes
CH. ix] kirkman's school-girls problem 215
of the 'a's on the 13 circle. This gives the following solution, in which the first six triangles are isosceles: (a2. aS. h5), (a4. aS. 610), (a6. all. 62), (al2. a9. 64), (a5. a7. 66), (alO. al. 612), (63. 69. 61), (611. 67. 68), {k. al3. 613).
In the case of 27 girls, we may equally well represent the points by k at the centre of the circle and 26 equidistant points 1, 2,... 26 on the circumference. The points previously denoted by a and 6 with the suffix h are now denoted by the numbers 2h—l and 2h. Hence the basic pairs (2. 8), (4. 3), ...become (3. 15), (7. 5), (11. 21), (23. 17), (9. 13), (19. 1), and the corre- sponding scalene arrangement for the first day is (3. 15. 20), (7. 5. 14), ... {k. 25. 26). From this by a two-step cyclical permutation of the numbers, an arrangement for 13 days can be got.
The case of 27 girls can also be treated by the direct formation of triplets. The triplets must be such that each difference is represented twice, but so that the groups of differences are different. There are analytical rules for forming such triplets somewhat analogous to those I have given for forming basic pairs, but their exposition would be lengthy, and I will not discuss them here. One set which will answer our purpose is (1. 12. 5), (2. 3. 10), (4. 6. 9), (8. 11. 7), giving respectively the differences [2, 6, 4], [1, 6, 5], [2, 3, 5], [3, 4, 1]. Now every difference c? in a 13 circle will correspond to d or IS — d in a 26 circle, and every residue e in a 13 circle will correspond to e or 1'3 + e in a 26 circle. Further, a triplet in the 26 circle must either have tliree even differences, or one even and two odd differences. Hence from the above sets we can get the following arrangement for the first day, (1.25.5) and (14.12.18) with differences [2,6,4], (15.3.10) and (2. 16. 23) with differences [12, 7, 5], (17. 6. 9) and (4. 19. 22) with differences [11, 3, 8], (21. 11. 20) and (8. 24. 7) with differences [10, 9, 1], and {k. 13. 26). From this by either a one-step or a two-step cyclical permutation of the numbers, an arrangement for 13 days can be got. I will not go into further details about the deduction of other similar solutions. A similar method is always applicable when n is of the form 24m + 3.
216
KIRKMAN S SCHOOL-GIRLS PROBLEM
[CH. IX
The process by pairing when 3/ is a prime of the form 6u-\-l is extremely rapid. For instance, in the case of 15 girls we have n = 15, 3/ = 7, w = 1, a?= 5. The order of the residues is 5, 4, 6, 2, 3, 1. By our rule we can at once arrange basic pairs (5. 4), (6. 2), (3. 1). From these pairs we can obtain numerous solutions. Thus using scalene triangles as above explained, we get as an arrangement for the first day (a 5, a 4, 62), (a 6. a 2. 61), (a3. al. 64), (63. 65. 66), (k. al. 67), from which by a one-step cyclical permutation of the numbers, arrangements for the seven days can be obtained. Using the basic pairs as bases of isosceles triangles, we get as an arrangement for the first day (a5. a4. 61), (a6. a2. 64), (a3. al. 62), (63. 65. 66), {k. al. hi).
Again, take the case of 39 girls. Here we have n = 39, 2/= 19, i^=3, ^=3. The order of the residues is 3, 9, 8; 5, 15, 7;
2, 6, 18 ; 16, 10, 11 ; 14, 4, 12 ; 17, 13, 1. The basic pairs are (3. 5), (9. 15), (8. 7), (2. 16), &c. These are the sufiixes of the *a's. The possible triplets which determine what *6's are to be associated with these, and what ' 6 's are to be left for the remaining three triangles, can be determined as follows : From the residue series we obtain the derivative series
3, 9, 8, 5, 4, 7, 2, 6, 1, &c. The divisions are (i) 3, 5, 2; (ii) 9, 4, 6; (iii) 8, 7, 1. A cyclical arrangement like that given above leads to the result in the left half of the annexed table which does not satisfy our condition. A cyclical displacement of the symbols in the vertical lines in the first column leads to the arrangement given in the right half of the table, and shows
3. 9. 8
6
2
5
3. 15. 16
7
3
4
5. 15. 7
9
8
2
5. 6. 11
1
5
6
2. 6. 18
4
7
3
2. 10. 12
8
2
9
16. 10. 11
6
1
5
16. 4. 1
7
3
4
14. 4. 12
9
8
2
14. 13. 8
1
5
6
17. 13. 1
6
7
3
17. 9. 7
8
2
9
that (3. 15. 18), (5. 6. 11), &c. are possible triplets. From these results numerous solutions can be deduced in the same way as above. For instance one solution is (a 3. a 5. 64),
CH. ix] kirkman's school-girls problem 217
(a9. al5. 612), (aS. a1. hll), (a2. al6. 69), {aQ, alO. 68), (al8. all. 65), (al4. all. 66), (a4. al3. 618), (ttl2. al. 616), (63. 610. 61), (62. 613. 67), (614. 615. 611), (A;. al9. 619).
In the case of 39 girls we may also extend the method used above by which for 27 girls we obtained the solution (1. 25. 5), (14. 12. 18), .... We thus get a solution for 39 girls as follows: (1.25.18), (14.38.31), (27. 12. .5); (15.16.10), (28. 29. 23), (2. 3. 30); (17. 19. 35), (30. 32. 9), (4. 6. 22); (21. 24. 33), (34. 37. 7), (8. 11. 20); (13. 26. 39). From this the arrangements for the first 13 days are obtained either by a one-step or a three-step cyclical permutation of the numbers. The single triplets from each of which an arrangement for one of the other six days is obtainable are (1. 5. 15), (2. 6. 16), (3. 7. 17); (1. 9. 20), (2. 10. 21), (3. 11. 22). From each of these the arrangement for one day is obtainable by a three-step cyclical permutation of the numbers.
These examples of the use of the Focal and Analytical Methods are given only by way of illustration, but they will serve to suggest the applications to other cases. When the number taken as base is composite, the formations of the series used in the Analytical Method may be troublesome, but the principle of the method is not affected, though want of space forbids my going into further details. Eckenstein, to whom the development of this method is mainly due, can, with the aid of a table of primitive roots and sets of numbers written on cards, within half an hour obtain a solution for any case in which n is less than 500, and can within one hour obtain a solution for any case in which n lies between 500 and 900.
Number of Solutions. The problems of 9 and of 15 girls have been subjected to an exhaustive examination. It ha« been shown that all solutions of the problem of 9 girls are reducible to one type, and that the number of independent solutions is 840, where, however, any arrangement on Monday, Tuesday, Wednesday and Thursday, and the same arrangement on (say) Monday, Tuesday, Thursday and Wednesday are regarded as identical. [If they are regarded as different the number of possible independent solutions is 20,160.] The total number of
218 KIRKMAN'S school-girls problem [CH. IX
possible arrangements of the girls in triplets for four days is (280)Y4!; hence the probability of obtaining a solution by a chance arrangement is about 1 in 300,000.
All solutions of the problem of 15 girls are reducible to one of eleven types, distinguished by the number of cycles required for expressing them. The number of independent solutions is said to be 65 x(13!), but I do not vouch for the correctness of the result. The total number of ways in which the girls can walk out for a week in triplets is (455)'; so the probability that any chance way satisfies the condition of the problem is very small.
Walecki's Theorem. It should be noticed that Walecki — quoted by Lucas — has shown that if a solution for the case of n girls walking out in triplets for (n — l)/2 days is known, then a solution for Sn girls walking out for (3n — l)/2 days can be deduced.
For if an arrangement of the n girls Oi, ag, ..., a^ for (n— l)/2 days is known ; and also one of the n girls h^, h^, ...,&»; and also one of the n girls Ci, Ca, ..., Cn\ then obviously an arrangement of these 3n girls for (n — l)/2 days can be written down at once. A set of n triplets for another day will be given by ami>m+kCm+2k, where m is put equal to 1, 2, ..., n successivel3\ Here k may have any of the n values, 0, 1, 2, ..., (n — 1) ; but, wherever a suffix is greater than n, it is to be divided by n and only the remainder retained. Hence altogether we have an arrangement for (n — l)/2 + n days, i.e. for (Sn — l)/2 days. We might also form the known order of arrangements for (n — 1)/2 days for the three sets of girls, and then arrange the girls in triplets thus: (ci. a^. hn), (02- cl^. &n-iX ••• ('^n- ^7f &i)« from this, arrangements for n days can be obtained by one-step cyclical permutations of the a and h suffixes, keeping the c suffixes unchanged. Hence altogether we get, as before, arrangements for (ri — l)/2 + n days, i.e. for (8n — l)/2 days.
I have given solutions for all values of n less than 100. Other solutions for some of these values could also be found by Walecki's Theorem. By that theorem we can also write down
CH. ix] kirkman's school-girls problem 219
solutions for 3'"/i girls where n has any of the values given above.
Extension to n^ Girls. Peirce suggested the corresponding problem of arranging n^ girls in n groups, each group containing n girls, on w + 1 days so that no two girls will be together in a group on more than one day. We may conveniently represent the girls by a point k at the centre of a circle and n^ — 1 equi- distant points on the circumference.
When ?i = 2, we may arrange initially the 4 points in two pairs, one pair consisting of k and one of the points, say, 3, and the other pair of the remaining points (1. 2). These two pairs give the arrangement for the first day. From them, the solu- tion for the other day is obtained b}- a one-step cyclical permutation.
When n = 3, we may arrange initially the 9 points in three triplets, namely, k and the ends of a diameter {k. 4. 8) ; a triangle (1. 2. 7) ; and the same triangle rotated through 180°, thus occupying the position (5. 6. 3). These three triplets give an arrangement for the first day. From them the solutions for the other days are obtained by one-step cyclical permutations.
When n = 4, we may arrange initially the 16 points in four quartets, namely, k and three equidistant points, (k. 5. 10. \o); a quadrilateral (1. 2. 4. 8) ; the same quadrilateral rotated through 120° and 240°, thus occupying the positions (6. 7. 9. 13) and (11. 12. 14. 3). These four quartets give an arrangement for the first day. From them the solutions for the other days are obtained by one-step cyclical permutations.
When n = 5, we may arrange initially the 25 points in five quintets, namely, k and four equidistant points, (/j. 6. 12. 18. 24); a pentagon (2. 3. 5. 13. 22) ; the same pentagon rotated through 90°, 180°, 270°, thus occupying the positions (8. 9. 11. 19. 4), (14. 15. 17. 1. 10), (20. 21. 23. 7. 16). These five quintets give an arrangement for the first day. From them the solutions for the other days are obtained by one-step cyclical permutations. There is a second solution (k 6. 12. 18. 24), (1. 2. 15. 17. 22), &c.
Hitherto the case when n — (j has baffled all attempts to find a solution.
220
KIRKMAN S SCHOOL-GIRLS PROBLEM
[CH. IX
When 72 = 7 we may initially arrange the 49 points in seven groups namely {k. 8. 16. 24. 32. 40. 48), a group (1. 2. 5. 11. 31. 36. 38) and the same group rotated through 60°, 120°, 180°, 240°, 300°. There are three other solutions: in these the second group is either (2. 3. 17. 28. 38. 45. 47), or (3. 4. 6. 18. 23. 41. 45), or (3. 4. 14. 17. 26. 45. 47).
When n = 8 there are three solutions, due to Eck en stein. If the first group is {k. 9. 18. 27. 36. 45. 54. 63), the second groupiseither(1.2.4.8.16.21.32.42), or (2.3.16.22.24.50.55.62), or (3. 4. 7. 19. 24. 26. 32. 56): the other groups in each solution heing obtained by successive addition of 9 to the number in the second group.
When n is composite no general method of attacking the problem has been discovered, though solutions for various par-
kl, k2, kn.
al, a2, an.
61, 62, bn.
kl, al, 62, c3,
k2, a2, 64, c6,
kS, a3, 66, c9,
kn, an, bn, en,
Arrangement on First Day
Arrangement on Second Day
ticular cases have been given. But when n is prime, we can proceed thus. Denote the n^ girls by the suffixed letters shown in the left half of the above table. Take this as giving the
kl, k2, kd, fe4, ko, fc6, kl.
al, a2, a3, a4, a5, a6, al.
61, 62, 63, 64, 65, 66, 67.
cl, c2, cB, c4, c5, c6, c7.
dl, d2, d3, d4, do, dQ, dl.
el, e2, eS, e4, e5, e6, el.
fh /2, /3, /4, /5, /6, fl.
Arrangement on the First Day
I
kl, al, 62, c3, d4, eo, /6.
k2, a2, 64, c6, dl, e3, /5.
^•3, aS, 66, c2, do, el, /4.
fe4, a4, 61, c5, d2, e6, /3.
fc5, a5, 63, cl, d6, e4, /2.
k6, a6, 65, c4, d3, e2, fl.
kl, al, hi, cl, dl, el, fl.
Arrangement on the Second Day
arrangement on the first day. Then on the second day we may take as an arrangement that shown in the right half of the
CH. ix] kirkman's school-girls problem 221
table. From the arrangement on the second day, the arrange- ments for the other days are obtained by one-step cyclical permutations of the suffixes of a, b, &c.; the suffixes of A; being unaltered. An example will make this clearer. For instance, when n = 7 the rule gives the arrangements for the first and second days shown in the second table.
Kirkmans Problem in Quartets. The problem of arranging 4??i girls, where m is of the form 3n + 1, in quartets to walk out for (4/Ai,— 1)/3 days, so that no girl will walk with any of her school-fellows in any quartet more than once has been attacked. Methods snuilar to those given above are applicable, and solu- tions for all cases where m does not exceed 31, have been written out. Analogous methods seem to be applicable to corresponding problems about quintets, sextets, &c.
Bridge Problem. Another analogous question is where we deal with arrangements in pairs instead of triplets. One problem of this kind is to arrange 4m members of a bridge club for 4m — 1 rubbers so that (i) no two members shall plav toofether as partners more than once, and (ii) each member shall meet every other member as opponent twice. The general theory has been discussed by E. H. Moore. To obtain cyclic solutions we may proceed thus. Denote the members by a point k at the centre of a circle and by 4?7i — 1 equidistant points, numbered 1, 2, 3, ... on the circumference. We can join the points 2, 3, 4, ... by chords, and these chords with {k. 1) give possible partners at the m tables in the first rubber. A one-step cyclical permutation of the numbers will give the arrangements for the other rubbers if, in the initial arrangement, (i) the lengths of the chords representing every pair of partners are unequal and thus appear only once, and (ii) the lengths of the chords representing every pair of opponents appear only twice. Solutions have been published for several values of m. In the following examples for m = 2, 3, 4, 10, I give an arrangement of the card tables for the first rubber : the arrangements for the subsequent rubbers being thence obtained by one-step cyclical permutations of the numbers. If 7?i=2, such an initial arrangement is {k. 1 against 5. 6) and (2. 4 against 3. 7). If m = 3, one such initial
222 kirkman's school-girls problem [ch. ix
arrangement is (k. 1 against 5. 6), (2. 11 against 3. 9) and (4. 8 against 7. 10). If m = 4, such an inibial arrangement is {k. 1 against 6. 11), (2. 3 against 5. 9), (4. 12 against 13. 15), and (7. 10 against 8. 14). One example of a higher number will suffice; if m = 10 such an initial arrangement is (k. 1 against 14. 27), (2. 9 against 26. 6), (3. 17 against 12. 11), (5. 33 against 23. 21), (15. 39 against 19. 22), (16. 25 against 24. 30), (18, 36 against 34. 7), (28. 32 against 35. 13), (29. 37 against 4. 38) and (31. 8 against 20. 10). In some cases there are also solutions not reducible to single cycles.
Sylvesters Corollary. To the original theorem J. J. Sylvester added the corollary that the school of 15 girls could walk out in triplets on 91 days until every possible triplet had walked abreast once, and he published a solution in 1861.
The generalized problem of finding the greatest number of ways in which co girls walking in rows of a abreast can be arranged so that every possible combination of b of them may walk abreast once and only once has been solved for various cases. Suppose that this greatest number of ways is y. It is obvious that, if all the cc girls are to walk out each day in rows of a abreast, then x must be an exact multiple of a and the number of rows formed each day is oo/a. I confine myself to these cases. If such an arrangement can be made for z days, then we have a solution of the problem to arrange x girls to walk out in rows of a abreast for z days so that they all go out each day and so that every possible combination of h girls may walk together once, and only once.
An example where the solution is obvious is if a; = 2n, a— 2, 6 = 2, in which case 3/ = ?i(27i — 1), z=2n — \. If we take the case a; =15, a = 3, 6=2, we find 3/ =35; and it happens that these 35 rows can be divided into 7 sets, each of which contains all the symbols ; hence ^=7. More generally, if a?= 5 X 3'^ a = 3, 6= 2, we find y = ^{x-\)ftx, z=-{x-\)l2. It will be noticed that in the solutions of the original fifteen school-girls problem and of Walecki's extension of it given above every possible pair of girls walk together once ; hence we might infer that in these cases we could determine z as well as y.
CH. ix] kirkman's school-girls problem 223
The results of the last paragraph were given by Kirkman in 1850. In the same memoir he also proved that, if x=9, (X=3, b = o, then y = 84, ^ = 28; and if x=lo, a = 3, 6 = 3, 2/ =455, ^ = 91, but some of the extensions he gave are not correct. He showed, however, how 9 girls can be arranged to walk out 28 times (say 4 times a day for a week) so that in any day the same pair never are together more than once and so that at the end of the week each girl has been associated with every possible pair of her school-fellows. Three years later he attacked the problem when x — 2^\ a = 4, 6=3, but his analysis is open to objection. In 1867 S. Bills showed that if 57 = 15, a = 3, 6 = 2, then y = 35: and the method used will give the value of y, if a;=2'*— 1, a =3, 6=2. Shortly afterwards W. Lea showed that if a; =16, a =4, 6 = 3, then y= 140. These writers did not confine their discussion to cases where x is an exact multiple of a.
Steiner's Problem. I should add that Kirkman's problem, but in a somewhat more general form, was proposed independently by J. Steiner in 1852, and, as enunciated by him, is known as Steiners Combinatorische Aufgabe. In substance Steiner sought to find for what values of n it is possible to arrange n things in triplets, so that every pair of things is contained in one and only one triplet: any triplet forming part of such an arrangement is called a triad. Also, if ?i is a number for which such an arrangement can be formed, he asked whether there are other arrangements that cannot be obtained from it by permutations of the things. Other problems proposed by him are as follows. When such an arrangement of triads has been made, is it possible to arrange the n things in sets of four, called tetrads, so that no one of the triads is contained in any tetrad, but every triplet which is not a triad is contained in one and only one tetrad ? And generally when an arrangement in ^^-ads has been made, is it possible to arrange the things in sets of k -{- 1-ads so that no /i-ad, where ^ :|> A:, is obtained in a A; + l-ad, and so that every A;-let tliat is not or does not contain an /i-ad is contained in one and only one k-v 1-ad ?
224