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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Оригинальная публикация задачи

Задача Киркмана о школьницах — это комбинаторная задача, предложенная Томасом Пенингтоном Киркманом в 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)[en], дан ниже.

Решение 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)[en] с двумя элементами использовалось с четырьмя однородными координатами для формирования PG(3,2) с 15 точками, 3 точками на прямой, 7 точками и 7 прямыми на плоскости. Плоскость можно считать полным четырёхугольником вместе с прямыми через его диагональные точки. Каждая точка лежит на 7 прямых и есть в общем счёте 35 прямых.

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

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

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

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

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

Обобщение[править | править код]

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

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

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

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

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

Другие приложения[править | править код]

Примечания[править | править код]

  1. ↑ 1 2 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. ↑ 1 2 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 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.
  • 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.
  • Тараканов В. Е. Комбинаторные задачи и (0,1) матрицы. — Москва: «Наука», 1985. — (Проблемы науки и технического прогресса).

Ссылки[править | править код]

Источник — https://ru.wikipedia.org/w/index.php?title=Задача_Киркмана_о_школьницах&oldid=136332035