Задача Кіркмана про школярок

комбінаторна задача

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

Оригінальна публікація задачі

П'ятнадцять дівчаток у школі ходять по три в ряд сім днів (щодня), потрібно розподілити їх на кожну прогулянку так, щоб жодні дві дівчинки не йшли в тому самому ряду (Graham, Grötschel, Lovász, 1995).

Розв'язок

ред.

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

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

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

Існує сім неізоморфних розв'язків задачі про школярок[3]. Два з них можна візуалізувати як відношення між тетраедром та його вершинами, ребрами та гранями[4]. Нижче наведено підхід, що використовує тривимірну проєктивну геометрію над GF(2)[en].

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

Історія

ред.

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

Кіркман часто пояснював, що його велика стаття (Kirkman, 1847) була повністю викликана величезним інтересом до задачі[12].

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

ред.

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

Поле Галуа GF(2)[en] з двома елементами використовувалося з чотирма однорідними координатами для формування PG(3,2) з 15 точками, 3 точками на прямій, 7 точками та 7 прямими на площині. Площину можна вважати повним чотирикутником разом із прямою, проведеною через його діагональні точки. Кожна точка лежить на 7 прямих і є загалом 35 прямих.

Прямі простору PG(3,2) визначаються їх плюккеровими координатами в PG(5,2) з 63 точками, 35 з яких представляють прямі PG(3,2). Ці 35 точок утворюють поверхню S, відому як квадрика Кляйна[en]. Для кожної з 28 точок, що не лежать на S, існує 6 прямих через цю точку, які не перетинаються з S[14].

Як число днів у тижні, сімка відіграє важливу роль у розв'язку:

  Якщо дві точки A і B на прямій ABC вибрано, кожна з п'яти інших прямих через A перетинається тільки з однією з п'яти прямих, що проходять через B. П'ять точок, отриманих перетином цих пар, разом із двома точками A і B ми називаємо «сімкою»(Conwell, 1910, 68).  

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

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

Узагальнення

ред.

Завдання можна узагальнити до   учениць, де   має бути числом, рівним добутку непарного числа на 3 (тобто,  ), що ходять трійками   днів за умови, знову ж, що жодна пара дівчат не ходить у тому самому ряді двічі[17]. Розв'язком цього узагальнення є система трійок Штейнера S(2, 3, 6t + 3) з паралельністю (тобто система, в якій кожні 6t + 3 елементів потрапляють рівно раз у кожен блок із 3-елементних множин), відома як система Кіркмана[1]. Це узагальнення задачі, яке спочатку обговорював Кіркман, а знаменитий частковий випадок   він обговорював пізніше[7]. Повний розв'язок загального випадку опублікували Д. К. Рей-Чадгурі[en] і Р. М. Вільсон[en] 1968 року[18], хоча китайський математик Лю Джаксі[en] розв'язав задачу 1965 року[19], але на той час розв'язок не був опублікованим[20].

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

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

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

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

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

ред.

Примітки

ред.
  1. а б Rouse Ball, Coxeter, 1987, с. 287−289.
  2. Weisstein, Eric W. Задача Кіркмана про школярок(англ.) на сайті Wolfram MathWorld.
  3. Cole, 1922, с. 435–437.
  4. Falcone, Pavone, 2011, с. 887–900.
  5. Cayley, 1850, с. 50–53.
  6. Kirkman, 1850.
  7. а б Kirkman, 1847.
  8. Lucas, 1883, с. 183–188.
  9. Rouse Ball, 1892.
  10. Ahrens, 1901.
  11. Dudeney, 1917.
  12. Cummings, 1918.
  13. Conwell, 1910, с. 60–76.
  14. Conwell, 1910, с. 67.
  15. Conwell, 1910, с. 69.
  16. Conwell, 1910, с. 74.
  17. Тараканов, 1985, с. 109.
  18. Ray-Chaudhuri, Wilson, 1971.
  19. Lu, 1990.
  20. Colbourn, Dinitz, 2007, с. 13.
  21. Hartman, 1980.
  22. Bryant, Danziger, 2011.

Література

ред.

Посилання

ред.