Альфапедия

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

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

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

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

СОДЕРЖАНИЕ
  • 1 Решения
  • 2 История
  • 3 проблема Сильвестра
    • 3.1 9 школьниц и расширений
    • 3.2 Более крупные системы и продолжающиеся исследования
  • 4 Геометрия Галуа
  • 5 Спреды и упаковка
  • 6 Обобщение
  • 7 Другие приложения
  • 8 Примечания
  • 9 ссылки
  • 10 Внешние ссылки
Решения

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

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

Класс решения Группа автоморфизмов 1 день День 2 3 день День 4 5 день 6 день 7 день
Решение I Заказ 168, созданный (A K G E I L B) (C H M J N O D) и (AM L K O C D) (B H N G I E J). Относится к PG (3,2). ABC DEF GHI JKL MNO ADG BEH CJM FKN ILO АОЭ BIJ CDN FHL ГКМ AIM BDL CEK FGO HJN AFJ BKO CGL DHM EIN AHK BGN CFI DJO ELM ALN BFM CHO DIK EGJ
Решение II Заказ 168, созданный (A B I M F C J) (D N H K O L E) и (A J M I B F C) (D H G N K E O). Относится к PG (3,2). ABC DEF GHI JKL MNO ADG BEH CJM FKN ILO АОЭ BIJ CDN FHL ГКМ AFJ BGN CHO DIK ELM AHK BFM CGL DJO EIN AIM BDL CEK FGO HJN ALN BKO CFI DHM EGJ
Решение III Порядок 24, созданный (A H E) (B O K) (C F I) (D J L) (G N M) и (A J B M) (D L E O) (F I) (G K H N) ABC DEF GHI JKL MNO ADG BEH CJM FKN ILO AEO BIM CDK FGL HJN AFM BGN CHL DJO EIK АХК BFJ ОЦП DIN ELM AIJ BDL CEN FHO GKM ALN BKO CFI DHM EGJ
Решение IV Порядок 24, созданный (A J M) (C F I) (D E K) (H O L) и (A L B O) (C I) (D K E N) (G J H M) ABC DEF GHI JKL MNO ADG BEH CJM FKN ILO AEO BIM CDK FGL HJN AFM BKO CHL DIN EGJ AHK BGN CFI DJO ELM AIJ BDL CEN FHO GKM ALN BFJ CGO DHM EIK
Решение V Группа тетраэдра порядка 12, порожденная (A L) (B G) (E O) (F J) (H K) (I M) и (AB C) (D L G) (F J I) (E K H) ABC DEF GHI JKL MNO ADG BEJ CHM FKN ILO AEM BDL CIK FGO HJN AFH BKM ВКТ DJO EIN AIJ BGN Генеральный директор DHK FLM AKO BFI CDN EHL GJM ALN BHO CFJ DIM EGK
Решение VI Группа тетраэдра порядка 12, порожденная (A L) (B G) (E O) (H K) (F J) (I M) и (AB C) (D L G) (E K H) (F J I) ABC DEF GHI JKL MNO ADG BEJ CHM FKN ILO AEM BDL CIK FGO HJN AFH BKM ВКТ DJO EIN AIJ BHO CDN EGK FLM AKO BGN CFJ DIM EHL Генеральный директор ALN BFI DHK GJM
Решение VII Порядок 21, созданный (A B L C G D N) (E H K I O J F) и (B G L) (C D N) (E F K) (H I O) ABC DEF GHI JKL MNO ADG BEJ CHM FKN ILO АЕИ BDN CJO FHL ГКМ AFO BIK CGN DHJ ELM AHK BFM CDL EGO IJN AJM BGL CFI ДКО EHN ALN BHO CEK FGJ DIM

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

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

знак равно 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}}.

