Kirkman's Schoolgirl Problem

Glad Kirkman knows he's the one with the problem.

In a boarding school there are fifteen schoolgirls who always take their daily walks in rows of threes.  How can it be arranged so that each schoolgirl walks in the same row with every other schoolgirl exactly once a week?  

[Heinrich Dörrie; 100 Great Problems of Elementary Mathematics] 

Kirkman originally posed the problem in 1850, in the Lady's and Gentleman's Diary, a yearly repository of mathematical puzzles and bad poetry about them.

Boxy McGee has found the general solution, and two particular solutions:

A superabundance of solutions!

The puzzle blocks are general; the cards and the hanging pentagon are particular solutions.  Now, about solving it.  I need a mental picture. Let me try the question again.

In a certain town of G---- the Abbess is strict.  The 15 girls are left alone only for their daily walks, which they may take in any of five gardens and woods.  Three girls may visit any one location at a time.  When all the girls go out, they make five trios, and each trio visits a different wood. 
The girls may walk with whomever they wish, but they must submit a schedule to the Abbess in advance.
It happens that Sister Agnès has made an arrangement with Guillot, a strong and beautiful young man whose face was well known and liked by all the girls.  She devised the following ruse.  Every day of the week, Guillot will wait in a certain kingcup field, where the girls often dally out of sight of the Abbess.  Here, he will trade places with Agnès.  He will take her habit, and number of other things she has meant to give him for some time.  She will take his day-clothes, and a number of other things he has earnestly tried to give her, and enjoy an afternoon in town.  He will then take her place, and two girls will enjoy his company in the woods.  On the return trip, the girls will stop at the same spot, and the two will again trade places.  
In this way, for the duration of the week Agnès will have the pleasure of Guillot's company twice a day, going and coming.  In addition, one of the five rows of girls, being now two girls and Guillot, will enjoy a number of hours in a secluded wood.
Now, the girls are jealous of their prize, and eager.  None wishes to be left out, and they cannot decide who shall strip him of trousers twice in the kingcups, and who shall be contented to walk with their young Adonis, and un-dress him in the woods.
Agnès is a sly fox.  See what she has done.  The week prior, she submitted a special schedule to the Abbess in which all 15 girls go out every day of the week. Then, into a hat she placed the fifteen names of the girls, each on a separate slip of paper.  Out of the hat, a single name will be drawn at random.  This name is the one who Guillot will replace for the duration of the week, who shall have him twice daily in kingcup fields.
Agnès' claim to the girls is this: she had arranged the schedule so that no matter which name is to be drawn out of the hat,  each of the remaining fourteen girls will walk in the same row as Guillot exactly once during the week.
To which the girls agree, and it is done, and they are done, there is a great deal of having and doing, and the Old Sister is never more satisfied with the fervor and sincerity of the pleading cries of her young lambs, which fill the valley for seven gold days in of spring.
Eight of the girls become pregnant that winter, are mercifully beaten and thrown into the streets.

The question remains. How did Agnès do it?

THE SOLUTION

Notes:
1) This is not a problem of combinatorics. How many ways are there? is a different question.
2)  This is not a system of 15 linear equations.  5 girls, 3 rows, 7 days, no repetitions are all constraints which limit the solution.  How many independent variables are there? is part of the question.
3) Call Day 1 Sunday.  Each girl may return to the same position the following Sunday.
4) Say each girl walks a path with seven stops and the last stop returns to the first.  But then we need six more girls to fill the remaining stops.  Can the girls be divided up this way? (Yes. For this problem it works very well.  The solution space is cyclic, and very small).

I: SUBSTITUTION

The problem is the same if a stranger takes the place of any one of the girls.  To me, this is the crux.  We can impose a series of limitations without changing the question.  It is surprisingly difficult to check the restrictions for consistency.  Does it throw out any valid solutions?  Substitution is not necessary.  But if the first constraint is, 'we may choose an arbitrary girl as a fixed frame of reference',  this can be double-checked by a simple substitution: can Guillot take the place of any one of the girls, chosen at random?  Yes.

