Kirkman's schoolgirl problem
Source: Classic combinatorics problem. Read it at a lot of places. Also in wikipedia Wiki Link
Problem: Nine schoolgirls are to be arranged in three rows and three columns on four different days so that any pair of schoolgirls is in the same row on exactly one of the four days.
Update:(18/12/09) Hint was wrong and hence removed. Solution by Giridhar in comments. Some discussion by me in comments.
Problem: Nine schoolgirls are to be arranged in three rows and three columns on four different days so that any pair of schoolgirls is in the same row on exactly one of the four days.
Update:(18/12/09) Hint was wrong and hence removed. Solution by Giridhar in comments. Some discussion by me in comments.
First Day :
ReplyDelete1 2 3
4 5 6
7 8 9
Second Day (columns become Rows) :
1 4 7
2 5 8
3 6 9
Third Day ( Form rows with elements along Principal Diagonal ) :
1 5 9
2 6 7
3 4 8
Fourth Day ( Form rows with elements along Other Diagonal ) :
1 6 8
2 4 9
3 5 7
Every day an element is paired with two new elements every day. Hence every element is paired with 8 other elements in total( 2 on each day). This implies uniqueness.
Did i misunderstood any part ?
Nice solution.. Thanx giridhar.
ReplyDeleteGoing a bit more technical (and mathematical): http://home.wlu.edu/~mcraea/Finite_Geometry/Applications/Prob31SchoolGirl/problem31.html goes into a more detailed analysis