Проблема школьницы Киркмана

Задача Киркмана о школьнице — это задача комбинаторики, предложенная Томасом Пенингтоном Киркманом в 1850 году как «Запрос VI» в «Дневнике леди и джентльмена» (стр. 48). В проблеме говорится:

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

Решения

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

Существует ровно семь неизоморфных решений проблемы школьницы, первоначально перечисленных Фрэнком Нельсоном Коулом в «Парадах Киркмана» в 1922 году. Семь решений сведены в таблицу ниже, где 15 девочек обозначены буквами от А до О.

Класс решения	Группа автоморфизмов	День 1	День 2	День 3	День 4	День 5	День 6	День 7
Решение I	Заказ 168, созданный (A K G E I L B) (CH M J N O D) и (A M L K O C D) (B H N G I E J). Относится к PG(3,2) .	АВС ДЕФ ПРИНИМАТЬ К СВЕДЕНИЮ ДЖКЛ МНОГО	заместитель генерального директора ХОРОШО CJM ФКН МОТ	УЭО ПЧЕЛА CDN ФХЛ ГКМ	ЦЕЛЬ БДЛ ПРОВЕРЯТЬ ФГО HJN	АФЖ БКО CGL ДХМ А	АХК левов CFI ДЖО ЭЛМ	АЛН БФМ ДАВАТЬ ЧТО ЕСТЬ
Решение II	Заказ 168, созданный (А Б И М Ф С Дж) (Д Н Х К О Л Е) и (A J M I B F C) (D H G N K E O). Относится к PG(3,2) .	АВС ДЕФ ПРИНИМАТЬ К СВЕДЕНИЮ ДЖКЛ МНОГО	заместитель генерального директора ХОРОШО CJM ФКН МОТ	УЭО ПЧЕЛА CDN ФХЛ ГКМ	АФЖ левов ДАВАТЬ ЧТО ЭЛМ	АХК БФМ CGL ДЖО А	ЦЕЛЬ БДЛ ПРОВЕРЯТЬ ФГО HJN	АЛН БКО CFI ДХМ ЕСТЬ
Решение III	Заказ 24, созданный (A H E) (BO K) (C F I) (D J L) (G N M) и (A J B M) (D L E O) (FI) (G K H N)	АВС ДЕФ ПРИНИМАТЬ К СВЕДЕНИЮ ДЖКЛ МНОГО	заместитель генерального директора ХОРОШО CJM ФКН МОТ	УЭО БИМ СДК ФГЛ HJN	АСМ левов КХЛ ДЖО ДУБ	АХК БФДЖ CGO ОТ ЭЛМ	AIJ БДЛ CEN ФХО ГКМ	АЛН БКО CFI ДХМ ЕСТЬ
Решение IV	Заказ 24, созданный (A J M) (C F I) (D E K) (H O L) и (А L B O)(C I) (D K E N) (G J H M)	АВС ДЕФ ПРИНИМАТЬ К СВЕДЕНИЮ ДЖКЛ МНОГО	заместитель генерального директора ХОРОШО CJM ФКН МОТ	УЭО БИМ СДК ФГЛ HJN	АСМ БКО КХЛ ОТ ЕСТЬ	АХК левов CFI ДЖО ЭЛМ	AIJ БДЛ CEN ФХО ГКМ	АЛН БФДЖ CGO ДХМ ДУБ
Solution V	Тетраэдрическая группа 12-го порядка, созданный (А L)(B G)(Е О)(F J)(H K)(I M) и (A B C) (D L G) (F J I) (E K H)	АВС ДЕФ ПРИНИМАТЬ К СВЕДЕНИЮ ДЖКЛ МНОГО	заместитель генерального директора ДЕЛАТЬ ЧМ ФКН МОТ	АЕМ БДЛ СКОЛЬКО ФГО HJN	АФХ БКМ CGL ДЖО А	AIJ левов Генеральный директор ДГК ФЛМ	я БФИ CDN ЭХЛ ГЖМ	АЛН ОТ CFJ ДИМ ЕЭК
Решение VI	Тетраэдрическая группа 12-го порядка, созданный (А L)(B G)(Е О)(H K)(F J)(I M) и (A B C) (D L G) (E K H) (F J I)	АВС ДЕФ ПРИНИМАТЬ К СВЕДЕНИЮ ДЖКЛ МНОГО	заместитель генерального директора ДЕЛАТЬ ЧМ ФКН МОТ	АЕМ БДЛ СКОЛЬКО ФГО HJN	АФХ БКМ CGL ДЖО А	AIJ ОТ CDN ЕЭК ФЛМ	я левов CFJ ДИМ ЭХЛ	АЛН БФИ Генеральный директор ДГК ГЖМ
Решение VII	Заказ 21, созданный (A B L C G D N) (E H K I O J F) и (BGL)(CDN)(EFK)(HIO)	АВС ДЕФ ПРИНИМАТЬ К СВЕДЕНИЮ ДЖКЛ МНОГО	заместитель генерального директора ДЕЛАТЬ ЧМ ФКН МОТ	АЕИ БДН CJO ФХЛ ГКМ	ОГОНЬ ОСОБЫЙ CGN Декабрь ЭЛМ	АХК БФМ CDL EGO ИДЖН	АЖМ БГЛ CFI ДКО ЭНН	АЛН ОТ ПРОВЕРЯТЬ ФГЖ ДИМ

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

