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

Розв'язок
Якщо дівчат пронумерувати від 0 до 14, такий розподіл буде одним із розв'язків:


Неділя

 Понеділок

 Вівторок

 Середа

 Четвер

 П'ятниця

 Субота


 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

Розв'язок цієї задачі є прикладом системи трійок Кіркмана; це означає, що вона є системою трійок Штейнера, що має паралельність, тобто має розбиття блоків системи трійок на паралельні класи, які є розбиттям точок на блоки, що не перетинаються.

Існує сім неізоморфних розв'язків задачі про школярок. Два з них можна візуалізувати як відношення між тетраедром та його вершинами, ребрами та гранями. Нижче наведено підхід, що використовує тривимірну проєктивну геометрію над .

Розв'язок 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).

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

Кіркман часто пояснював, що його велика стаття  була повністю викликана величезним інтересом до задачі.

Геометрія Галуа
1910 року Джордж Конвелл розглянув задачу за допомогою геометрії Галуа.

Поле Галуа  з двома елементами використовувалося з чотирма однорідними координатами для формування 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.

Як число днів у тижні, сімка відіграє важливу роль у розв'язку:Сімка визначається двома її точками. Кожна з 28 точок поза S лежить на двох сімках. Є 8 сімок. Проєктивна лінійна група PGL(3,2) ізоморфна знакозмінній групі на 8 сімках.

Завдання про школярок полягає в пошуку, в 5-мірному просторі семи прямих, які не перетинаються, таких, що будь-які дві прямі завжди мають спільну сімку.

Узагальнення
Завдання можна узагальнити до  учениць, де  має бути числом, рівним добутку непарного числа на 3 (тобто, ), що ходять трійками  днів за умови, знову ж, що жодна пара дівчат не ходить у тому самому ряді двічі. Розв'язком цього узагальнення є система трійок Штейнера S(2, 3, 6t + 3) з паралельністю (тобто система, в якій кожні 6t + 3 елементів потрапляють рівно раз у кожен блок із 3-елементних множин), відома як система Кіркмана. Це узагальнення задачі, яке спочатку обговорював Кіркман, а знаменитий частковий випадок  він обговорював пізніше. Повний розв'язок загального випадку опублікували  і  1968 року, хоча китайський математик  розв'язав задачу 1965 року, але на той час розв'язок не був опублікованим.

Розглядалися кілька варіантів основної задачі. Алан Гартман розв'язував задачу цього типу з вимогою, що жодні три не ходять у рядах по чотири більше одного разу, за допомогою системи четвірок Штейнера.

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

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

Задача Обервольфаха розкладання повного графа на копії, що що не перетинаються, даного 2-регулярного графа, також узагальнює задачу Кіркмана про школярок. Задача Кіркмана є окремим випадком задачі Обервольфаха, в якому 2-регулярний граф складається з п'яти трикутників, що не перетинаються.

Інші застосування

* Кооперативне навчання — стратегія для підвищення співпраці учнів у класі
* Організація спортивних змагань

Примітки


Література

* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
** 
* 
* 
* 
* 
* 
* 
* 
* 
**  Оригінальне видання:1974
* 


Посилання
* 



