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

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

Решение

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

Воскре- сенье	Поне- дельник	Вторник	Среда	Четверг	Пятница	Суббота
0,  5, 10	0,  1,  4	1,  2,  5	4,  5,  8	2,  4, 10	4,  6, 12	10, 12,  3
1,  6, 11	2,  3,  6	3,  4,  7	6,  7, 10	3,  5, 11	5,  7, 13	11, 13,  4
2,  7, 12	7,  8, 11	8,  9, 12	11, 12,  0	6,  8, 14	8, 10,  1	14,  1,  7
3,  8, 13	9, 10, 13	10, 11, 14	13, 14,  2	7,  9,  0	9, 11,  2	0,  2,  8
4,  9, 14	12, 14,  5	13,  0,  6	1,  3,  9	12, 13,  1	14,  0,  3	5,  6,  9

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

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

Решение XOR троек

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

Воскре- сенье	Поне- дельник	Вторник	Среда	Четверг	Пятница	Суббота
0001, 0010, 0011	0001, 0100, 0101	0001, 0110, 0111	0001, 1000, 1001	0001, 1010, 1011	0001, 1100, 1101	0001, 1110, 1111
0100, 1000, 1100	0010, 1000, 1010	0010, 1001, 1011	0010, 1100, 1110	0010, 1101, 1111	0010, 0100, 0110	0010, 0101, 0111
0101, 1010, 1111	0011, 1101, 1110	0011, 1100, 1111	0011, 0101, 0110	0011, 0100, 0111	0011, 1001, 1010	0011, 1000, 1011
0110, 1011, 1101	0110, 1001, 1111	0100, 1010, 1110	0100, 1011, 1111	0101, 1001, 1100	0101, 1011, 1110	0100, 1001, 1101
0111, 1001, 1110	0111, 1011, 1100	0101, 1000, 1101	0111, 1010, 1101	0110, 1000, 1110	0111, 1000, 1111	0110, 1010, 1100

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

История

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

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

Геометрия Галуа

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

Поле Галуа с двумя элементами использовалось с четырьмя однородными координатами для формирования 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 .

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

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

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

Обобщение

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

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

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

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

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

Другие приложения

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

Примечания

Литература

Ссылки

• Erica Klarreich. // . — 2015. — Июнь.