## Kirkman's Schoolgirls

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

### Kirkman's Schoolgirls

Given this puzzle dates from 1850, I assumed it had been posted here before, but I wouldn't know what to search for, and nothing I tried found it. If someone knows it is here and can link it, please lock this thread.

The Lady's and Gentleman's Diary, 1850, p. 48 wrote:Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast.

I don't know the answer myself.

SDK
Posts: 697
Joined: Thu May 22, 2014 7:40 pm UTC

### Re: Kirkman's Schoolgirls

Spoiler:
Seems pretty simple. Five rows of three means each individual walks abreast of two others each day. With fourteen others total, there's your seven days!

Treat it like probability, looking at the possible permutations first for the ladies in row 1 (there are six permutations, pulling from rows 2&3, 2&4, 2&5, 3&4, 3&5, and 4&5). That applies for ladies 1, 2 and 3, so let’s do them first, filling in our first three rows for each group.

1 2 3
4 5 6
7 8 9
10 11 12
13 14 15

1 4 7
2 6 13
3 10 14

1 5 12
2 7 11
3 8 13

1 6 13
2 8 15
3 9 12

1 9 10
2 12 14
3 6 11

1 8 14
2 5 10
3 4 15

1 11 15
2 4 9
3 5 7

That all looks good, but when I tried to fill in the last two rows, I got a bit of overlap. There must be some optimized permutation choices for ladies 2 and 3 that leaves you with a good set of numbers to work with for the last two rows. I’m not smart enough to know what that is, but I’m sure I could get this given another hour of guess and check anyway.
The biggest number (63 quintillion googols in debt)

MOJr
Posts: 12
Joined: Mon Sep 07, 2015 5:43 pm UTC

### Re: Kirkman's Schoolgirls

I was able to get it to five days.

Spoiler:
Lets arrange the girls to 5 by 3 matrix:

1 6 11
2 7 12
3 8 13
4 9 14
5 10 15

you can now just slide the 2nd colum by 1 and 3rd colum by 2 so you guarantee they never repeat.

1 7 13
2 8 14
3 9 15
4 10 11
5 6 12

1 8 15
2 9 11
3 10 12
4 6 13
5 7 14

1 9 12
2 10 13
3 6 14
4 7 15
5 8 11

1 10 14
2 6 15
3 7 11
4 8 12
5 9 13

But in the end you end up with non used triplets that you could theoretically use but you don't have enough of them to make one day.
It seams there should be a solution for 7, but I would probably have to brute force it, and it would be a different kind of solution.

Also SDK you have a mistake there:
Spoiler:
U use both:
2 6 13 and 1 6 13

Reydien
Posts: 2
Joined: Sat Feb 05, 2011 9:55 pm UTC

### Re: Kirkman's Schoolgirls

I think I have a solution.

Spoiler:
I used 0-9 and A-E to note the girls, mostly cause working with single-character items was easier

Code: Select all

`05A   06C   07E   0B7   0C9   D08   E0916B   17D   18A   1C8   1D5   E19   A1527C   28E   29B   2D9   2E6   A25   B2638D   39A   35C   3E5   3A7   B36   C3749E   45B   46D   4A6   4B8   C47   D48`

As for a somewhat winded explanation of my methods:

Spoiler:
It's kind of similar to MOJr's approach, which some modifications. I am essentially sliding the 3 columns up or down, but also swapping the columns too to make things fit.

There were a couple tricks I used to simply the process of finding working sets.

The first trick was keeping the 5 girls in a column together, and just sliding them up or down: what happens is that either all of the pairs between two columns are new or none of them are, so you don't have to check all 10 pairs. You can just check the top row against previous days (or just against the previous days' top row pattern, even) which greatly speeds things up.

The second trick was realizing that you could use permutation to make the first trick even stronger. You can swap two rows or two columns around and it doesn't affect any of the pairs, which means you can pick one set of 5 girls and always keep them in the same order, and either on the left row or the middle row. For my sets I kept the 0-4 girls in order.

Also as a side note, I think it's worth pointing out that the set in the middle uses twice as many pairings per day, so swapping out which set of girls is in the middle minimizes how many total pairs each girl has. 7 days means two days in the middle for two of the sets, and three days in the middle for one of the sets.

Using the two tricks means I basically started with the following seven strings

0XY
0XY
0XY
0YX
0YX
Y0X
Y0X

Where 0 is the first girl in the first column, X would be the second column of girls, and Y would be the third column of girls. From there I filled in unique pairs with the 0 girl.

05Y
06Y
07Y
0BX
0CX
D08
E09