$15!\times \left({\frac {1}{168}}+{\frac {1}{168}}+{\frac {1}{24}}+{\frac {1}{24}}+{\frac {1}{12}}+{\frac {1}{12}}+{\frac {1}{21}}\right)$

$=15!\times {\frac {13}{42}}$

$=404,756,352,000$

$=2^{10}\times 3^{5}\times 5^{3}\times 7\times 11\times 13^{2}$.

История

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

Проблема имеет давнюю и легендарную историю. Этот раздел основан на исторических работах, выполненных в разное время Робином Уилсоном. и Луиза Даффилд Каммингс . История такова:

• В 1844 году Уэсли Вулхаус редактор « Дневника леди и джентльмена» , в то время , задал общий вопрос: «Определите количество комбинаций, которые можно составить из n символов, по p символов в каждом; с таким ограничением, что ни одна комбинация не может быть составлена ​​из n символов, по p символов в каждом; из q символов, которые могут появиться в любом из них, должны повторяться в любом другом». Было получено только два ответа: один неправильный, а другой правильный, отвечая на вопрос с ${\textstyle {\frac {n!}{q!(n-q)!}}\div {\frac {p!}{q!(p-q)!}}}$. Поскольку в вопросе не требовалось ничего, кроме количества комбинаций, ничего не было получено об условиях n , p или q, при которых такое решение может быть достигнуто.

• В 1846 году Вулхаус задал вопрос: «Сколько триад можно составить из n символов так, чтобы ни одна пара символов не входила в их число более одного раза?». Это эквивалентно повторению его вопроса 1844 года со значениями p = 3 и q = 2.

• В 1847 году, в возрасте 41 года, Томас Киркман опубликовал свою статью под названием « О проблеме комбинаций» ( Kirkman 1847 ), в которой всесторонне описана и решена проблема построения тройных систем порядка n , где n = 1 или 3 (mod 6). Он также рассматривал другие значения n, хотя идеальный баланс был невозможен. Он дал две разные последовательности тройных систем: одну для n = 7, 15, 19, 27 и т. д., а другую для n = 9, 13, 25 и т. д. Используя эти положения, он доказал, что тройные системы существуют для всех значений. из n = 1 или 3 (по модулю 6) (не обязательно разрешимые, а вообще тройные системы). В этой статье он также подробно описал разрешимые тройные системы, особенно для n = 9 и 15; разрешимые тройные системы теперь известны как тройные системы Киркмана. Он не мог окончательно сказать, при каких других значениях n будут существовать разрешимые тройные системы; эта проблема не была решена до 1960-х годов (см. ниже).

• В 1850 году Киркман поставил задачу о 15 школьницах, которая стала гораздо более известной, чем уже написанная им статья 1847 года. Было получено несколько решений. Киркман сам дал решение позже будет обнаружено, что оно изоморфно Решению I, приведенному выше. Киркман утверждал, что это единственно возможное решение, но это было неверно. Артура Кейли Решение Позже выяснилось, что он изоморфен раствору II. Оба решения могли быть встроены в PG(3,2), хотя в то время эта геометрия не была известна. Однако, публикуя свои решения проблемы школьниц, Киркман не отослал читателей к своей собственной статье 1847 года, и это упущение имело бы серьезные последствия для изобретения и приоритета, как показано ниже.