So, set a frame of reference, and move the other girls around it. Choose a symbol for this person, put it somewhere obvious, and don't move it.  Dörrie uses *, and puts it in the middle of a row.  I choose row 1, and refer to her as the Joker.  Hence,

(1)    Row 1 will always be    − *  −

II. PARTITION; SUITS

Each day, two different girls walk with the Joker in row 1.  A total of seven girls will pass through Row 1 on her left, and seven on her right.  Hand each of these girls a playing card.  Girls on the left are given Diamonds.  Girls on the right, Spades.  Hand out the Ace through 7 of each suit, in order:
     On Sunday, give out the Aces.
     On Monday, give out the 2's.
     On Tuesday, the 3's, and so on.
Now, consider the first day, Sunday.  We have

(2)     Row 1, Sunday:     ◊A * ♠A

Arrangement of Suits:

12 girls hold among them the 2-7 of Diamonds and Spades, arranged in 4 rows.  What can we say about them?  There are four cases:
              1                 2                 3                  4    
          ◊  *  ♠          ◊   *  ♠          ◊  *   ♠          ◊  *  ♠
          ◊  ◊  ◊          ◊  ◊  ◊          ◊  ◊  ♠          ◊  ◊  ♠ 
          ◊  ◊  ◊          ◊  ◊  ♠          ◊  ◊  ♠          ◊  ◊  ♠  
          ♠  ♠  ♠          ◊  ♠  ♠          ◊  ◊  ♠          ◊  ♠  ♠ 
          ♠  ♠  ♠          ♠  ♠  ♠          ♠  ♠  ♠          ◊  ♠  ♠ 
Any other permutation can be turned into one of these four by changing the order of the rows and rearranging the cards within a row, which do not affect the solution.  Each girl occupies a different position every day: a Diamond will visit every square on the graph labeled with a diamond.  Each day, each girl walks with 2 others.  In seven days, she has 7*2=14 partners.  They must be:
     The joker,
     the 6 other girls in the same suit
     the 7 girls in the opposite suit.


Case 1:  A Diamond walks with
  - the Joker and 1 ♠
  - (2 rows) *(2 ◊ per row) * (3 visits to each row) = 12 ◊
And likewise for a spade.  Throw out Case 1.

Case 2:  The two suits still do not meet often enough.  Throw out Case 2.

Case 3:  A Diamond walks with
      - the Joker and 1 ♠
      - (3 rows) * (1 ♠  per row) * (2 visits) = 6 ♠
   And in those same rows
      - (3 rows) * (1 ◊  per row) * (2 visits) = 6 ◊
A Spade walks with
      - the Joker and 1 ◊
      - (3 rows) *  (2 ◊ per row)  *  (1 visit) = 6 ◊
      - (1 row)  *  (2  ♠ per row) * (3 visits) = 6 ♠
 Case 3 Satisfies the conditions.

Case 4: Girls in the same suit do not meet often enough. Opposite suits meet too often.  Throw out Case 4.

• Case 3 is the only valid case.  We must have

It it, alas, easier to arrange the remaining information in a satisfactory way using

III. MODULO ARITHMETIC

We need to count by sevens.  Gauss to the rescue.
DEFINITION:  A is congruent to B modulo 7 if the difference A−B is divisible by seven.
          A   ≡  B  mod 7     if      (A−B)  =  7n ,       n any integer.

Do not stare directly into the abstraction!  This is how we count days:  7, 14, 21... days from now it will be the same day of the week as today, which is 0 days away:
          7 ≡  14  ≡  21 ...  ≡  0 mod 7
The definition arises on its own in the context of the problem.

                    Sun     Mon    Tues     Wed      Thur      Fri       Sat      Sun 

                      1         2           3           4           5          6          7      8≡1