That just leaves five XY pairs to align. I initially made a mistake here though, because I was in the mindset of matching a 0-X style pair, so I did something like 05A and 06B, not realizing the 6B pair would show up in the 05A set. That's easy enough to catch though, and it should be pretty clear there's enough sets of pairs for the remaining 5 slots (the 5A, 5B, 5C, 5D, 5E sets of pairs).

05A (5A set)
06C (5B set)
07E (5C set)
0B7 (5E set)
0C9 (5D set)
D08
E09

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Kirkman's Schoolgirls

Reydien wrote:I think I have a solution.

Spoiler:

Code: Select all

`05A   06C   07E   0B7   0C9   D08   E0916B   17D   18A   1C8   1D5   E19   A1527C   28E   29B   2D9   2E6   A25   B2638D   39A   35C   3E5   3A7   B36   C3749E   45B   46D   4A6   4B8   C47   D48`

Note that 'abreast' in the original problem does not necessarily mean adjacent in a triplet. What is meant is that no pair of schoolgirls should ever occur in more than one triplet.
Your solution fails therefore as you have 4B8 and D48, so 4 and 8 occur twice. Similarly 4 and D in 46D and D48.

Edit: In case you are wondering, this problem really does have solutions, and there is some deep mathematics behind it.

emlightened
Posts: 42
Joined: Sat Sep 26, 2015 9:35 pm UTC
Location: Somewhere cosy.

### Re: Kirkman's Schoolgirls

As it happens, each schoolgirl must walk abreast with each other schoolgirl exactly once. (3*5-1=14 other schoolgirls; 2*7=14 different abreast schoolgirls)

This problem looks very hard, so I'll leave it for now.

"Therefore it is in the interests not only of public safety but also public sanity if the buttered toast on cats idea is scrapped, to be replaced by a monorail powered by cats smeared with chicken tikka masala floating above a rail made from white shag pile carpet."

Sandor
Posts: 179
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Kirkman's Schoolgirls

jaap wrote:In case you are wondering, this problem really does have solutions, and there is some deep mathematics behind it.

There is at least one solution (plus lots of permutations of it) that can be found fairly quickly by hand, given the right approach.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Kirkman's Schoolgirls

Hi,

It is a Steiner system. You can find the solution here :

http://www.ccrwest.org/cover/t_pages/t2 ... 5_3_2.html

Just group the triplets such as for 5 triplets no number is used twice then 5*7=35.

Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

### Re: Kirkman's Schoolgirls

I have no life spent a solid 12 hours of my weekend working out a solution by hand and writing it up. I came up with my own approach instead of using Google, so it might be an interesting read.

Spoiler:
The question is equivalent to finding 7 unique 5 x 3 matrices of girls such that every pair of girls is only together in exactly one row of exactly one of the matrices. Let a set of 7 matrices that satisfies these constraints be defined as a particular set of solutions, or PSS.

Because rows and columns can be swapped around within a matrix without changing the solution it represents, we need to establish a point of reference to make it easier to distinguish different matrices.
Arrange the matrices in the PSS into a random permutation {M1,M2,…,M7}. Define the “Pivot” (Pv) as the element occupying the (1,1) position of M1. Every one of the other 6 matrices can be manipulated (using row and column swaps) to place Pv at the top left. Thus, every matrix in a PSS has this form:

Code: Select all

`Pv ?? ???? ?? ???? ?? ???? ?? ???? ?? ??`

Simplifying the Problem
Given a PSS in some permutation, let T1 be the transformation that maps M1 to M2. Likewise, let T2 be the transformation that maps M2 to M3, T3 maps M3 to M4, etc.
In the general case, for any permutation of any PSS, we have:
{M7 = (T6)…(T2)(T1)M1, M5 = (T5)…(T2)(T1)M1,…, M2 = (T1)M1}
However, due to the symmetric nature of the problem, there is good reason to believe there’s at least one PSS with T1 = T2 = T3 = T4 = T5 = T6.
Such a PSS will have the form:
{M7 = (T6)M1, M6 = (T5)M1,…, M2 = (T)M1}.

Finding a Solution
Let G0 and H0 correspond to the elements in M1 located X0 = (1,2) and Y0 = (1,3), respectively.
In (T)M1 will map <G0,H0> to new locations: <X0,Y0> -> <X1,Y1>. T will also map the original elements located at <X1,Y1>, call them <G1,H1>, to different locations: <X1,Y1> -> <X2,Y2>.
Thus, we can define <Xj,Yj> as the location of <G0,H0> in the matrix Mj = (Tj)M1.