• Также в 1850 году Джеймс Джозеф Сильвестр задался вопросом, существует ли 13 различных решений задачи о 15 школьницах, в которых использовались бы все ${\textstyle {15 \choose 3}=455}$ в целом утроится ровно один раз, учитывая, что $455=13\times 35$. Другими словами, возможно ли, чтобы девушки маршировали каждый день в течение 13 недель так, чтобы каждые две девушки маршировали вместе ровно один раз в неделю, а каждые три девушки маршировали вместе ровно один раз в течение 13 недель? Эта проблема была намного сложнее, и вычислительное решение наконец было предложено в 1974 году RHF Denniston (см. Ниже).

• В 1852 году Роберт Ричард Анстис предложил циклическое решение, состоящее из пяти троек первого дня: 0Gg, AbC, aDE, cef, BdF из 15 символов 0ABCDEFGabcdefg , а затем циклически сдвигая каждый последующий день на одну букву, оставляя 0 неизменным ( прописные буквы остаются прописными, а строчные остаются строчными). четыре тройки без элемента 0 ( AbC, aDE, cef, BdF Если взять ) и преобразовать верхний регистр в нижний ( abc, ade, cef, bdf ), они образуют то, что позже будет названо конфигурацией Паша . Конфигурация Паша станет важной в методах отторжения изоморфов в 20 веке.

• В 1853 году Якоб Штайнер , совершенно не зная о статье Киркмана 1847 года, опубликовал свою статью под названием Combinatorische Aufgabe , в которой вновь ввел концепцию тройных систем, но не упомянул разрешимость в отдельные параллельные классы. обязательно должно Штайнер отметил, что n быть равно 1 или 3 (по модулю 6), но оставил открытым вопрос, когда это будет реализовано, не зная, что Киркман уже решил этот вопрос в 1847 году. В европейском математическом истеблишменте тройные системы позже стали известны как тройные системы Штейнера .

• В 1859 году Мишель Рейсс ответил на вопросы, поднятые Штайнером, используя как методологию, так и обозначения, настолько похожие на работу Киркмана 1847 года (без упоминания Киркмана), что последующие авторы, такие как Луиза Каммингс, обвинили его в плагиате . Сам Киркман выразил свою горечь.

• В 1860 году Бенджамин Пирс объединил несколько разнородных решений, представленных до сих пор, и показал, что существует три возможные структуры циклических решений: одна соответствует работе Анстиса, одна основана на решении Киркмана и одна — на решении Кэли.

• В 1861 году Джеймс Джозеф Сильвестр вновь обратился к этой проблеме и попытался заявить, что он изобрел ее и что его кембриджские лекции стали источником работы Киркмана. Киркман быстро отверг его утверждения, заявив, что, когда он писал свои статьи, он никогда не был в Кембридже и не слышал о работе Сильвестра. Этот спор о приоритетах привел к ссоре между Сильвестром и Киркманом.

• В 1861–1862 годах Киркман поссорился с Артуром Кэли по несвязанному с этим вопросу (Кели решил не публиковать серию статей Киркмана по теории групп и многогранникам , что стоило Киркману признания математического сообщества в Европе), что еще больше способствовало его будучи отодвинутым на второй план математическим истеблишментом. В частности, его обширная статья 1847 года была забыта, поскольку многие последующие авторы отдавали должное либо Штайнеру, либо Рейссу, не зная об истории.

• На популярность школьной головоломки не повлияли академические конфликты Киркмана, и в конце 19-го и начале 20-го веков головоломка появилась в нескольких развлекательных математических книгах Эдуарда Лукаса . Роуз Болл , Вильгельм Аренс , и Генри Дюдени . При жизни Киркман жаловался, что его серьезная математическая работа затмевается популярностью задачи о школьнице. Киркман умер в 1895 году.

• В 1918 году серьезная математическая работа Киркмана была вновь привлечена к более широкому вниманию Луизой Даффилд Каммингс в статье под названием « Недооцененная статья Киркмана». в котором обсуждалась ранняя история этой области и исправлялись исторические упущения.

• Примерно в то же время Каммингс работал с Фрэнком Нельсоном Коулом и Генри Сили Уайтом над тройными системами. Кульминацией этого стала их знаменитая и широко цитируемая статья 1919 года « Полная классификация триадных систем по 15 элементам». это была первая статья, в которой были изложены все 80 решений системы тройки Штейнера размера 15. Они включали как разрешимые, так и неразрешимые системы.