Beginning with Sunday, assign the numbers 1-7 to the days of the week.  Say today is Sunday. In two days it will be Tuesday.  Five days ago it was also Tuesday.  Counting days is a circle:

Pick any position on the circle, x.  Add clockwise, subtract counterclockwise.  The following hold no matter where we start:

(3)     Adding or subtracting a multiple of seven lands on the same position, x.
               x + 7n ≡ x       (Any multiple of seven days away is the same day of the week)
          Adding 1 is equivalent to subtracting 6
               x + 1 ≡ x − 6     (Tomorrow is the same day of the week as six days ago)
          Adding 2 is equivalent to subtracting 5, and so on
               x + 2 ≡ x − 5
               x + 3 ≡ x − 4
               x + 4 ≡ x − 3
               x + 5 ≡ x − 2
               x + 6 ≡ x − 1
Where '≡' is read 'equivalent to' or 'congruent to'.  Here, it means "the same day of the week as".

We can also count the distance between any pair of days.  Consider the following diagrams:

 The Red block covers a pair of numbers 1 step apart.  The green pair are 2 numbers apart, and the blue  are 3 apart.  What can we say about them?
      • Any pair of days we choose can be covered by one of the three pieces.  Invariably,
           A difference of ±1 and ±6 refer to the Red piece
           A difference of  ±2 and ±5  refer to Green
           A difference of  ±3 and ±4  refer to Blue
     •  The list of congruences (3) becomes
             x − 1 ≡ x + 6,        x − 6 ≡ x + 1
             x − 2 ≡ x + 5,        x − 5 ≡ x + 2
             x − 3 ≡ x + 4,        x − 4 ≡ x + 3
Each piece is uniquely identified by one of the three differences ±1, ±2, ±3.

IV. DISTANCE

DEFINITION: The distance between a pair of girls in a row is one of the three differences ±1, ±2, ±3.

Each day, the girls trade places: Each moves to the next lowest number in her suit.  The ◊A takes the place of the ◊7, who takes the place of ◊6, ... and the ◊2 moves to the place vacated by ◊A.  The girls walk in a loop  ◊A. . . ◊7.  How can we add this loop to the diagram?

Consider the following arrangement:

         Sunday       Monday         Tuesday        Wednesday

        A   *    ♠         ◊2   *    ♠        ◊3  *     ♠         ◊4   *    ♠
       ◊2  ◊4   ♠        ◊3  ◊5   ♠        ◊4  ◊6   ♠        ◊5  ◊7   ♠

       ◊3  ◊5   ♠        ◊4  ◊6   ♠        ◊5  ◊7   ♠        ◊6   A   ♠     . . .
       ◊6  ◊7   ♠        ◊7   A   ♠         A  ◊2   ♠         ◊2  ◊3   ♠
        ♠    ♠    ♠        ♠    ♠    ♠         ♠    ♠    ♠          ♠    ♠    ♠

The Diamonds in rows 2 and 3 are the same distance apart:
     ◊4 − ◊2 =  ◊5 − ◊3 = 2.  In other words:
 The highlighted rows are repeated from the day before.  If the distance between a pair of diamonds in a row is x.  Each girl walks in that row twice, once with the girl x steps in front of her and x steps behind her.

• Example: The expression 5 ±2  refers to both 3 and 7.  ◊5 appears...-in row 2 on Monday and Wednesday, with the ◊3 and the ◊7, and-in row 3 on Sunday and Tuesday, again with the ◊3 and the ◊7.

The pair of diamonds in each row must be a different distance apart.

V. DIAMONDS

• Rule: If we can arrange the 6 cards ◊2, ◊3, ◊4, ◊5, ◊6, ◊7  so that the cards in rows 2, 3 and 4 are ±1, ±2 and ±3 steps apart, respectively, then the seven Diamonds will walk with one another only once.  Thus we have

Any way the Red, Green, and Blue pieces can be assembled, is a valid solution.  Remembering that one of the places is fixed by the Ace,

