After several weeks of guest speakers in our Friday Afternoon Mathematics Undergraduate Seminar (FAMUS), I gave a short talk on Friday, November 13 that was centered around The Kirkman Schoolgirls Problem. In 1850, the Reverend Thomas Kirkman, posed an innocent-looking puzzle in the *Lady’s and Gentleman’s Diary*, a recreational mathematics journal:

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.

Here “abreast” means “in a group,” so the girls are walking out in groups of three, and each pair of girls should only be in the same group once. It turns out that this problem is harder than it looks. It’s not even obvious that a solution is possible. In order to gain some insight into Kirkman’s problem, we tinkered with the following simpler problems.

15 young ladies in a school walk out in groups of 3 for 8 days in succession. Can you arrange the girls in walking groups so that no pair of girls ever walks in the same group of three more than once?

6 young ladies in a school walk out in groups of 3 for 2 days in succession. Can you arrange the girls in walking groups so that no pair of girls ever walks in the same group of three more than once?

9 young ladies in a school walk out in groups of 3 for 4 days in succession. Can you arrange the girls in walking groups so that no pair of girls ever walks in the same group of three more than once?

The audience was able to quickly determine that the answer is “no” for problems 1 and 2. For the third problem, I let the audience play around for a bit and then I showed them one possible solution using *Quanta Magazine’s* applet located here. After discussing what it would take to verify that a proposed solution to Kirkman’s problem was actually a solution, I showed them one of seven possible solutions.

It turns out that Kirkman’s puzzle is a prototype for a more general problem:

If you have $n$ schoolgirls, can you create groups of size $k$ such that each smaller set of size $t$ appears in just one of the larger groups?

Such an arrangement is said to be of type $S(t,k,n)$, which is called a Steiner systems (or combinatorial design theory). For example, solutions to the original Kirkman problem are of type $S(2,3,15)$. Notice that we have abandoned the extra restriction that the sets of size $k$ are sortable into days.

One of the fundamental problems in the theory of combinatorial designs is determining whether a given $S(t,k,n)$ exists and if one exists, how many are there? For example, is $S(2,3,7)$ possible? The answer is yes and one can interpret the Fano plane as one possible solution.

Many combinations of $t, k$, and $n$ can be quickly ruled out by divisibility obstacles. For example, problem 2 above helped us to determine that $S(2,3,6)$ is not possible. For combinations that aren’t immediately tossed out, there’s no easy way to discover whether a given combination is possible. For example, it turns out that $S(2,7,43)$ is impossible, but it is for complicated reasons. However, in January 2014, Peter Keevash (Oxford) established that, apart from a few exceptions, $S(t,k,n)$ will always exist if a few divisibility requirements are satisfied. This is a big deal in the world of combinatorial design theory.

As with many of the topics I choose to give a talk on in FAMUS, I pretty much knew nothing about the topic before I started prepping for the talk. I go out of my way to emphasize that this is the case because I want the students to know that the learning never ends.

Here are the slides for my talk. *Note:* There are two additional problems related to Kirkman’s problem at the very end that you might find interesting.

The content of my slides was inspired or came directly from the following sources:

- There is a great write up of Kirkman’s original problem, its connection to CDT, and a brief summary of Keevash’s new result in Quanta Magazine.
- The Wikipedia article on The Kirkman Schoolgirl Problem has a lot of cool information.
- Also, check out the Wikipedia articles on Steiner systems, Combinatorial Design Theory, and the Fano plane.
- You can find Peter Keevash’s article about the existence of Steiner systems over on the arXiv.

Most weeks in FAMUS, the host interviews a faculty member. However, this week, Dr. Derek Sonderegger gave a 30 minute talk on the merits of pursuing a graduate degree in mathematics, statistics, or mathematics education. In addition, Derek provided some details about our graduate program. We also had quite a few of our grad students in attendance that were able to chime in about their current experience.

Mathematics & Teaching

Northern Arizona University

Flagstaff, AZ

Website

928.523.6852

Twitter

Instagram

Facebook

Strava

GitHub

arXiv

ResearchGate

LinkedIn

Mendeley

Google Scholar

Impact Story

ORCID

MAT 226: Discrete Math

MAT 526: Combinatorics

This website was created using GitHub Pages and Jekyll together with Twitter Bootstrap.

Unless stated otherwise, content on this site is licensed under a Creative Commons Attribution-Share Alike 4.0 International License.

The views expressed on this site are my own and are not necessarily shared by my employer Northern Arizona University.

The source code is on GitHub.

Flagstaff and NAU sit at the base of the San Francisco Peaks, on homelands sacred to Native Americans throughout the region. The Peaks, which includes Humphreys Peak (12,633 feet), the highest point in Arizona, have religious significance to several Native American tribes. In particular, the Peaks form the Diné (Navajo) sacred mountain of the west, called Dook'o'oosłííd, which means "the summit that never melts". The Hopi name for the Peaks is Nuva'tukya'ovi, which translates to "place-of-snow-on-the-very-top". The land in the area surrounding Flagstaff is the ancestral homeland of the Hopi, Ndee/Nnēē (Western Apache), Yavapai, A:shiwi (Zuni Pueblo), and Diné (Navajo). We honor their past, present, and future generations, who have lived here for millennia and will forever call this place home.