We made the assumption that T is acted 6 times on M1 to produce the remaining 6 matrices in the PSS. Under this assumption, we can say that Xj == X0 and Yk == Y0 only if j=k=0 modulo 7. This is because <X0,Y0> must be occupied by 14 distinct values across the 7 different matrices in the PSS. If <G0,H0> was to re-occupy the position prior to the seventh iteration, the property of the PSS would not hold.
Given the above knowledge, we can describe T by a matrix populated with the labels X1,Y1,X2,Y2,…,X6,Y6. Let’s call this the "flow map” of T.
T acting on a matrix moves elements at <Xk,Yk> to <X(k+1),Y(k+1)>, where k is modulo 7. If T is repeatedly performed, the elements will move around in a cyclic manner with period 7.

Code: Select all

`Example of flow map:Pv X0 Y0X1 Y1 X2Y2 X3 Y3X4 Y4 X5Y5 X6 Y6A single step of the above flow map:M =            (T)M =Pv G0 H0       Pv G1 H1G1 H1 G2       G2 H2 G3H2 G3 H3   ->  H3 G4 H4G4 H4 G5       G5 H5 G6H5 G6 H6       H6 G0 H0`

The flow map for T requires some constraints to prevent duplicate collisions from occurring in the rows. Because the behavior is cyclic, we can inductively determine the following constraints:
1. If Xa and Xb exist in the same row, there can be no row which contains Xc and Xd such that (c-d)=(a-b) mod 7; where c != a, b != d.
In other words there is no 0 < k < 7 such that (a+k) = c mod 7 and (b+k) = d mod 7.
2. Rule 1 applied to YY pairs (instead of XX pairs).
3. Rule 1 applied to XY pairs.
4. Rule 1 applied to YX pairs.

At this point, I just went and solved it intuitively, but here is a more systematic explanation:

Any ordered pair (a,b) chosen from [0,6] will split one cycle into two parts. The split could be 0:7, 1:6, 2:5, or 3:4. The rules above is equivalent to saying any pair of indices cannot have the same split given the letter pairings match. Thus, every pair of labels chosen from any row can be uniquely identified by one of the following:
{XX,1:6}, {XX,2:5}, {XX,3:4} = {XX,1}, {XX,2}, {XX,3}
{YY,1:6}, {YY,2:5}, {YY,3:4} = {YY,1}, {YY,2}, {YY,3}
{XY,1:6}, {XY,2:5}, {XY,3:4} = {XY,1}, {XY,2}, {XY,3}
{YX,1:6}, {YX,2:5}, {YX,3:4} = {YX,1}, {YX,2}, {YX,3}
{XY,0:7} = {YX,0:7} = {XY,0}*

*Note that the {XY,0} = {YX,0} by symmetry. Also, this ID is already taken by the <X0,Y0> in the first row (the derivation of the flow map, started with the assumption that <X0,Y0> was at (1,2) and (1,3))

We need to populate the bottom four rows of the flow map with X1,Y1,…,X6,Y6 such that any pair drawn from any row can be uniquely assigned one of the possible IDs given above.
A row of <X,X,Y> yields two XY/YX pairings and one XX pairing.
A row of <X,Y,Y> yields two XY/YX pairings and one YY pairing.
A row of <Y,Y,Y> or <X,X,X> yields three pairings of YY or XX respectively.
Since we have 6 available XY/YX IDs and 3 each of XX and YY IDs, the only possible arrangement for the bottom four rows is the following (ignoring row-column permutations and X-Y symmetry):

Code: Select all

`Y Y YX X YX X YX X Y`

The row with YYY must have indices that provide the 1,2,3 splits when chosen in pairs. One way to satisfy this is <Y1,Y2,Y4>.
<Y4,Y1> will have the 3:4 split. <Y4,Y2> will have the 2:5 split. <Y2,Y1> will have the 1:6 split.

The next three rows are interchangeable, but each will have one of Y3,Y5,Y6.
Putting X2 and X3 with Y6 would use up {XY,3} and {YX,3}.
Putting X1 and X5 with Y3 would use up {XY,2} and {YX,2}.
Putting X4 and X6 with Y5 would use up {XY,1} and {YX,1}.

Putting everything together yields the final flow map:

Code: Select all

`Pv X0 Y0Y1 Y2 Y4X1 X5 Y3X4 X6 Y5X2 X3 Y6To make it easier to interpret, here is how it would behave:M=           (T)M =1 2 3          1 7 44 5 6          5 9 C7 8 9   -T->   D B 6A B C          8 2 FD E F          E A 3`

T can also be expressed as a 15 x 15 matrix which acts on a 15 dimensional vector:

Code: Select all

` 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0`

EDIT: Sorry, I messed up printing out the matrix with java. It should be correct now
You just need a single configuration expressed as a vector, and repeatedly multiplying by the above matrix will generate the other six!
Last edited by Cradarc on Tue Oct 13, 2015 3:10 am UTC, edited 1 time in total.
This is a block of text that can be added to posts you make. There is a 300 character limit.

Sandor
Posts: 179
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Kirkman's Schoolgirls

