10
$\begingroup$

Given a solution to Kirkman's School Girl Problem, it is of course easy enough to check that it actually is a solution. But how could you reconstruct it if you lost it? Is there a method or algorithm for constructing a solution which is easier to remember than the actual solution?

There are many combinatorial problems that have such memorable solutions:

In the related Tournament Scheduling Problem you fix one player and rotate the remaining $n-1$ players.

In the Transylvanian Lottery Problem you divide the 14 points into 2 Fano planes and consider the 7 lines in each Fano plane.

And doubtless many others (which it might also be interesting to list).

$\endgroup$
3
  • 9
    $\begingroup$ I came up with a memorable solution, but I've forgotten it. $\endgroup$ Mar 23, 2015 at 17:12
  • 1
    $\begingroup$ In "Mathematics Magazine" vol. 82 No.1 February 2009, they have an article ("Kirkman's Schoolgirls Wearing Hats and Walking through Fields of Numbers, by Erza Brown and Keith Mellinger) that that makes connections with certain number fields and some packing problems in finite projective geoemtry. Looks like it would be memorable, I just have not look at it in detail. I am sure someone will write... $\endgroup$
    – user29123
    Mar 24, 2015 at 10:20
  • 3
    $\begingroup$ It would be polite to provide a description of the problem, or at least a link. $\endgroup$
    – TonyK
    Mar 24, 2015 at 10:57

2 Answers 2

23
$\begingroup$

I do not know about photographic memory, but I found this quite appealing way to describe it:

enter image description here

The girls are represented as points and the groups as paths. Each group contains three girls and no two girls belong to the same group on different days. I found the description of it on this website and made the above animation of it.


BTW: Just a few thoughts. The link goes into details about enumerating the points and states that the pattern should be rotated counterclockwise. The enumeration is only necessary if we are to write down the groups, and any initial enumeration may be chosen. If the girls can sort it out among themselves, they can even choose with whom they want to be on the first day.

Rotating counterclockwise is only one possible choice: Let the $7$-cycle $\tau=(1234567)$ represent the rotation by one step counterclockwise each day as in the animation. Then we have a cyclic subgroup of order $7$ in $S_7$ with generators $\tau,\tau^2,...,\tau^6$ $$ \mathbb Z_7\simeq\langle\tau\rangle=\langle\tau^2\rangle=...=\langle\tau^6\rangle\subseteq S_7 $$ where $\tau^k$ corresponds to rotating $k$ steps counterclockwise. Then $\tau^6$ still generates the entire group and corresponds to rotating one step clockwise instead (it should come as no surprise that this works as well).

$\endgroup$
3
  • $\begingroup$ This is a wonderful solution and just what I was looking for! $\endgroup$
    – Lancel
    Mar 24, 2015 at 21:46
  • $\begingroup$ Fantastic -- I never would have guessed the solution could be made to look that simple. $\endgroup$ Nov 6, 2015 at 4:04
  • $\begingroup$ This is not all patterns. At least I found diffirence 10 patterns. $\endgroup$ Apr 9, 2016 at 7:57
1
$\begingroup$

Number the girls 1 thru 15 (it will be easier to see patterns with numbers instead of letters) then divide the girls into 3 groups: 1-7, 8-14, and 15.

1,2,x │ 3,5,x  │ 4,7,x │ 6,15,x │ x,x,x
2,3,  │ 4,6,   │ 5,1,  │ 7,15,  │
3,4,  │ 5,7,   │ 6,2,  │ 1,15,  │
4,5     6,1      7,3     2,15
5,6     7,2      1,4     3,15
6,7     1,3      2,5     4,15
7,1     2,4      3,6     5,15

Now solve for x like a Sudoku puzzle using only the numbers for the group 8-14. You will always keep these numbers in order remembering to 'wrap-around' when you get to 14 ie: 8 will follow 14. You only have to solve the top row. There are many solutions to this problem at this point. Start with the first x =8 (there will be two solutions) then try the first x =9 etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.