Kirkman's Schoolgirls

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Kirkman's Schoolgirls

Postby quintopia » Tue Oct 06, 2015 3:32 am UTC

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.

User avatar
SDK
Posts: 664
Joined: Thu May 22, 2014 7:40 pm UTC
Location: Canada

Re: Kirkman's Schoolgirls

Postby SDK » Wed Oct 07, 2015 3:04 pm UTC

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

Postby MOJr » Fri Oct 09, 2015 7:23 am UTC

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

Postby Reydien » Fri Oct 09, 2015 11:38 am UTC

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   E09
16B   17D   18A   1C8   1D5   E19   A15
27C   28E   29B   2D9   2E6   A25   B26
38D   39A   35C   3E5   3A7   B36   C37
49E   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

User avatar
jaap
Posts: 2085
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Kirkman's Schoolgirls

Postby jaap » Fri Oct 09, 2015 12:13 pm UTC

Reydien wrote:I think I have a solution.

Spoiler:

Code: Select all

05A   06C   07E   0B7   0C9   D08   E09
16B   17D   18A   1C8   1D5   E19   A15
27C   28E   29B   2D9   2E6   A25   B26
38D   39A   35C   3E5   3A7   B36   C37
49E   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.

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

Re: Kirkman's Schoolgirls

Postby emlightened » Fri Oct 09, 2015 4:47 pm UTC

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.
← approximately how gay I am.
"a nebulous cloud of different combinations of styling bodily features"
"on either side of a wrought iron fence made of tigers"

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

Re: Kirkman's Schoolgirls

Postby Sandor » Sat Oct 10, 2015 8:19 pm UTC

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.

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

Re: Kirkman's Schoolgirls

Postby Goahead52 » Sun Oct 11, 2015 12:04 pm UTC

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.

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

Re: Kirkman's Schoolgirls

Postby Cradarc » Mon Oct 12, 2015 4:30 am UTC

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 Y0
X1 Y1 X2
Y2 X3 Y3
X4 Y4 X5
Y5 X6 Y6

A single step of the above flow map:
M =            (T)M =
Pv G0 H0       Pv G1 H1
G1 H1 G2       G2 H2 G3
H2 G3 H3   ->  H3 G4 H4
G4 H4 G5       G5 H5 G6
H5 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 Y
X X Y
X X Y
X 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 Y0
Y1 Y2 Y4
X1 X5 Y3
X4 X6 Y5
X2 X3 Y6

To make it easier to interpret, here is how it would behave:
M=           (T)M =
1 2 3          1 7 4
4 5 6          5 9 C
7 8 9   -T->   D B 6
A B C          8 2 F
D 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: 177
Joined: Sat Feb 13, 2010 8:25 am UTC

Re: Kirkman's Schoolgirls

Postby Sandor » Mon Oct 12, 2015 5:44 pm UTC

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 ABCDF
BHJKI FILJH DHMIK HMDKJ NDHIJ JLEIH LEIKH
CLOMN 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.

User avatar
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

Postby Vytron » Tue Oct 13, 2015 12:24 am UTC

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.

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

Re: Kirkman's Schoolgirls

Postby Cradarc » Tue Oct 13, 2015 2:53 am UTC

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: 177
Joined: Sat Feb 13, 2010 8:25 am UTC

Re: Kirkman's Schoolgirls

Postby Sandor » Tue Oct 13, 2015 2:56 pm UTC

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.

Also, this page has some discussion of this and related problems.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 4 guests