Kirkman's Schoolgirl Problem
12 Sep 2008
Puzzle

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.

Source

A classic puzzle found in several books.

Solution

Let A, B, C, ..., I denote the schoolgirls. Each color represents a row of schoolgirls:

 A  B  C 
 D  E  F 
 G  H  I 
 A  B  C 
 D  E  F 
 G  H  I 
 A  B  C 
 D  E  F 
 G  H  I 
 A  B  C 
 D  E  F 
 G  H  I 

Followup

What if there are 15 schoolgirls to be arranged in 5 rows and 3 columns on 7 days so that no two schoolgirls share a row on more than one day? This is the original Kirkman's Schoolgirl Problem from 1850.

A beautiful visual representation of the solution may be found here.

© Copyright 2008—2023, Gurmeet Manku.