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.

**Moderators:** jestingrabbit, Moderators General, Prelates

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.

I don't know the answer myself.

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.

I was able to get it to five days.

**Spoiler:**

Also SDK you have a mistake there:

**Spoiler:**

Also SDK you have a mistake there:

I think I have a solution.

**Spoiler:**

As for a somewhat winded explanation of my methods:

**Spoiler:**

As for a somewhat winded explanation of my methods:

Reydien wrote:I think I have a solution.Spoiler:

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.

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.

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."

"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."

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.

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.

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.

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:**

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.

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

**Spoiler:**

- 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

Um...I effectively provided a crap load of solutions with my previous post. Or did people miss this part:

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, T^{2}v, T^{3}v, T^{4}v, T^{5}v, T^{6}v} 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:

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, T

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.

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

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.

Users browsing this forum: No registered users and 8 guests