• В 1922 году Коул опубликовал свою статью «Парады Киркмана». в котором впервые перечислены все семь неизоморфных решений задачи о 15 школьницах, что дает ответ на давний вопрос с 1850-х годов. Семь решений Киркмана соответствуют четырем различным системам Штейнера, когда разрешимость в параллельные классы удалена как ограничение. Три системы Штейнера имеют два возможных способа разделения на параллельные классы, что означает по два решения Киркмана каждый, а четвертая имеет только один, что дает в общей сложности семь решений Киркмана.

• В 1960-е годы было доказано, что системы троек Киркмана существуют для всех порядков n = 3 (mod 6). Впервые это было доказано Лу Цзяси ( китайский : 陆家羲 ) в 1965 году. и он представил ее в Acta Mathematica Sinica, но журнал ошибочно решил, что проблема уже решена, и отклонил его статью в 1966 году, что позже было признано серьезной ошибкой. Его последующие академические вклады были прерваны Культурной революцией и снова отвергнуты. В 1968 году обобщенная теорема была независимо доказана Д. К. Рэем-Чаудхури и Р. М. Уилсоном .

• В 1974 году RHF Denniston решил задачу Сильвестра о построении 13 непересекающихся решений Киркмана и использовании их для покрытия всех 455 троек для 15 девочек. Его решение обсуждается ниже.

Проблема Сильвестра

Джеймс Джозеф Сильвестр в 1850 году спросил, можно ли построить 13 непересекающихся систем Киркмана по 35 троек в каждой, чтобы использовать все ${\textstyle {15 \choose 3}=455}$ тройки по 15 девочек. Никакого решения не было найдено до 1974 года, когда Р.Ф. Деннистон из Университета Лестера сконструировал его с помощью компьютера. Идея Деннистона заключалась в том, чтобы создать однонедельное решение Киркмана таким образом, чтобы его можно было переставлять в соответствии с конкретной перестановкой с длиной цикла 13 для создания непересекающихся решений для последующих недель; он выбрал перестановку с одним 13-периодом и двумя фиксированными точками, например (1 2 3 4 5 6 7 8 9 10 11 12 13)(14)(15). При этой перестановке тройка типа 123 будет отображаться в 234, 345, ... (11, 12, 13), (12, 13, 1) и (13, 1, 2) перед повторением. Таким образом, Деннистон классифицировал 455 троек на 35 строк по 13 троек в каждой, причем каждая строка представляет собой орбиту данной тройки при перестановке. Чтобы построить решение Сильвестра, ни одно недельное решение Киркмана не могло использовать две тройки из одной и той же строки, иначе они в конечном итоге столкнулись бы, когда к одной из них была применена перестановка. Решение проблемы Сильвестра эквивалентно нахождению одной тройки из каждой из 35 строк так, чтобы 35 троек вместе составляли решение Киркмана. Затем он попросил компьютер Elliott 4130 выполнить именно этот поиск, и на поиск решения за первую неделю у него ушло 7 часов: обозначив 15 девушек буквами от A до O :

Day 1 ABJ CEM FKL HIN DGO
Day 2 ACH DEI FGM JLN BKO
Day 3 ADL BHM GIK CFN EJO
Day 4 AEG BIL CJK DMN FHO
Day 5 AFI BCD GHJ EKN LMO
Day 6 AKM DFJ EHL BGN CIO
Day 7 BEF CGL DHK IJM ANO

На этом этапе он прекратил поиск, не стремясь установить уникальность.

Американский композитор-минималист Том Джонсон сочинил музыкальное произведение под названием «Женщины Киркмана» , основанное на решении Деннистона.

По состоянию на 2021 год неизвестно, существуют ли другие неизоморфные решения проблемы Сильвестра и сколько их существует.

9 школьниц и приставок

Эквивалент задачи Киркмана для 9 школьниц приводит к S(2,3,9), аффинной плоскости , изоморфной следующим тройкам в каждый день:

Day 1: 123 456 789
Day 2: 147 258 369
Day 3: 159 267 348
Day 4: 168 249 357

Соответствующая задача Сильвестра требует 7 различных систем S(2,3,9) по 12 троек в каждой, вместе охватывающих все ${\textstyle {9 \choose 3}=84}$ тройки. Это решение было известно Бэйсу (1917), которое было снова найдено с другой стороны Эрлом Крамером и Дейлом Меснером в статье 1974 года под названием «Пересечения среди систем Штейнера» (J Combinatorial Theory, Vol 16, стр. 273-285). Действительно может быть 7 непересекающихся систем S(2,3,9), и все такие множества из 7 попадают в две неизоморфные категории размером 8640 и 6720 с 42 и 54 автоморфизмами соответственно.

