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:
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.
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:
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:
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
MAT 123: First Year Seminar
MAT 136: Calculus I
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.