Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

Kirkman's Schoolgirl Problem

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.

Three wizards are seated at a circular room. A magician shall make hats appear on their heads, one hat per wizard. Hats are either black or white, chosen uniformly at random. A wizard cannot see his own hat. At the sound of a bell, all wizards react simultaneously. A wizard reacts by either announcing a color or keeping quiet. If at least one wizard makes an announcement and if all the announcements are correct, the wizards have collectively won the game! Wizards are allowed to confer beforehand to devise a strategy. On average, can they win more than half the times the game is played?

The first box has two white balls. The second box has two black balls. The third box has one white and one black ball. Boxes are labeled but all labels are wrong! You are allowed to open one box, pick one of its balls at random, see its color and put it back into the box (you do not get to know the color of the other ball). How many such operations are necessary to correctly label the boxes?

12 Sep 2008
© Copyright 2008—2017, Gurmeet Manku.