...one last constraint arises for the Diamonds: if the Red piece is placed next to the Ace, it is no longer possible to fit both the Green and Blue pieces. This leaves only three possible locations for the Red piece: (◊3 ◊4), (◊4 ◊5), (◊5 ◊6) each of which uniquely determines the Green and Blue pieces.

         ◊3 ◊4            ◊4 ◊5           ◊6 ◊5 
         ◊5 ◊7            ◊7 ◊2           ◊4 ◊2  
         ◊6 ◊2            ◊3 ◊6           ◊3 ◊7

If we count backward in the third case: 7-6-5-4-3-2, we visit the same places, in the same order, as counting forward in the first. Paths I and III are identical. This is a result of the rule, a difference of ±1 and ± 6 refers to the same row; a difference of ±2 and ±5, & c.  
For the numbers 1-7, reversing the direction requires an offset:
     x' ≡  2 − x
Which turns path 1 in to path 3:
           ◊3 ◊4          ◊(-1) ◊(-2)              ◊6 ◊5 
   2 −   ◊5 ◊7   =     ◊(-3) ◊(-5)      ≡     ◊4 ◊2  
           ◊6 ◊2          ◊(-4) ◊( 0)              ◊3 ◊7

The second case is its own mirror image.  Reversing the direction has no effect.  Dressing them up in smart woolen vests does.  It keeps them warm.  Thus we have for the Diamonds

• The arrangement of diamonds in rows 2, 3, 4:
             ◊4 ◊i
             ◊7  ◊j
             ◊6 ◊k
  Case  I:       i, j, k = (3, 5, 2)
  Case II*:    i, j, k = (5, 2, 3)

VI. SPADES

Again, we are only concerned with the values 2-7.  The Ace has already been used, the inequality x ≠ 1, for any Spade x, is a constraint on all that follows.  Labeling the remaining six spades B - G, we have

ROW 5:
All of the Spades meet each other in the fifth row, so the distances between all 3 girls E, F, G must be different.

    E − F ≡ ±1     (E and F are 1 step apart)

    F − G ≡ ±2    (F and G are 2 steps apart)

    E − G ≡ ±3    (E and G are 3 steps apart)
With three girls in the same suit, we must resolve the ± sign.  For simplicity, I have arranged E, F, and G so that the equations are only satisfied if the three differences are all the same sign.  This is easier to see with a diagram:

E, F, G are clockwise: 2, 3, 5

Flip the piece over and E, F, G are counterclockwise, in order.  

Thus we have two possibilities for the last row:

(E, F, G)  ≡ (E, E+1, E+3)   or  (E, E−1, E−3)

ROWS 2-4:

In addition, a Spade must meet six different diamonds when visiting B, C, D: the differences between the three girls in rows 2-4 must all be different. Consider Case I:
     ◊4 ◊3  B
     ◊7 ◊5  C
     ◊6 ◊2  D
The six differences, B−◊4,  B−◊3,  C−◊7,  C−◊5,  D−◊6,  D−◊2  must all be mutually incongruent, modulo 7.  We can rewrite the inequalities
     B−x ≠ C−y              C ≠ B − x + y 
     C−y ≠ D−z      as     D ≠ C − y + z 
     B−x ≠ D−z              D ≠ B − x + z 
where x, y, z are Diamonds in rows 2, 3, and 4 respectively.  In addition, a spade and a diamond in the same row cannot have the same number, because they already meet in the first row with the Joker.  So we add the inqualities
     B ≠ x,   C ≠ y,   D ≠ z

Proceeding in this way... {Click to show the details}

      C ≠ B+2     (C ≠ B − ◊3 + ◊5)
      C ≠ B+4     (C ≠ B − ◊3 + ◊7)
      C ≠ B+1     (C ≠ B − ◊4 + ◊5)
      C ≠ B+3     (C ≠ B − ◊4 + ◊7)
      C ≠ B         