Seeing as nobody has actually posted a solution, I thought I would.

Spoiler:
I first tried many patterns different patterns, similar to MOJr's attempt above. I did this by hand, but used a computer to visualise the results. After a couple of hours I decided that wasn't going to work - you seem to need five-fold symmetry for some pairs, and there aren't enough days to fit them in.

Instead I decided to first find 35 triplets where all the girls are paired exactly once. This was surprisingly easy - I only had to back-track a few times. Then I arranged them into days, with no girl appearing twice in the same day. This involved a bit more back-tracking, but not much.

My solution:

Code: Select all

`ADEFG ABCDE ABCFG ABCEF ABCEG ABCDG ABCDFBHJKI FILJH DHMIK HMDKJ NDHIJ JLEIH LEIKHCLOMN GKONM EJNOL IOGNL OFKLM KNFMO MGJON`

As Goahead52 pointed out, this is called a Steiner system (although I didn't know that until after I solved it). There's actually a Wikipedia page about the problem. As the OP said, it was proposed by Rev. Thomas Penyngton Kirkman in 1850, in The Lady's and Gentleman's Diary.

Vytron
Posts: 429
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

### Re: Kirkman's Schoolgirls

Spoiler:
I really need a Red and Rover here (i.e. explain me what is going on as if I was a 4 year old.)

Apparently this passes some kind of complexity I'm unable to understand, though it looks scary how people have to spend entire hours figuring it out, and the solution doesn't seem like one that one could arrive at quickly.

I seem unable to do this in a way different from trial and error, but that's like trying different numbers in a Sudoku puzzle until you eliminate them as possibilities (guessing) instead of having a clear logic path to completion.

Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

### Re: Kirkman's Schoolgirls

Um...I effectively provided a crap load of solutions with my previous post. Or did people miss this part:
Cradarc wrote:You just need a single configuration expressed as a vector, and repeatedly multiplying by the above matrix will generate the other six!

You literally just need a single day's arrangement, and my matrix can generate the other six days arrangement for you.

Suppose you got an arrangement A, which is a 5 x 3 matrix.
1. "Unravel" the matrix so it becomes a 15 x 1 vector, where the first 3 elements are the first row of A, the next 3 is the second row, etc. Let that vector be v.
2. {v, Tv, T2v, T3v, T4v, T5v, T6v} will be your solutions for the seven days, where T is the matrix I provided.
3. Simply "repack" each 15 x 1 vector back into 5 x 3 matrices, and you got 7 arrangements.

If you look over my work, there is some degree of freedom to how T can be constructed. If you construct a different transformation matrix than the one I did, you can potentially* double the number of solutions you generated for every given A.

*I haven't explicitly tested it, but I applied my transformation to the first matrix in Sandor's solution and got a different set than the one he provided. Most likely his set can be generated by a different transformation matrix:

Code: Select all

`N=0:3 2 1 C 8 4 F A 5 D B 6 E 9 7 N=1:3 F C 8 5 6 E B 4 A 2 7 9 D 1 N=2:3 E 8 5 4 7 9 2 6 B F 1 D A C N=3:3 9 5 4 6 1 D F 7 2 E C A B 8 N=4:3 D 4 6 7 C A E 1 F 9 8 B 2 5 N=5:3 A 6 7 1 8 B 9 C E D 5 2 F 4 N=6:3 B 7 1 C 5 2 D 8 9 A 4 F E 6 N=7:3 2 1 C 8 4 F A 5 D B 6 E 9 7 `
This is a block of text that can be added to posts you make. There is a 300 character limit.

Sandor
Posts: 179
Joined: Sat Feb 13, 2010 8:25 am UTC

### Re: Kirkman's Schoolgirls

Cradarc wrote:I haven't explicitly tested it, but I applied my transformation to the first matrix in Sandor's solution and got a different set than the one he provided.

It might be the same basic arrangement, but displayed in a different order with different names for the girls. One could try all 15! permutations of girls' names, but that will generate an awful lot of permutations that have triples in your arrangement that aren't in mine.

Instead one could first sort my arrangement so the schoolgirls within each row are in order, the rows within each day are in order, and the days are in order. Then, for your arrangement:

• Try all your 7 days as the first day, for each:
• Try all 5! (120) combinations of rows, for each:
• Try all 3!^5 (7776) combinations of schoolgirls within each row
I make that 6531840 different permutations of your arrangement that could match my arrangement's first day. For each, one could substitute the girl's names so they match my arrangement's first day, sort the rest of your arrangement (in the same way mine was sorted), then see if they match. That's easily brute-forcible.

Wikipedia claims there are seven non-isomorphic solutions to the schoolgirl problem, so I guess there's a 1 in 7 chance we actually got the same basic solution.