Solution 1:
             Day 1          Day 2          Day 3          Day 4
Week 1    ABC.DEF.GHI    ADG.BEH.CFI    AEI.BFG.CDH    AFH.BDI.CEG
Week 2    ABD.CEH.FGI    ACF.BGH.DEI    AEG.BCI.DFH    AHI.BEF.CDG
Week 3    ABE.CDI.FGH    ACG.BDF.EHI    ADH.BGI.CEF    AFI.BCH.DEG
Week 4    ABF.CEI.DGH    ACD.BHI.EFG    AEH.BCG.DFI    AGI.BDE.CFH
Week 5    ABG.CDE.FHI    ACH.BEI.DFG    ADI.BCF.EGH    AEF.BDH.CGI
Week 6    ABH.CDF.EGI    ACI.BDG.EFH    ADE.BFI.CGH    AFG.BCE.DHI
Week 7    ABI.CFG.DEH    ACE.BFH.DGI    ADF.BEG.CHI    AGH.BCD.EFI

Решение 1 имеет 42 автоморфизма, порожденных перестановками (A I D C F H)(B G) и (CF D H E I)(B G). Применение 9! = 362880 перестановок ABCDEFGHI, существует 362880/42 = 8640 различных решений, все изоморфны раствору 1.

Solution 2:
             Day 1          Day 2          Day 3          Day 4
Week 1    ABC.DEF.GHI    ADG.BEH.CFI    AEI.BFG.CDH    AFH.BDI.CEG
Week 2    ABD.CEH.FGI    ACF.BGH.DEI    AEG.BCI.DFH    AHI.BEF.CDG
Week 3    ABE.CGH.DFI    ACI.BFH.DEG    ADH.BGI.CEF    AFG.BCD.EHI
Week 4    ABF.CGI.DEH    ACE.BDG.FHI    ADI.BCH.EFG    AGH.BEI.CDF
Week 5    ABG.CDI.EFH    ACH.BDF.EGI    ADE.BHI.CFG    AFI.BCE.DGH
Week 6    ABH.CEI.DFG    ACD.BFI.EGH    AEF.BCG.DHI    AGI.BDE.CFH
Week 7    ABI.CDE.FGH    ACG.BDH.EFI    ADF.BEG.CHI    AEH.BCF.DGI

Решение 2 имеет 54 автоморфизма, порожденных перестановками (AB D)(CH E)(F G I) и (A I F D E H)(B G). Применение 9! = 362880 перестановок ABCDEFGHI, имеется 362880/54 = 6720 различных решений, все изоморфны раствору 2.

Таким образом, всего существует 8640 + 6720 = 15360 решений, попадающих в две неизоморфные категории.

Помимо S(2,3,9), Крамер и Меснер исследовали другие системы, которые могут быть получены из S(5,6,12) , и обнаружили, что может существовать до двух непересекающихся систем S(5,6,12). , до 2 непересекающихся систем S(4,5,11) и до 5 непересекающихся систем S(3,4,10). Все такие наборы из 2 или 5 соответственно изоморфны друг другу.

Более крупные системы и продолжающиеся исследования

В 21 веке аналоги проблемы Сильвестра посещались другими авторами под такими терминами, как «Непересекающиеся системы Штейнера», «Непересекающиеся системы Киркмана» или «LKTS» (большие множества тройных систем Киркмана) для n > 15. Подобные наборы непересекающихся систем Штейнера были исследованы также для системы Штейнера S (5,8,24) помимо тройных систем.

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

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

Поле Галуа 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. проходит

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

Когда выбраны две точки A и B линии ABC, каждая из пяти других линий, проходящих через A, пересекается только с одной из пяти других линий, проходящих через B. Пять точек, определяемых пересечениями этих пар линий вместе с две точки А и В мы обозначаем «семеркой».

Семерка определяется любыми двумя ее точками. Каждая из 28 точек от S лежит в двух семерицах. Всего 8 гептад. Проективная линейная группа PGL(3,2) изоморфна знакопеременной группе на 8 семерицах.

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

Спреды и упаковка

В PG(3,2) разбиение точек на линии называется разбросом , а разбиение линий на развороты — упаковкой или параллелизмом . В наличии 56 разворотов и 240 упаковок. Когда Хиршфельд рассматривал эту проблему в своих «Конечных проективных пространствах трех измерений» (1985), он отметил, что некоторые решения соответствуют упаковкам PG (3,2), по существу, как описано Конвеллом выше: и он представил два из них.