История

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

  • В 1844 году Уэсли Вулхаус, редактор «Дневника леди и джентльменов» в то время, задал общий вопрос: «Определите количество комбинаций, которые можно составить из n символов, по p символов в каждой; с этим ограничением, что никакая комбинация из q символов, которые могут появиться в любом из них, должны повторяться в любом другом ". Было получено только два ответа, один неверный, а другой правильно ответил на вопрос с помощью. Поскольку вопрос не требовал ничего, кроме количества комбинаций, ничего не было получено об условиях на n, p или q, когда такое решение могло быть достигнуто. п ! q ! ( п - q ) ! ÷ п ! q ! ( п - q ) ! {\ displaystyle {\ frac {n!} {q! (nq)!}} \ div {\ frac {p!} {q! (pq)!}}}
  • В 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 (mod 6) (не обязательно разрешимые, но вообще тройные системы). Он также подробно описал разрешимые тройные системы в этой статье, особенно для n = 9 и 15; разрешимые тройные системы теперь известны как тройные системы Киркмана. Он не мог окончательно сказать, для каких других значений n будут существовать разрешимые тройные системы; эта проблема не была решена до 1960-х годов (см. ниже).
  • В 1850 году Киркман поставил задачу о 15 школьницах, которая станет гораздо более известной, чем статья 1847 года, которую он уже написал. Было получено несколько решений. Сам Киркман дал решение, которое позже окажется изоморфным Решению I. Киркман утверждал, что это единственно возможное решение, но это было неверно. Решение Артура Кэли позже окажется изоморфным Решению II. Оба решения можно было встроить в PG (3,2), хотя в то время эта геометрия не была известна.
  • Также в 1850 году Джеймс Джозеф Сильвестр спросил, могут ли быть 13 различных решений проблемы 15 школьниц, которые бы использовали все 15C3 = 455 троек ровно один раз, заметив, что 455 = 13 x 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 (mod 6), но оставил открытым вопрос о том, когда это будет реализовано, не зная, что Киркман уже решил этот вопрос в 1847 году. Европейский математический истеблишмент, тройные системы позже стали известны как тройные системы Штейнера.
  • В 1859 году Мишель Рейсс ответил на вопросы, поставленные Штайнером, используя как методологию, так и обозначения, аналогичные работе Киркмана 1847 года (без упоминания Киркмана), что последующие авторы, такие как Луиза Каммингс, выразили свои сомнения относительно его оригинальности. Сам Киркман выразил горечь.
  • В 1860 году Бенджамин Пирс объединил несколько разрозненных решений, представленных до сих пор, и показал, что существуют три возможных циклических структуры решений: одна соответствует работе Анстис, одна основана на решении Киркмана и одна - на решении Кэли.
  • В 1861 году Джеймс Джозеф Сильвестр вернулся к проблеме и попытался заявить, что он ее изобрел, что его кембриджские лекции были источником работы Киркмана. Киркман быстро опроверг его утверждения, заявив, что, когда он писал свои статьи, он никогда не был в Кембридже и не слышал о работе Сильвестра.
  • До начала 20-го века работа Киркмана 1847 года в значительной степени не включалась в математическую литературу, причем тройные системы в основном принадлежали Штайнеру и другим. При жизни Киркман жаловался, что его математическая работа затмевается популярностью задачи школьницы. Киркман также поссорился с Кэли и Королевским обществом примерно в 1862 году из-за отказа от публикации серии статей Киркмана по теории групп и многогранникам, что, возможно, способствовало его отстранению от работы.
  • В 1918 году серьезная математическая работа Киркмана была возвращена более широкому вниманию Луизы Даффилд Каммингс в статье под названием «Недооцененная статья Киркмана», в которой обсуждалась ранняя история и исправлено упущение.
  • Примерно в то же время Каммингс работал с Фрэнком Нельсоном Коулом и Генри Сили Уайтом над тройными системами. Это привело к их статье 1919 г. « Полная классификация систем триад на 15 элементах», которая была первой статьей, в которой были изложены все 80 решений системы троек Штейнера размера 15. Они включали как разрешимые, так и неразрешимые системы.
  • В 1922 году Коул опубликовал свою статью « Парады Киркмана», в которой впервые перечислил все семь неизоморфных решений задачи «15 школьниц», таким образом отвечая на давний вопрос с 1850-х годов. Семь решений Киркмана соответствуют четырем различным системам Штейнера, когда разрешимость на параллельные классы удаляется как ограничение. Три системы Штейнера имеют два возможных способа разделения на параллельные классы, то есть по два решения Киркмана каждое, а четвертая имеет только одно, что дает в целом семь решений Киркмана.
  • В 1960-х годах было доказано, что тройные системы Киркмана существуют для всех порядков n = 3 (mod 6). Впервые это было доказано Лу Цзяси ( кит. :陆 家 羲) в 1965 году, но в то время не было опубликовано. В 1968 году это было независимо доказано Д.К. Рей-Чаудхури и Р.М. Уилсоном.
  • В 1974 году RHF Denniston решил задачу Сильвестра построить 13 непересекающихся решений Киркмана и использовать их для покрытия всех 455 троек для 15 девочек. Его решение обсуждается ниже.
