Задача Киркмана о школьницах

Задача Киркмана о школьницах — это комбинаторная задача, предложенная Томасом Пенингтоном Киркманом в 1850 году как Вопрос VI в журнале The Lady's and Gentleman's Diary (журнал занимательной математики, издававшийся между 1841 и 1871). Задача гласит:

Пятнадцать молодых девушек в школе прогуливаются по три в ряд семь дней (каждый день), требуется распределить их на каждую прогулку так, чтобы никакие две девушки не шли в том же ряду (Graham, Grötschel, Lovász 1995).

Если девушек пронумеровать от 0 до 14, следующее распределение будет одним из решений^[1]:

Решение этой задачи является примером системы троек Киркмана^[2]; это означает, что она является системой троек Штейнера, обладающей параллельностью, то есть обладающей разбиением блоков системы троек на параллельные классы, которые являются разбиением точек на непересекающиеся блоки.

Существует семь неизоморфных решений задачи о школьницах^[3]. Два из них можно визуализировать как отношения между тетраэдром и его вершинами, рёбрами и гранями^[4]. Подход, использующий трёхмерную проективную геометрию над GF(2)^[англ.], дан ниже.

Если девушек перенумеровать двоичными числами от 0001 до 1111, следующее распределение является решением, таким, что для любых трёх девушек, образующих группу, побитное XOR двух чисел даёт третье:

Это решение имеет геометрическую интерпретацию, связанную с геометрией Галуа и PG(3,2). Возьмём тетраэдр и перенумеруем его вершины как 0001, 0010, 0100 и 1000. Перенумеруем шесть центров рёбер как XOR концов ребра. Присвоим четырём центрам граней метки, равные XOR трёх вершин, а центру тела дадим метку 1111. Тогда 35 троек и XOR решение соответствует в точности 35 прямым PG(3,2).

Первое решение опубликовал Артур Кэли^[5]. За ним быстро последовало решение самого Киркмана^[6], которое было дано как специальный случай его комбинаторного размещения, опубликованного тремя годами ранее^[7]. Д. Д. Сильвестр также исследовал задачу и закончил утверждением, что Киркман украл идею у него. Головоломка появилась в нескольких занимательных математических книгах на стыке веков у Лукаса^[8], Роуз Болла^[9], Ааренса^[10] и Дьюдени^[11].

Киркман часто объяснял, что его большая статья (Kirkman 1847) была полностью вызвана огромным интересом к задаче^[12].

В 1910 задачу рассмотрел Джорж Конвелл с помощью геометрии Галуа^[13].

Поле Галуа GF(2)^[англ.] с двумя элементами использовалось с четырьмя однородными координатами для формирования PG(3,2) с 15 точками, 3 точками на прямой, 7 точками и 7 прямыми на плоскости. Плоскость можно считать полным четырёхугольником вместе с прямыми через его диагональные точки. Каждая точка лежит на 7 прямых и есть в общем счёте 35 прямых.

Прямые пространства PG(3,2) определяются их плюкеровыми координатами в PG(5,2) с 63 точками, 35 из которых представляют прямые в PG(3,2). Эти 35 точек образуют поверхность S, известную как квадрика Кляйна^[англ.]. Для каждой из 28 точек, не лежащих на S, существует 6 прямых через эту точку, которые не пересекаются с S^[14].

Как число дней в неделе, семёрка играет важную роль в решении:

Семёрка определяется двумя её точками. Каждая из 28 точек вне S лежит на двух семёрках. Есть 8 семёрок. Проективная линейная группа^[англ.] PGL(3,2) изоморфна знакопеременной группе на 8 семёрках^[15].

Задача о школьницах состоит из поиска семи непересекающихся прямых в 5-мерном пространстве, таких, что любые две прямые всегда имеют общую семёрку^[16].

Задачу можно обобщить до ${\displaystyle n}$ учениц, где ${\displaystyle n}$ должно быть числом, равным произведением нечётного числа на 3 (то есть, ${\displaystyle n\equiv 3{\pmod {6}}}$), прогуливающиеся тройками ${\displaystyle {\frac {1}{2}}(n-1)}$ дней с условием, снова, что никакая пара девушек не прогуливается в том же ряду дважды^[17]. Решение этого обобщения является системой троек Штейнера S(2, 3, 6t + 3) с параллельностью (то есть системой, в которой каждые 6t + 3 элементов оказываются ровно раз в каждом блоке из 3-элементных множеств), известной как система Киркмана^[1]. Это обобщение задачи, которое первоначально обсуждал Киркман, а знаменитый частный случай ${\displaystyle n=15}$ он обсуждал позднее^[7]. Полное решение общего случая опубликовали Д. К. Рей-Чадхури и Р. М. Вильсон в 1968 году^[18], хотя задача уже была решена китайским математиком Лю Джакси (陆家羲) в 1965 году^[19], но в то время решение ещё опубликовано не было^[20].

Рассматривались несколько вариантов основной задачи. Алан Хартман решал задачу этого типа с требованием, что никакие три не прогуливаются в рядах по четыре более одного раза^[21], с помощью системы четвёрок Штейнера.

Недавно стала известна похожая проблема, известная как «задача о поле для гольфа», в которой имеется 32 игрока в гольф, которые хотят играть с различными людьми каждый день группами по 4 в течение 10 дней подряд.

Так как это стратегия перегруппировки, когда все группы ортогональны, этот процесс образования из большой группы маленьких групп, в которых никакие два человека не попадают одновременно в более чем одну группу, можно рассматривать как ортогональную перегруппировку. Однако этот термин употребляется редко и можно считать, что нет общепринятого термина для этого процесса.

Задача Обервольфаха разложения полного графа на непересекающиеся копии заданного 2-регулярного графа также обобщает задачу Киркмана о школьницах. Задача Киркмана является специальным случаем задачи Обервольфаха, в котором 2-регулярный граф состоит из пяти непересекающихся треугольников^[22].

• Кооперативное обучение — стратегия для увеличения сотрудничества учащихся в классе
• Спортивные соревнования

• Erica Klarreich. A design dilemma solved, minus designs. // Quanta Magazine. — 2015. — Июнь.