Проблема комбинаторики: задача Киркмана о школьницах
Задача о 15 школьницах долгое время считалась одной из самых знаменитых проблем в комбинаторике. Её предложил Томас Пеннингтон Киркман (1806–1895) — английский математик, алгебраист, член Лондонского королевского общества (1881). Его труды являются первым систематическим изложением элементов теории групп на английском языке. Также он внёс большой вклад в комбинаторику.
Задача о 15 школьницах была опубликована в 1850 году как Вопрос VI в журнале The Lady's and Gentleman's Diary (журнал занимательной математики, издававшийся между 1841 и 1871 годами).
«Пятнадцать молодых девушек в школе прогуливаются по три в ряд семь дней, каждый день. Требуется распределить их на каждую прогулку так, чтобы никакие две девушки не шли в том же ряду».
(Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily, so that no two shall walk twice abreast).
В силу своей ложной простоты задача быстро стала знаменитой.
Одно из возможных решений приведено в таблице ниже. В ней девушки пронумерованы от 0 до 14.
Известно, что существует семь неизоморфных решений этой задачи о 15 школьницах.
(Изоморфизм — это биективное отображение между множествами с одинаковой структурой, сохраняющее эту структуру).
Первое решение опубликовал Артур Кэли (1850). За ним быстро последовало решение самого Киркмана (1850). Оно было дано как специальный случай его комбинаторного размещения, опубликованного тремя годами ранее (1847). Д. Д. Сильвестр также исследовал эту задачу. Головоломка появилась в нескольких занимательных математических книгах.
Комбинаторные схемы стали очень популярны и применялись даже в мошенничествах с азартными играми. Была история, когда преступный картель заработал миллионы долларов за семь лет, скупая билеты со всеми возможными комбинациями 5 из 46 в лотерее 6 из 46, если стоимость билетов была ниже, чем дополнительные бонусы за выигрыш 5 из 46 плюс вероятность выигрыша джекпота.
Другое решение задачи даётся XOR-тройками. Если девушек перенумеровать двоичными числами от 0001 до 1111, следующее распределение является решением, таким, что для любых трёх девушек, образующих группу, побитное XOR двух чисел даёт третье.
(Побитовое исключающее «ИЛИ» (XOR) — бинарная операция, действие которой эквивалентно применению логического исключающего «ИЛИ» к каждой паре битов, которые стоят на одинаковых позициях в двоичных представлениях операндов.)
Задача была обобщена и на другие начальные условия: есть n школьниц, нужно создать группы размером k, так что наборы из t девушек никогда не встречались дважды в одной группе. Такая формулировка задачи называется схемой (n, k, t). Задача решается при некоторых условиях и не решается при некоторых других. За минувшие годы решение стало известно для многих сочетаний (n, k, t), которые были проверены либо алгебраически, либо перебором на компьютерах.
В результате, головоломка о школьницах помогла сформировать новое направление математики: комбинаторные схемы. Эти схемы стали методом, который применяется сейчас в кодах коррекции ошибок в информатике, криптографии, сельском хозяйстве, спорте, дизайне. Например, классический код Хэмминга для коррекции ошибок использует решение задачи про школьниц.