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

Комбинаторная задача, предложенная Томасом Пенингтоном Киркманом
Решение задачи Киркмана о школьницах с вершинами, обозначающими девочек, и цветами, обозначающими дни недели [1]

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

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

Решения

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

Существует ровно семь неизоморфных решений задачи о школьницах, которые первоначально были перечислены Фрэнком Нельсоном Коулом в Kirkman Parades в 1922 году. [4] Семь решений обобщены в таблице ниже, где 15 девочек обозначены буквами от A до O.

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

15 ! × ( 1 168 + 1 168 + 1 24 + 1 24 + 1 12 + 1 12 + 1 21 ) {\displaystyle 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 ! × 13 42 {\displaystyle =15!\times {\frac {13}{42}}}
= 404 , 756 , 352 , 000 {\displaystyle =404,756,352,000}
= 2 10 × 3 5 × 5 3 × 7 × 11 × 13 2 {\displaystyle =2^{10}\times 3^{5}\times 5^{3}\times 7\times 11\times 13^{2}} .

История

Оригинальная публикация проблемы

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

  • В 1844 году Уэсли Вулхаус , редактор The Lady's and Gentleman's Diary того времени, задал общий вопрос: «Определите количество комбинаций, которые можно составить из n символов, по p символов в каждой; с тем ограничением, что никакая комбинация из q символов, которая может появиться в любой из них, не должна повторяться в любой другой». Было получено всего два ответа, один неверный, а другой правильный, отвечающий на вопрос с . Поскольку в вопросе не требовалось ничего, кроме количества комбинаций, ничего не было получено об условиях на n , p или q , при которых такое решение может быть достигнуто. n ! q ! ( n q ) ! ÷ p ! q ! ( p q ) ! {\textstyle {\frac {n!}{q!(n-q)!}}\div {\frac {p!}{q!(p-q)!}}}
  • В 1846 году Вулхаус спросил: «Сколько триад можно составить из n символов, так чтобы ни одна пара символов не встречалась среди них более одного раза?». Это эквивалентно повторению его вопроса 1844 года со значениями p = 3 и q = 2. [5]
  • В 1847 году, в возрасте 41 года, Томас Киркман опубликовал свою статью под названием «О проблеме комбинаций» (Kirkman 1847), в которой всесторонне описал и решил проблему построения тройных систем порядка n , где n = 1 или 3 ( mod 6). Он также рассмотрел другие значения n , хотя идеальный баланс был бы невозможен. Он дал две различные последовательности тройных систем, одну для n = 7, 15, 19, 27 и т. д., а другую для n = 9, 13, 25 и т. д. Используя эти предложения, он доказал , что тройные системы существуют для всех значений n = 1 или 3 (mod 6) [7] (не обязательно разрешимые, но тройные системы в целом). Он также подробно описал разрешимые тройные системы в этой статье, особенно для n = 9 и 15; разрешимые тройные системы теперь известны как тройные системы Киркмана. Он не смог окончательно сказать, при каких других значениях n будут существовать разрешимые тройные системы; эта проблема не была решена до 1960-х годов (см. ниже).
  • В 1850 году Киркман сформулировал задачу о 15 школьницах, которая стала гораздо более известной, чем статья 1847 года, которую он уже написал. Было получено несколько решений. Сам Киркман дал решение [8] , которое позже оказалось изоморфным Решению I выше. Киркман утверждал, что это единственное возможное решение, но это было неверно. Решение Артура Кэли [9] позже оказалось изоморфным Решению II. Оба решения могли быть вложены в PG(3,2) , хотя эта геометрия в то время не была известна. Однако, публикуя свои решения задачи о школьницах, Киркман забыл отослать читателей к своей собственной статье 1847 года, и это упущение имело бы серьезные последствия для изобретения и приоритета, как показано ниже.
  • Также в 1850 году Джеймс Джозеф Сильвестр спросил, может ли быть 13 различных решений задачи о 15 школьницах, которые использовали бы все тройки ровно один раз в целом, заметив, что . Другими словами, возможно ли, чтобы девочки маршировали каждый день в течение 13 недель, так что каждые две девочки маршировали вместе ровно один раз в неделю и каждые три девочки маршировали вместе ровно один раз в течение 13 недель? Эта задача была намного сложнее, и вычислительное решение было наконец предоставлено в 1974 году RHF Denniston (см. ниже). ( 15 3 ) = 455 {\textstyle {15 \choose 3}=455} 455 = 13 × 35 {\displaystyle 455=13\times 35}
  • В 1852 году Роберт Ричард Энстис предложил циклическое решение, созданное путем построения пяти троек первого дня, которые должны были быть 0Gg, AbC, aDE, cef, BdF на 15 символах 0ABCDEFGabcdefg , а затем циклического сдвига каждого последующего дня на одну букву, оставляя 0 неизменным (заглавные буквы остаются заглавными, а строчные остаются строчными). [5] Если взять четыре тройки без элемента 0 ( AbC, aDE, cef, BdF ) и преобразовать заглавные буквы в строчные ( abc, ade, cef, bdf ), они образуют то, что позже назовут конфигурацией Паша . [10] Конфигурация Паша станет важной в методах отклонения изоморфов в 20 веке.
  • В 1853 году Якоб Штайнер , совершенно не зная о статье Киркмана 1847 года, опубликовал свою статью под названием Combinatorische Aufgabe , в которой заново ввел понятие тройных систем, но не упомянул о разрешимости в отдельные параллельные классы. Штайнер отметил, что необходимо, чтобы n было равно 1 или 3 (mod 6), но оставил открытым вопрос о том, когда это будет реализовано, не зная, что Киркман уже решил этот вопрос в 1847 году. Поскольку эта статья была более широко прочитана европейским математическим сообществом, тройные системы позже стали известны как тройные системы Штейнера . [5]
  • В 1859 году Мишель Рейсс ответил на вопросы, поднятые Штайнером, используя как методологию, так и обозначения, настолько похожие на работу Киркмана 1847 года (не признавая Киркмана), что последующие авторы, такие как Луиза Каммингс, обвинили его в плагиате . [11] Сам Киркман выразил свою горечь.
  • В 1860 году Бенджамин Пирс объединил несколько разрозненных решений, представленных до сих пор, и показал, что существует три возможные структуры циклических решений: одна соответствует работе Энстиса, другая основана на решении Киркмана и третья — на решении Кэли. [5]
  • В 1861 году Джеймс Джозеф Сильвестр вернулся к проблеме и попытался заявить, что он ее придумал, и что его кембриджские лекции были источником работы Киркмана. Киркман быстро отверг его заявления, заявив, что когда он писал свои статьи, он никогда не был в Кембридже и не слышал о работе Сильвестра. [5] Этот спор о приоритетах привел к ссоре между Сильвестром и Киркманом.
  • В 1861-1862 годах Киркман поссорился с Артуром Кейли из-за не имеющего к этому отношения вопроса (Кейли решил не публиковать серию статей Киркмана по теории групп и многогранникам , что стоило Киркману признания математическим сообществом Европы), что еще больше способствовало его отстранению от математического сообщества. Его всеобъемлющая статья 1847 года, в частности, была забыта, и многие последующие авторы либо приписывали ее Штайнеру, либо Рейссу, не зная об истории.
  • Популярность головоломки школьницы сама по себе не была затронута академическими конфликтами Киркмана, и в конце 19-го и начале 20-го веков головоломка появилась в нескольких книгах по развлекательной математике Эдуарда Лукаса , [12] Рауз Болл , [13] Вильгельма Аренса , [14] и Генри Дьюдени . [15] При жизни Киркман жаловался на то, что его серьезная математическая работа затмевается популярностью задачи школьницы. [16] Киркман умер в 1895 году.
  • В 1918 году серьезная математическая работа Киркмана была вновь привлечена к более широкому вниманию Луизой Даффилд Каммингс в статье под названием «Недооцененная работа Киркмана» [17] , в которой обсуждалась ранняя история этой области и исправлялось историческое упущение.
  • Примерно в то же время Каммингс работал с Фрэнком Нельсоном Коулом и Генри Сили Уайтом над тройными системами. Это достигло кульминации в их знаменитой и широко цитируемой статье 1919 года «Полная классификация систем триад на 15 элементах» [18] , которая была первой статьей, изложившей все 80 решений тройной системы Штейнера размером 15. Они включали как разрешимые, так и неразрешимые системы.
  • В 1922 году Коул опубликовал свою статью Kirkman Parades [4] , в которой впервые были перечислены все семь неизоморфных решений задачи о 15 школьницах, тем самым ответив на давний вопрос с 1850-х годов. Семь решений Киркмана соответствуют четырем различным системам Штейнера, когда разрешимость в параллельные классы снимается как ограничение. Три из систем Штейнера имеют два возможных способа разделения на параллельные классы, что означает два решения Киркмана каждая, в то время как четвертая имеет только один, что дает семь решений Киркмана в целом.
  • В 1960-х годах было доказано, что тройные системы Киркмана существуют для всех порядков n = 3 (mod 6). Это было впервые доказано Лу Цзяси ( китайск . :陆家羲) в 1965 году [19] , и он представил его в Acta Mathematica Sinica, но журнал ошибочно посчитал, что проблема уже решена, и отклонил его статью в 1966 году, что позже было признано серьезной ошибкой. [20] Его последующие академические вклады были прерваны Культурной революцией и снова отклонены. В 1968 году обобщенная теорема была независимо доказана Д.К. Рэем-Чаудхури и Р.М. Уилсоном . [21]
  • В 1974 году Р. Х. Ф. Деннистон решил задачу Сильвестра, построив 13 непересекающихся решений Киркмана и использовав их для покрытия всех 455 троек для 15 девочек. [22] Его решение обсуждается ниже.

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

Джеймс Джозеф Сильвестр в 1850 году спросил, можно ли построить 13 непересекающихся систем Киркмана из 35 троек каждая, чтобы использовать все тройки на 15 девочках. Решение не было найдено до 1974 года, когда Р. Х. Ф. Деннистон из Университета Лестера построил его с помощью компьютера. [22] Идея Деннистона заключалась в создании однонедельного решения Киркмана таким образом, чтобы его можно было переставлять в соответствии с определенной перестановкой цикла длиной 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 троек в каждой, причем каждая строка является орбитой заданной тройки при перестановке. [22] Чтобы построить решение Сильвестра, ни одно решение Киркмана за одну неделю не может использовать две тройки из одной строки, иначе они в конечном итоге столкнутся, когда перестановка будет применена к одной из них. Решение задачи Сильвестра эквивалентно нахождению одной тройки из каждой из 35 строк таким образом, чтобы 35 троек вместе составляли решение Киркмана. Затем он попросил компьютер Elliott 4130 выполнить именно этот поиск, что заняло у него 7 часов, чтобы найти это решение первой недели [22] , обозначив 15 девочек буквами от A до O : ( 15 3 ) = 455 {\textstyle {15 \choose 3}=455}

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

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

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

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

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

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

День 1: 123 456 789День 2: 147 258 369День 3: 159 267 348День 4: 168 249 357

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

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

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

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

Решение 2 имеет 54 автоморфизма, порожденных перестановками (A B D)(C H 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) , и обнаружили, что может быть до 2 непересекающихся систем S(5,6,12), до 2 непересекающихся систем S(4,5,11) и до 5 непересекающихся систем S(3,4,10). Все такие наборы из 2 или 5 соответственно изоморфны друг другу.

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

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

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

В 1910 году Джордж Конвелл решил эту проблему, используя геометрию Галуа . [27]

Поле Галуа 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. [27] : 67 

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

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

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

Задача школьницы состоит в нахождении семи прямых в пятимерном пространстве, которые не пересекаются и такие, что любые две прямые всегда имеют общую семерку. [27] : 74 

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

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

Обобщение

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

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

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

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

Задача Resolvable Coverings рассматривает общий случай девушек, групп, где каждая пара девушек должна быть в одной группе в какой-то момент, но мы хотим использовать как можно меньше дней. Это может быть использовано, например, для планирования плана вращающихся столов, в котором каждая пара гостей должна в какой-то момент оказаться за одним и тем же столом. [36] n {\displaystyle n} g {\displaystyle g}

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

Смотрите также

Примечания

  1. ^ http://mathworld.wolfram.com/KirkmansSchoolgirlProblem.html
  2. ^ Грэм, Гретшель и Ловас 1995
  3. ^ Вайсштейн, Эрик В. «Проблема школьницы Киркмана». MathWorld .
  4. ^ ab Коул 1922
  5. ^ abcdef Ранняя история блочных конструкций Робина Уилсона, Кафедра чистой математики, Открытый университет, Великобритания
  6. ^ Каммингс 1918
  7. ^ Каммингс 1918
  8. ^ Киркман 1850
  9. ^ Кейли 1850
  10. ^ Вайсштейн, Эрик В. , «Конфигурация Паша», MathWorld
  11. ^ Каммингс 1918
  12. ^ Лукас 1883
  13. ^ Рауз Болл 1892
  14. ^ Аренс 1901
  15. ^ Дьюдени 1917
  16. ^ Каммингс 1918
  17. ^ Каммингс 1918
  18. ^ Коул, Ф. Н.; Каммингс, Луиза Д.; Уайт, Х. С. (1917). «Полное перечисление систем триад в 15 элементах». Труды Национальной академии наук . 3 (3): 197– 199. Bibcode : 1917PNAS....3..197C. doi : 10.1073 /pnas.3.3.197 . PMC 1091209. PMID  16576216. 
  19. ^ Лу 1990
  20. ^ Колборн и Диниц 2007, с. 13
  21. ^ Рэй-Чоудхури и Уилсон 1971
  22. ^ abcde Denniston, RHF (1974). "Проблема Сильвестра о 15 школьницах". Дискретная математика . 9 (3): 229– 233. doi : 10.1016/0012-365X(74)90004-1 .
  23. ^ Аудиозапись Kirkman's Ladies
  24. ^ Джонсон, Том; Едржеевски, Франк (2014). «Дамы Киркмана, комбинаторный дизайн». Взгляд на числа . стр.  37–55 . doi :10.1007/978-3-0348-0554-4_4. ISBN 978-3-0348-0553-7.
  25. ^ Чжоу, Цзюньлин; Чан, Яньсюнь (2014). «Новый результат по проблеме Сильвестра». Дискретная математика . 331 : 15–19 . doi :10.1016/j.disc.2014.04.022.
  26. ^ Арайя, Макото и Харада, Масааки. (2010). Взаимно непересекающиеся системы Штейнера S(5, 8, 24) и 5-(24, 12, 48) Конструкции. Electr. J. Comb.. 17.
  27. ^ abcde Конвелл, Джордж М. (1910). «Трехмерное пространство PG(3,2) и его группа». Annals of Mathematics . 11 (2): 60–76 . doi :10.2307/1967582. JSTOR  1967582.
  28. ^ abc Hirschfeld, JWP (1985), Конечные проективные пространства трех измерений , Oxford University Press , ISBN 0-19-853536-8
  29. Болл и Коксетер 1987, стр. 287−289.
  30. ^ Киркман 1847
  31. ^ Рэй-Чоудхури и Уилсон 1971
  32. ^ Лу 1990
  33. ^ Колборн и Диниц 2007, с. 13
  34. ^ Хартман 1980
  35. ^ Banchero, Matías; Robledo, Franco; Romero, Pablo; Sartor, Pablo; Servetti, Camilo (2021). "Ортогональная перегруппировка студентов MBA с максимальным разнообразием с использованием эвристики GRASP/VND". Поиск переменного соседства . Конспект лекций по информатике. Том 12559. С.  58–70 . doi :10.1007/978-3-030-69625-2_5. ISBN 978-3-030-69624-5. S2CID  232314621.
  36. ^ Ван Дам, Эдвин Р.; Хемерс, Виллем Х.; Пик, Морис Б. М. (2003). «Справедливые разрешимые покрытия». Журнал комбинаторных конструкций . 11 (2): 113– 123. doi : 10.1002/jcd.10024 . S2CID  120596961.
  37. ^ Брайант и Дэнзигер 2011
  38. ^ МакРобби, Линда Родригес. «Гибкая математика, стоящая за Spot It!, любимой семейной карточной игрой». Smithsonian Magazine . Получено 01.03.2020 .

Ссылки

  • Аренс, В. (1901), Mathematische Unterhaltungen und Spiele , Лейпциг: Тойбнер
  • Брайант, Даррин; Данцигер, Питер (2011), «О двудольных 2-факторизациях K n − I {\displaystyle K_{n}-I} и проблеме Обервольфаха» (PDF) , Журнал теории графов , 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
  • Дьюдени, Х. Э. (1917), «Развлечения в математике», Nature , 100 (2512), Нью-Йорк: Dover: 302, Bibcode : 1917Natur.100..302., doi : 10.1038/100302a0, S2CID  10245524
  • Грэм, Рональд Л .; Гретшель, Мартин ; Ловас, Ласло (1995), Справочник по комбинаторике, Том 2 , Кембридж, Массачусетс : The MIT Press, ISBN 0-262-07171-1
  • Хартман, Алан ( 1980 ), «Проблема тромбониста Киркмана», Ars Combinatoria , 10 : 19–26
  • Лу, Цзяси (1990), Собрание сочинений Лу Цзяси по комбинаторным расчетам , Хух-Хото: Народная пресса Внутренней Монголии
  • Киркман, Томас П. (1847), «Об одной проблеме в комбинациях», Кембриджский и Дублинский математический журнал , II , Макмиллан, Баркли и Макмиллан: 191–204
  • Киркман, Томас П. (1850), «Заметка о неотвеченном призовом вопросе», Кембриджский и Дублинский математический журнал , 5 , Macmillan, Barclay и Macmillan: 255–262
  • Лукас, Э. (1883), Récréations Mathématiques, vol. 2, Париж: Готье-Виллар, стр.  183–188 .
  • Рэй-Чоудхури, Д.К.; Уилсон, Р.М. (1971), «Решение проблемы школьницы Киркмана, в комбинаторике, Калифорнийский университет, Лос-Анджелес, 1968 », Труды симпозиумов по чистой математике , XIX , Провиденс, Род-Айленд : Американское математическое общество: 187–203 , doi :10.1090/pspum/019/9959, ISBN 978-0-8218-1419-2
  • Рауз Болл, WW (1892), Математические развлечения и эссе , Лондон: Macmillan
  • Кларрайх, Эрика (9 июня 2015 г.), «Дилемма дизайна решена, минус дизайн», Quanta Magazine
  • String (март 2015 г.) — Визуализированное решение, Stack Exchange
Retrieved from "https://en.wikipedia.org/w/index.php?title=Kirkman%27s_schoolgirl_problem&oldid=1268172044"