Обобщение

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

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

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

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

Проблема разрешимых покрытий рассматривает общую $n$ девушки, $g$ групповой случай, когда каждая пара девочек в какой-то момент должна находиться в одной группе, но мы хотим использовать как можно меньше дней. Это можно, например, использовать для планирования плана ротации столов, в котором каждая пара гостей в какой-то момент должна находиться за одним столом.

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

См. также

• Стратегия совместного обучения для повышения взаимодействия в рамках преподавания в классе
• Двойная карточная игра
• Прогрессивный дизайн званого обеда
• Speed ​​Networking События
• Спортивные соревнования
• Комбинаторика
• Р. М. Уилсон
• Бедра К. Рэй-Чаудхури
• Дискретная математика

Ссылки

• Аренс, В. (1901), Математические развлечения и игры , Лейпциг: Тойбнер
• Брайант, Дэррин; Данцигер, Питер (2011), «О двудольных 2-факторизациях $K_{n}-I$ и проблема Обервольфаха» (PDF) , Journal of The Graph Theory , 68 (1): 22–37, doi : 10.1002/jgt.20538 , MR   2833961 , S2CID   7478839
• Кэли, А. (1850), «О триадном расположении семи и пятнадцати вещей» , Philosophical Magazine , 37 (247): 50–53, doi : 10.1080/14786445008646550
• Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007), Справочник по комбинаторным планам (2-е изд.), Бока-Ратон: Chapman & Hall/CRC, ISBN  978-1-58488-506-1
• Коул, Ф.Н. (1922), «Парады Киркмана», Бюллетень Американского математического общества , 28 (9): 435–437, doi : 10.1090/S0002-9904-1922-03599-9
• Каммингс, Л.Д. (1918), «Недооцененная статья Киркмана», Бюллетень Американского математического общества , 24 (7): 336–339, doi : 10.1090/S0002-9904-1918-03086-3
• Дадени, HE (1917), «Забавы по математике», Nature , 100 (2512), Нью-Йорк: Дувр: 302, Бибкод : 1917Natur.100..302. , doi : 10.1038/100302a0 , S2CID   10245524
  • Дадени, HE (1958), Математические развлечения , Дуврская развлекательная математика, Минеола, Нью-Йорк : Дувр, ISBN  978-0-486-20473-4
• Грэм, Рональд Л .; Гретшель, Мартин ; Ловас, Ласло (1995), Справочник по комбинаторике, Том 2 , Кембридж, Массачусетс : The MIT Press, ISBN  0-262-07171-1
• Хартман, Алан (1980), «Проблема тромбониста Киркмана», Ars Combinatoria , 10 : 19–26.
• Лу, Цзяси (1990), Собрание сочинений Лу Цзяси по комбинаторным расчетам , Хух-Хото: Народная пресса Внутренней Монголии
• Киркман, Томас П. (1847), «О проблеме комбинаций» , Кембриджский и Дублинский математический журнал , II , Макмиллан, Барклай и Макмиллан: 191–204.
• Киркман, Томас П. (1850), «Заметка о призовом вопросе, оставшемся без ответа» , The Cambridge and Dublin Mathematical Journal , 5 , Macmillan, Barclay and Macmillan: 255–262.
• Лукас, Э. (1883), Математическое воссоздание , вып. 2, Париж: Готье-Виллар, стр. 183–188
• Рэй-Чаудхури, Дания; Уилсон, Р.М. (1971), «Решение проблемы Киркмана о школьнице, по комбинаторике, Калифорнийский университет, Лос-Анджелес, 1968 », Труды симпозиумов по чистой математике , XIX , Провиденс, Род-Айленд : Американское математическое общество: 187–203, doi : 10.1090/pspum/019/9959 , ISBN  978-0-8218-1419-2
• Роуз Болл, WW (1892), Математические развлечения и очерки , Лондон: Macmillan
  • Болл, У. В. Роуз ; Коксетер, HSM (1987) [1974], Математические развлечения и очерки (13-е изд.), Дувр, стр. 287–289, ISBN  0-486-25357-0

Внешние ссылки

• Вайсштейн, Эрик В. «Проблема школьницы Киркмана» . Математический мир .
• Кларрайх, Эрика (9 июня 2015 г.), «Дилемма дизайна решена, без дизайна». , журнал «Кванта»
• String (март 2015 г.) — визуализация решения , Stack Exchange