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

Оригинальная публикация задачи

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

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

Решение

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

Воскре- сенье	Поне- дельник	Вторник	Среда	Четверг	Пятница	Суббота
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

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

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

Решение 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).

История

Первое решение опубликовал Артур Кэли[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].

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

Если две точки A и B на прямой ABC выбраны, каждая из пяти других прямых через A пересекается только с одной из пяти прямых, проходящих через B. Пять точек, получающихся пересечением этих пар, вместе с двумя точками A и B мы именуем «семёркой»(Conwell 1910, 68).

Семёрка определяется двумя её точками. Каждая из 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].

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

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

Примечания

1. Rouse Ball, Coxeter, 1987, с. 287−289.
2. Weisstein, Eric W. Kirkman's Schoolgirl Problem (англ.) на сайте Wolfram MathWorld.
3. Cole, 1922, с. 435–437.
4. Falcone, Pavone, 2011, с. 887–900.
5. Cayley, 1850, с. 50–53.
6. Kirkman, 1850.
7. Kirkman, 1847.
8. Lucas, 1883, с. 183–188.
9. Rouse Ball, 1892.
10. Ahrens, 1901.
11. Dudeney, 1917.
12. Cummings, 1918.
13. Conwell, 1910, с. 60–76.
14. Conwell, 1910, с. 67.
15. Conwell, 1910, с. 69.
16. Conwell, 1910, с. 74.
17. Тараканов, 1985, с. 109.
18. Ray-Chaudhuri, Wilson, 1971.
19. Lu, 1990.
20. Colbourn, Dinitz, 2007, с. 13.
21. Hartman, 1980.
22. Bryant, Danziger, 2011.

Литература

• Cole F.W. Kirkman parades // Bulletin of the American Mathematical Society. — 1922. — Т. 28. — doi:10.1090/S0002-9904-1922-03599-9.
• Giovanni Falcone, Marco Pavone. Kirkman's Tetrahedron and the Fifteen Schoolgirl Problem // American Mathematical Monthly. — 2011. — Т. 118. — doi:10.4169/amer.math.monthly.118.10.887.
• George M. Conwell. The 3-space PG(3,2) and its Groups // Annals of Mathematics. — 1910. — Т. 11. — doi:10.2307/1967582.
• Cayley A. On the triadic arrangements of seven and fifteen things // Philosophical Magazine. — 1850. — Т. 37. — doi:10.1080/14786445008646550.
• Hirschfeld J.W.P. Finite Projective Spaces of Three Dimensions. — Oxford University Press, 1985. — ISBN 0-19-853536-8.
• Ahrens W. Mathematische Unterhaltungen und Spiele. — Leipzig: Teubner, 1901.
• Darryn Bryant, Peter Danziger. On bipartite 2-factorizations of ${\displaystyle K_{n}-I}$ and the Oberwolfach problem // Journal of Graph Theory. — 2011. — Т. 68, вып. 1. — С. 22–37. — doi:10.1002/jgt.20538.
• Charles J. Colbourn, Jeffrey H. Dinitz. Handbook of Combinatorial Designs. — 2nd. — Boca Raton: Chapman & Hall/ CRC, 2007. — ISBN 1-58488-506-8.
• Cummings L.D. An undervalued Kirkman paper // Bulletin of the American Mathematical Society. — 1918. — Т. 24. — С. 336–339. — doi:10.1090/S0002-9904-1918-03086-3.
• Dudeney H.E. Amusements in Mathematics. — New York: Dover, 1917.
  • Dudeney H.E. Amusements in Mathematics. — Mineola, New York: Dover, 1958. — (Dover Recreational Math). — ISBN 978-0-486-20473-4.
• Ronald L. Graham, Martin Grötschel, László Lovász. Handbook of Combinatorics, Volume 2. — Cambridge, MA: The MIT Press, 1995. — ISBN 0-262-07171-1.
• Alan Hartman. Kirkman's trombone player problem // Ars Combinatoria. — 1980. — Т. 10. — С. 19–26.
• Jiaxi Lu. Collected Works of Lu Jiaxi on Combinatorial Designs. — Huhhot: Inner Mongolia People's Press, 1990.
• Thomas P. Kirkman. On a Problem in Combinations // The Cambridge and Dublin Mathematical Journal. — Macmillan, Barclay, and Macmillan, 1847. — Т. II. — С. 191–204.
• Thomas P. Kirkman. Note on an unanswered prize question // The Cambridge and Dublin Mathematical Journal. — Macmillan, Barclay and Macmillan, 1850. — Т. 5. — С. 255–262.
• Lucas É. Récréations Mathématiques. — Paris: Gauthier-Villars, 1883. — Т. 2. — С. 183–188.
• Ray-Chaudhuri D.K., Wilson R.M. Solution of Kirkman's schoolgirl problem, in Combinatorics, University of California, Los Angeles, 1968. — Proceedings Symposisa Pure Mathematics. — 1971. — Т. XIX. — С. 187–203. — ISBN 978-0-8218-1419-2. — doi:10.1090/pspum/019/9959.
• Rouse Ball W.W. Mathematical Recreations and Essays. — London: Macmillan, 1892.
  • Rouse Ball W.W., Coxeter H.S.M. Mathematical Recreations and Essays. — 13th. — Dover, 1987. — С. 287−289. — ISBN 0-486-25357-0. Оригинальное издание:1974
• Тараканов В. Е. Комбинаторные задачи и (0,1) матрицы. — Москва: «Наука», 1985. — (Проблемы науки и технического прогресса).

Ссылки

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