Задача Киркмана о школьницах

Материал из testwiki
Перейти к навигации Перейти к поиску
Оригинальная публикация задачи

Задача Киркмана о школьницах — это комбинаторная задача, предложенная Томасом Пенингтоном Киркманом в 1850 году как Вопрос VI в журнале The Lady's and Gentleman's Diary (журнал занимательной математики, издававшийся между 1841 и 1871). Задача гласит:

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

Решение

Если девушек пронумеровать от 0 до 14, следующее распределение будет одним из решенийШаблон:Sfn:

Воскре-
сенье 		Поне-
дельник 		Вторник Среда Четверг Пятница Суббота
 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

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

Существует семь неизоморфных решений задачи о школьницахШаблон:Sfn. Два из них можно визуализировать как отношения между тетраэдром и его вершинами, рёбрами и гранямиШаблон:Sfn. Подход, использующий трёхмерную проективную геометрию над Шаблон:Не переведено 5, дан ниже.

Решение XOR троек

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

Воскре-
сенье 		Поне-
дельник 		Вторник Среда Четверг Пятница Суббота
0001, 0010, 0011 0001, 0100, 0101 0001, 0110, 0111 0001, 1000, 1001 0001, 1010, 1011 0001, 1100, 1101 0001, 1110, 1111
0100, 1000, 1100 0010, 1000, 1010 0010, 1001, 1011 0010, 1100, 1110 0010, 1101, 1111 0010, 0100, 0110 0010, 0101, 0111
0101, 1010, 1111 0011, 1101, 1110 0011, 1100, 1111 0011, 0101, 0110 0011, 0100, 0111 0011, 1001, 1010 0011, 1000, 1011
0110, 1011, 1101 0110, 1001, 1111 0100, 1010, 1110 0100, 1011, 1111 0101, 1001, 1100 0101, 1011, 1110 0100, 1001, 1101
0111, 1001, 1110 0111, 1011, 1100 0101, 1000, 1101 0111, 1010, 1101 0110, 1000, 1110 0111, 1000, 1111 0110, 1010, 1100

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

История

Первое решение опубликовал Артур КэлиШаблон:Sfn. За ним быстро последовало решение самого КиркманаШаблон:Sfn, которое было дано как специальный случай его комбинаторного размещения, опубликованного тремя годами ранееШаблон:Sfn. Д. Д. Сильвестр также исследовал задачу и закончил утверждением, что Киркман украл идею у него. Головоломка появилась в нескольких занимательных математических книгах на стыке веков у ЛукасаШаблон:Sfn, Роуз БоллаШаблон:Sfn, АаренсаШаблон:Sfn и ДьюдениШаблон:Sfn.

Киркман часто объяснял, что его большая статья Шаблон:Harv была полностью вызвана огромным интересом к задачеШаблон:Sfn.

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

В 1910 задачу рассмотрел Джорж Конвелл с помощью геометрии ГалуаШаблон:Sfn.

Поле Галуа Шаблон:Не переведено 5 с двумя элементами использовалось с четырьмя однородными координатами для формирования PG(3,2) с 15 точками, 3 точками на прямой, 7 точками и 7 прямыми на плоскости. Плоскость можно считать полным четырёхугольником вместе с прямыми через его диагональные точки. Каждая точка лежит на 7 прямых и есть в общем счёте 35 прямых.

Прямые пространства PG(3,2) определяются их плюкеровыми координатами в PG(5,2) с 63 точками, 35 из которых представляют прямые в PG(3,2). Эти 35 точек образуют поверхность S, известную как Шаблон:Не переведено 5. Для каждой из 28 точек, не лежащих на S, существует 6 прямых через эту точку, которые не пересекаются с SШаблон:Sfn.

Как число дней в неделе, семёрка играет важную роль в решении: Шаблон:Quote Семёрка определяется двумя её точками. Каждая из 28 точек вне S лежит на двух семёрках. Есть 8 семёрок. Шаблон:Не переведено 5 PGL(3,2) изоморфна знакопеременной группе на 8 семёркахШаблон:Sfn.

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

Обобщение

Задачу можно обобщить до n учениц, где n должно быть числом, равным произведением нечётного числа на 3 (то есть, n≡3(mod6)), прогуливающиеся тройками 12(n−1) дней с условием, снова, что никакая пара девушек не прогуливается в том же ряду дваждыШаблон:Sfn. Решение этого обобщения является системой троек Штейнера S(2, 3, 6t + 3) с параллельностью (то есть системой, в которой каждые 6t + 3 элементов оказываются ровно раз в каждом блоке из 3-элементных множеств), известной как система КиркманаШаблон:Sfn. Это обобщение задачи, которое первоначально обсуждал Киркман, а знаменитый частный случай n=15 он обсуждал позднееШаблон:Sfn. Полное решение общего случая опубликовали Д. К. Рей-Чадхури и Р. М. Вильсон в 1968 годуШаблон:Sfn, хотя задача уже была решена китайским математиком Лю Джакси (陆家羲) в 1965 годуШаблон:Sfn, но в то время решение ещё опубликовано не былоШаблон:Sfn.

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

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Rq

Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Задача_Киркмана_о_школьницах&oldid=19783