(a)  C ≡ {B+5,  B+6}

      D ≠ C+4     (D ≠ C − ◊5 + ◊2)   (and  -3 ≡ 4)
      D ≠ C+1     (D ≠ C − ◊5 + ◊6)
      D ≠ C+2     (D ≠ C − ◊7 + ◊2)        (-5 ≡ 2)
      D ≠ C+6     (D ≠ C − ◊7 + ◊6)        (-1 ≡ 6)
      D ≠ C         
(b)  D ≡ {C+3,  C+5}

      D ≠ B+6     (D ≠ B − ◊3 + ◊2)        (-1 ≡ 6)
      D ≠ B+3     (D ≠ B − ◊3 + ◊6)
      D ≠ B+5     (D ≠ B − ◊4 + ◊2)        (-2 ≡ 5)
      D ≠ B+2     (D ≠ B − ◊4 + ◊6)
      D ≠ B         
(c)  D ≡ {B+4,  B+1}

When C ≡ B+5                      When C ≡ B+6
    (b)  D ≡ {B+1, B+3}            (b)  D ≡ {B+2, B+4}
    (c)  D ≡ {B+4,  B+1}           (c)  D ≡ {B+4,  B+1}
          D ≡ B+1                               D ≡ B+4

Hence,

For a given value of B, we have:
       (B, C, D) ≡ (B, B+5, B+1) and  (B, B+6, B+4).
With the constraints  B ≠ x,   C ≠ y,   D ≠ z:
       B ≠ 1, 3, 4;  C ≠ 1, 5, 7;  D ≠ 1, 6, 2

Test the remaining possible values of B:  2, 5, 6, 7.
      (B, B+5, B+1):         (B, B+6, B+4):
      (2,  2+5, 2+1)           (2,  2+6, 2+4) 
      (5,  5+5, 5+1)           (5, 5+6,  5+4)        ≡ (6, 4, 7) and (7, 6, 4)
      (6,  6+5, 6+1)           (6,  6+6, 6+4) 
      (7,  7+5, 7+1)           (7,  7+6, 7+4)
Using only the numbers 4, 6, 7.  The other triplet (2, 3, 5) satisfies the equations for E, F, G.  Hence,

SPADES, Case I:
     (B, C, D) ≡ (6, 4 ,7) and (7, 6, 4)
     (E, F, G)  ≡ (2, 3, 5)

Following the same procedure, we obtain for  Case  II: 

     (B, C, D)  ≡  (B, B+1, B+3) or  (B, B+6, B+4)
     (B, C, D)  ≡  (2, 3, 5) and (7, 6, 4)
There is only one solution here. (2, 3, 5), and (7, 6, 4) are the same path, traveling in opposite directions.  If we choose (B, C, D) ≡ (7, 6, 4) the values for (E, F, G) are identical for both Case I and II.  Hence, we have

SPADES, Case II*:
     (B, C, D)  ≡ (7, 6, 4)
     (E, F, G)   ≡ (2, 3, 5)

PART SEVEN: THE REVENGE

At this point, a crucial question arises.  Why are you still reading this?  I accept the precipitous descent: I have been ruined by mathematics. I am a slut for math.  I wake early and nuzzle her skirttails.  If you are reading these words, perhaps you, too, have a problem.

oh hell. on with the solution.

The problem is now solved.  The general solution is:

with only three possible arrangements, in two cases:

Case I:

     i, j, k ≡ (3, 5, 2)

     B, C, D ≡ (6, 4, 7) and (7, 6, 4)

Case II*:

      i, j, k ≡ (5, 2, 3)

     B, C, D ≡ (7, 6, 4) 

where, in the first case, if one suit proceeds in the reverse direction, the other must as well;

whereas in the second case, Diamonds and Spades may proceed in either direction, independently of one another.  Thus the solution reduces to the question how to arrange for arbitrary girls i, j, and  k to meet once each with  {B, C, and D}.   Of course, Kirkman's way of asking is more prettily dressed.