Проблема школьницы Киркманса - Википедия - Kirkmans schoolgirl problem

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

Проблема школьницы Киркмана проблема в комбинаторика предложенный преп. Томас Пенингтон Киркман в 1850 г. как Запрос VI в Дневник леди и джентльмена (стр.48). В проблеме говорится:

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

Решение

Если девочки пронумерованы от 0 до 14, следующим решением будет следующее:^[2]

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

Есть семь не-изоморфный решения проблемы школьницы.^[4] Два из них можно визуализировать как отношения между тетраэдром и его вершинами, ребрами и гранями.^[5]Подход, использующий проективную геометрию трех измерений над GF (2) приведен ниже.

Тройное решение XOR

Если девушки пронумерованы двоичными числами от 0001 до 1111, следующее решение является одним из решений, при котором для любых трех девушек, образующих группу, побитовое исключающее ИЛИ любых двух равно третьей:

Это решение имеет геометрическую интерпретацию в связи с Геометрия Галуа и PG (3,2). Взять тетраэдр и пометьте его вершины как 0001, 0010, 0100 и 1000. Обозначьте его шесть центров ребер как XOR вершин этого ребра. Обозначьте четыре центра граней как XOR трех вершин этой грани, и центр тела получит метку 1111. Тогда 35 триад решения XOR точно соответствуют 35 строкам PG (3,2). Каждый день соответствует развороту, а каждая неделя - упаковке..^[6]

История

Первое решение было опубликовано Артур Кэли.^[7] Вскоре за этим последовало собственное решение Киркмана.^[8] которое было дано как частный случай его размышлений о комбинаторных механизмах, опубликованных за три года до этого.^[9] Дж. Дж. Сильвестр также исследовал проблему и в итоге заявил, что Киркман украл у него идею. Эта головоломка появилась в нескольких книгах по развлекательной математике на рубеже веков Лукаса,^[10] Роуз Болл,^[11] Аренс,^[12] и Дудени.^[13]

Киркман часто жаловался на то, что его содержательная статья (Киркман 1847 ) полностью затмил популярный интерес к проблеме школьницы.^[14]

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

В 1910 г. проблема была решена с помощью Геометрия Галуа Джорджа Конвелла.^[15]

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

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

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

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

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

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

А раздел точек в прямые называется распространять, а разбиение разворотов геометрии называется упаковка.^[16]:66 Когда Hirschfeld рассмотрел проблему в своем Конечные проективные пространства трех измерений (1985), он отметил, что некоторые решения соответствуют упаковкам PG (3,2), по существу, как описано Конвеллом выше,^[16]:91 и он представил два из них.^[16]:75

Обобщение

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

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

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

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

Проблема разрешимых покрытий рассматривает общие ${ displaystyle n}$ девушки, ${ displaystyle g}$ Групповой случай, когда каждая пара девочек должна быть в одной группе в какой-то момент, но мы хотим использовать как можно меньше дней. Это можно, например, использовать для составления плана смены стола, в котором каждая пара гостей должна в какой-то момент находиться за одним столом.^[21]

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

Другие приложения

• Совместное обучение стратегия увеличения взаимодействия в классе
• Добл карточная игра^[23]
• Прогрессивный ужин партийный дизайн
• Скорость сети События
• Спортивные соревнования

Примечания

Рекомендации

• Аренс, В. (1901), Mathematische Unterhaltungen und Spiele, Лейпциг: Тойбнер
• Брайант, Даррин; Данцигер, Питер (2011), "О двудольных 2-факторизациях ${ displaystyle K_ {n} -I}$ и проблема Обервольфаха " (PDF), Журнал теории графов, 68 (1): 22–37, Дои:10.1002 / jgt.20538, МИСТЕР  2833961
• Колборн, Чарльз Дж .; Диниц, Джеффри Х. (2007), Справочник по комбинаторным схемам (2-е изд.), Бока-Ратон: Chapman & Hall / CRC, ISBN  978-1-58488-506-1
• Каммингс, Л. (1918), «Недооцененная статья Киркмана», Бюллетень Американского математического общества, 24 (7): 336–339, Дои:10.1090 / S0002-9904-1918-03086-3
• Дудени, Х. (1917), Развлечения по математике, Нью-Йорк: Дувр
  • Дудени, Х. (1958), Развлечения по математике, Дуврская развлекательная математика, Минеола, Нью-Йорк: Дувр, ISBN  978-0-486-20473-4
• Грэм, Рональд Л.; Грётшель, Мартин; Ловас, Ласло (1995), Справочник по комбинаторике, Том 2, Кембридж, Массачусетс: MIT Press, ISBN  0-262-07171-1
• Хартман, Алан (1980), "Проблема тромбониста Киркмана", Ars Combinatoria, 10: 19–26
• Лу, Цзяси (1990), Собрание сочинений Лу Цзяси о комбинаторных конструкциях, Хух-Хото: Народная пресса Внутренней Монголии
• Киркман, Томас П. (1847), «О проблеме сочетаний», Кембриджский и Дублинский математический журнал, Макмиллан, Барклай и Макмиллан, II: 191–204
• Киркман, Томас П. (1850), «Примечание к вопросу о призах, на который нет ответа», Кембриджский и Дублинский математический журнал, Макмиллан, Барклай и Макмиллан, 5: 255–262
• Лукас, Э. (1883), Récréations Mathématiques, 2, Paris: Gauthier-Villars, стр. 183–188.
• Ray-Chaudhuri, D.K .; Уилсон, Р. (1971), "Решение проблемы школьницы Киркмана, в Комбинаторика, Калифорнийский университет, Лос-Анджелес, 1968 г.", Труды симпозиумов по чистой математике, Провиденс, Род-Айленд: Американское математическое общество, XIX: 187–203, Дои:10.1090 / pspum / 019/9959, ISBN  978-0-8218-1419-2
• Роуз Болл, W.W. (1892), Математические развлечения и эссе, Лондон: Macmillan
  • Болл, W.W. Роза; Кокстер, H.S.M. (1987) [1974], Математические развлечения и эссе (13-е изд.), Довер, стр. 287–289, ISBN  0-486-25357-0

внешняя ссылка

• Вайсштейн, Эрик В. "Проблема школьницы Киркмана". MathWorld.
• Кларрайх, Эрика (9 июня 2015 г.), «Дизайнерская дилемма решена без дизайна»., Журнал Quanta