Задача Киркмана о школьнице - это задача комбинаторики, предложенная преподобным Томасом Пенингтоном Киркманом в 1850 году в качестве запроса VI в «Дневнике леди и джентльмена» (стр. 48). Проблема гласит:
Пятнадцать барышень в школе ходят по три в ряд семь дней подряд: требуется устраивать их ежедневно так, чтобы никакие двое не ходили два раза в ряд. [1]
Решение
Если девочки пронумерованы от 0 до 14, следующее решение является одним из решений: [2]
Солнце. | Пн. | Вт. | Мы б. | Чт. | Пт. | Сидел. |
---|---|---|---|---|---|---|
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 |
Решение этой проблемы является примером Kirkman тройной системы , [3] , который является тройной системой Штейнера , имеющим параллелизм , то есть, разбиение блоков тройной системы в параллельные классы , которые сами по себе перегородки точек в непересекающиеся блоки.
Есть семь неизоморфных решений проблемы школьницы. [4] Два из них можно представить себе как отношения между тетраэдром и его вершинами, ребрами и гранями. [5] Ниже приводится подход, использующий проективную геометрию трех измерений над GF (2) .
История
Первое решение было опубликовано Артуром Кэли . [6] Вскоре за этим последовало собственное решение Киркмана [7], которое было приведено как частный случай его соображений о комбинаторных схемах, опубликованных за три года до этого. [8] Джей Джей Сильвестр также исследовал проблему и в итоге заявил, что Киркман украл у него идею. Головоломка появилась в нескольких книгах по развлекательной математике на рубеже веков Лукаса [9], Роуз Болл, [10] Аренса [11] и Дудени. [12]
Киркман часто жаловался на то, что его содержательная статья ( Kirkman 1847 ) полностью затмилась популярным интересом к проблеме школьницы. [13]
Геометрия Галуа
В 1910 году проблема была решена с помощью геометрии Галуа Джорджем Конвеллом. [14]
Поле Галуа 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] : 67
Поскольку в неделе семь дней, гептада является важной частью решения:
Когда выбраны две точки как A и B на прямой ABC, каждая из пяти других прямых, проходящих через A, встречается только с одной из пяти других прямых, проходящих через B. Пять точек, определяемых пересечениями этих пар прямых, вместе с две точки A и B мы обозначаем «гептадой». [14] : 68
Гептада определяется любыми двумя ее точками. Каждая из 28 точек от S лежит в двух семиугольниках. Всего 8 гептад. Проективная группа PGL (3,2) изоморфна знакопеременной группы по 8 heptads. [14] : 69
Задача школьницы состоит в том, чтобы найти семь линий в пятерке, которые не пересекаются и такие, что любые две линии всегда имеют общую гептаду. [14] : 74
Спреды и упаковка
В PG (3,2) разбиение точек на линии называется разворотом , а разбиение линий на развороты называется упаковкой или параллелизмом . [15] : 66 Когда Хиршфельд рассматривал проблему в своих конечных проективных пространствах трех измерений (1985), он отметил, что некоторые решения соответствуют упаковкам PG (3,2), по существу, как описано Конуэллом выше, [15] : 91 и он представил два из них. [15] : 75
Обобщение
Проблема может быть обобщена на девушки, где должно быть нечетно кратным 3 (т. е. ), ходьба тройней за дней, с опять же требованием, чтобы ни одна пара девушек не ходила в одном ряду дважды. Решением этого обобщения является система троек Штейнера , S (2, 3, 6 t + 3) с параллелизмом (то есть такая, в которой каждый из 6 t + 3 элементов встречается ровно один раз в каждом блоке 3-элементного множеств), известную как тройная система Киркмана . [2] Именно это обобщение проблемы впервые обсудил Киркман, в то время как знаменитый частный случайбыло предложено только позже. [8] Полное решение общего случая было опубликовано DK Ray-Chaudhuri и RM Wilson в 1968 г. [16], хотя оно уже было решено Лу Цзяси ( китайский :家) в 1965 г. [17], но не было опубликовано в то время. [18]
Можно рассмотреть множество вариантов основной проблемы. Алан Хартман решает проблему этого типа с помощью требования, чтобы ни одно трио не проходило в ряду из четырех человек более одного раза [19], используя систему четверок Штейнера.
Совсем недавно интерес к подобной проблеме, известной как проблема социального игрока в гольф, затронул 32 игрока в гольф, которые хотят играть с разными людьми каждый день в группах по 4 человека в течение 10 дней.
Поскольку это стратегия перегруппировки, при которой все группы ортогональны, этот процесс в рамках проблемы организации большой группы в более мелкие группы, где никакие два человека не делят одну и ту же группу дважды, можно назвать ортогональной перегруппировкой. Однако в настоящее время этот термин широко не используется, и данные свидетельствуют о том, что общепринятого названия для этого процесса не существует.
Проблема разрешимых покрытий рассматривает общие девушки, Групповой случай, когда каждая пара девочек должна быть в одной группе в какой-то момент, но мы хотим использовать как можно меньше дней. Это можно, например, использовать для планирования плана смены столов, в котором каждая пара гостей должна в какой-то момент находиться за одним и тем же столом. [20]
Проблема Обервольфаха о разложении полного графа на непересекающиеся по ребрам копии данного 2-регулярного графа также обобщает проблему Киркмана о школьнице. Проблема Киркмана - это частный случай проблемы Обервольфаха, в которой 2-регулярный граф состоит из пяти непересекающихся треугольников. [21]
Другие приложения
- Стратегия совместного обучения для увеличения взаимодействия в рамках обучения в классе
- Карточная игра Доббл [22]
- Прогрессивные дизайны званых обедов
- События Speed Networking
- Спортивные соревнования
- Комбинаторика
- Р. М. Уилсон
- Диджен К. Рэй-Чаудхури
- Дискретная математика
Заметки
- ^ Graham, Grötschel & Lovász 1995
- ^ Б Болл и Косетер 1987 , стр. 287-289
- ^ Weisstein, Эрик В. "Проблема школьницы Киркмана" . MathWorld .
- ^ Коул, FW (1922), "Парады Киркмана", Бюллетень Американского математического общества , 28 (9): 435–437, DOI : 10.1090 / S0002-9904-1922-03599-9
- ^ Фальконе, Джованни; Павоне, Марко (2011), «Тетраэдр Киркмана и проблема пятнадцати школьниц», American Mathematical Monthly , 118 (10): 887–900, doi : 10.4169 / amer.math.monthly.118.10.887
- ^ Кэли, A. (1850), "О триадических расположений семь и пятнадцать вещей" , Philosophical Magazine , 37 (247): 50-53, DOI : 10,1080 / 14786445008646550
- ^ Киркман 1850
- ^ a b Киркман 1847
- ↑ Лукас 1883 , стр. 183–188
- ^ Роуз Болл 1892
- ^ Аренс 1901
- ^ Дудени 1917
- ^ Каммингс 1918
- ^ а б в г д Конвелл, Джордж М. (1910). «Трехмерное пространство PG (3,2) и его группа». Анналы математики . 11 (2): 60–76. DOI : 10.2307 / 1967582 . JSTOR 1967582 .
- ^ а б в Хиршфельд, JWP (1985), Конечные проективные пространства трех измерений , Oxford University Press , ISBN 0-19-853536-8
- ^ Рэй-Чаудхури и Уилсон 1971
- ^ Лю 1990
- ^ Colbourn & Диниц 2007 , стр. 13
- ^ Хартман 1980
- ^ Ван Дам, ER, Haemers, WH, и Peek, MBM (2003). Справедливо разрешимые покрытия. Журнал комбинаторных дизайнов, 11 (2), 113-123.
- ^ Брайант и Данцигер 2011
- ^ МакРобби, Линда Родригес. «Загадочная математика, стоящая за« Найди это! », Любимая семейная карточная игра» . Смитсоновский журнал . Проверено 1 марта 2020 .
Рекомендации
- Аренс, В. (1901), Mathematische Unterhaltungen und Spiele , Лейпциг: Teubner
- Брайант, Дэррин; Данцигер, Питер (2011), "О двудольных 2-факторизациях K п - я {\ displaystyle K_ {n} -I} и проблема Обервольфах» (PDF) , Журнал теории графов , 68 (1): 22-37, DOI : 10.1002 / jgt.20538 , МР 2833961
- Колборн, Чарльз Дж .; Диниц, Джеффри Х. (2007), Справочник по комбинаторным схемам (2-е изд.), Бока-Ратон: Chapman & Hall / CRC, ISBN 978-1-58488-506-1
- Cummings, LD (1918), "Заниженный Kirkman бумаги", Бюллетень Американского математического общества , 24 (7): 336-339, DOI : 10,1090 / S0002-9904-1918-03086-3
- Дудени, HE (1917), Развлечение по математике , Нью-Йорк: Дувр
- Dudeney, HE (1958), Развлечение по математике , Dover Recreational Math, Mineola, New York : Dover, ISBN 978-0-486-20473-4
- Грэм, Рональд Л .; Грёчель, Мартин ; Ловас, Ласло (1995), Справочник по комбинаторике, том 2 , Кембридж, Массачусетс : The MIT Press, ISBN 0-262-07171-1
- Хартман, Алан (1980), "Проблема тромбониста Киркмана", Ars Combinatoria , 10 : 19–26
- Лу, Цзяси (1990), Сборник работ Лу Цзяси по комбинаторным схемам, Huhhot: Inner Mongolia People's Press
- Киркман, Томас П. (1847), «Об одной проблеме комбинаций» , Кембриджский и Дублинский математический журнал , Macmillan, Barclay, and Macmillan, II : 191–204
- Киркман, Томас П. (1850), «Заметка о вопросе о призах без ответа» , Кембриджский и Дублинский математический журнал , Macmillan, Barclay and Macmillan, 5 : 255–262
- Лукас, Э. (1883), Récréations Mathématiques , 2 , Paris: Gauthier-Villars, стр. 183–188.
- Рэй-Чаудхури, Дания; Уилсон, Р.М. (1971), «Решение проблемы Киркмана о школьнице, в комбинаторике, Калифорнийский университет, Лос-Анджелес, 1968 », Труды симпозиумов по чистой математике , Провиденс, Род-Айленд : Американское математическое общество, XIX : 187–203, doi : 10.1090 / pspum / 019/9959 , ISBN 978-0-8218-1419-2
- Роуз Болл, WW (1892), Математические развлечения и эссе , Лондон: Macmillan
- Болл, В. В. Роуз ; Coxeter, HSM (1987) [1974], Mathematical Recreations and Essays (13-е изд.), Dover, стр. 287–289, ISBN 0-486-25357-0
Внешние ссылки
- Вайсштейн, Эрик В. "Проблема школьницы Киркмана" . MathWorld .
- Кларрайх, Эрика (9 июня 2015 г.), «Дилемма дизайна решена без дизайна». , Quanta Magazine