Проблема сильвестра

Джеймс Джозеф Сильвестр в 1850 году спросил, можно ли построить 13 непересекающихся систем Киркмана по 35 троек в каждой, чтобы использовать все 15C3 = 455 троек на 15 девушках. Решение не было найдено до 1974 года, когда RHF Denniston из Университета Лестера сконструировал его с помощью компьютера. Идея Деннистона заключалась в том, чтобы создать однонедельное решение Киркмана таким образом, чтобы его можно было переставлять в соответствии с конкретной перестановкой длины цикла 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 троек в каждой, вместе покрывающих все 9C3 = 84 тройки. Это решение было известно Бэйсу (1917), которое было найдено снова с другого направления Эрлом Крамером и Дейлом Меснером в статье 1974 года, озаглавленной « Пересечения между системами Штейнера» (J Combinatorial Theory, Vol 16, pp. 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) и (C F 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 автоморфизма, порожденных перестановками (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 соответственно изоморфны друг другу.

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

В XXI веке аналоги проблемы Сильвестра посещались другими авторами под такими терминами, как «дизъюнктные системы Штейнера», «дизъюнктные системы Киркмана» или «LKTS» (большие множества тройных систем Киркмана) для n gt; 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. Пять точек, определяемых пересечениями этих пар прямых, вместе с две точки A и B мы обозначаем «гептадой».

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

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

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

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

Обобщение

Проблема может быть обобщена на девочек, где должно быть нечетное число, кратное 3 (то есть), которые ходят тройняшками в течение нескольких дней, с требованием, опять же, чтобы ни одна пара девочек не ходила в одном ряду дважды. Решением этого обобщения является система троек Штейнера, S (2, 3, 6 t + 3) с параллелизмом (то есть такая, в которой каждый из 6 t + 3 элементов встречается ровно один раз в каждом блоке 3-элементной множеств), известную как тройная система Киркмана. Именно это обобщение проблемы обсуждал Киркман первым, тогда как знаменитый частный случай был предложен только позже. Полное решение общего случая было опубликовано DK Ray-Chaudhuri и RM Wilson в 1968 году, хотя оно уже было решено Лу Цзяси ( китайский :家 家 羲) в 1965 году, но не было опубликовано в то время. п {\ displaystyle n} п {\ displaystyle n} п ≡ 3 ( мод 6 ) {\ Displaystyle п \ эквив 3 {\ pmod {6}}} 1 2 ( п - 1 ) {\ displaystyle {\ frac {1} {2}} (n-1)} п знак равно 15 {\ displaystyle n = 15}

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

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

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

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

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

Другие приложения
Примечания
использованная литература
внешние ссылки
Последняя правка сделана 2023-03-20 05:30:55
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте