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

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

Зада́ча Кі́ркмана про школя́рок — це комбінаторна задача, яку Томас Пенінгтон Кіркман^[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].

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

Завдання можна узагальнити до ${\displaystyle n}$ учениць, де ${\displaystyle n}$ має бути числом, рівним добутку непарного числа на 3 (тобто, ${\displaystyle n\equiv 3{\pmod {6}}}$), що ходять трійками ${\displaystyle {\frac {1}{2}}(n-1)}$ днів за умови, знову ж, що жодна пара дівчат не ходить у тому самому ряді двічі[17]. Розв'язком цього узагальнення є система трійок Штейнера S(2, 3, 6t + 3) з паралельністю (тобто система, в якій кожні 6t + 3 елементів потрапляють рівно раз у кожен блок із 3-елементних множин), відома як система Кіркмана[1]. Це узагальнення задачі, яке спочатку обговорював Кіркман, а знаменитий частковий випадок ${\displaystyle n=15}$ він обговорював пізніше[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.

Література

• Cole F.W. Kirkman parades // Bulletin of the American Mathematical Society. — 1922. — Т. 28. — DOI:10.1090/S0002-9904-1922-03599-9.
• Giovanni Falcone, Marco Pavone. Kirkman's Tetrahedron and the Fifteen Schoolgirl Problem // The American Mathematical Monthly. — 2011. — Т. 118. — DOI:10.4169/amer.math.monthly.118.10.887.
• George M. Conwell. The 3-space PG(3,2) and its Groups // Annals of Mathematics. — 1910. — Т. 11. — DOI:10.2307/1967582.
• Cayley A. On the triadic arrangements of seven and fifteen things // Philosophical Magazine. — 1850. — Т. 37. — DOI:10.1080/14786445008646550.
• Hirschfeld J.W.P. Finite Projective Spaces of Three Dimensions. — Oxford University Press, 1985. — ISBN 0-19-853536-8.
• Ahrens W. Mathematische Unterhaltungen und Spiele. — Leipzig : Teubner, 1901.
• Darryn Bryant, Peter Danziger. On bipartite 2-factorizations of ${\displaystyle K_{n}-I}$ and the Oberwolfach problem // Journal of Graph Theory. — 2011. — Т. 68, вип. 1. — С. 22–37. — DOI:10.1002/jgt.20538.
• Charles J. Colbourn, Jeffrey H. Dinitz. Handbook of Combinatorial Designs. — 2nd. — Boca Raton : Chapman & Hall/ CRC, 2007. — ISBN 1-58488-506-8.
• Cummings L.D. An undervalued Kirkman paper // Bulletin of the American Mathematical Society. — 1918. — Т. 24. — С. 336–339. — DOI:10.1090/S0002-9904-1918-03086-3.
• Dudeney H.E. Amusements in Mathematics. — New York : Dover, 1917.
  • Dudeney H.E. Amusements in Mathematics. — Mineola, New York : Dover, 1958. — (Dover Recreational Math) — ISBN 978-0-486-20473-4.
• Ronald L. Graham, Martin Grötschel, László Lovász. Handbook of Combinatorics, Volume 2. — Cambridge, MA : The MIT Press, 1995. — ISBN 0-262-07171-1.
• Alan Hartman. Kirkman's trombone player problem // Ars Combinatoria. — 1980. — Т. 10. — С. 19–26.
• Jiaxi Lu. Collected Works of Lu Jiaxi on Combinatorial Designs. — Huhhot : Inner Mongolia People's Press, 1990.
• Thomas P. Kirkman. On a Problem in Combinations // The Cambridge and Dublin Mathematical Journal. — Macmillan, Barclay, and Macmillan, 1847. — Т. II. — С. 191–204.
• Thomas P. Kirkman. Note on an unanswered prize question // The Cambridge and Dublin Mathematical Journal. — Macmillan, Barclay and Macmillan, 1850. — Т. 5. — С. 255–262.
• Lucas É. Récréations Mathématiques. — Paris : Gauthier-Villars, 1883. — Т. 2. — С. 183–188.
• Ray-Chaudhuri D.K., Wilson R.M. Solution of Kirkman's schoolgirl problem, in Combinatorics, University of California, Los Angeles, 1968. — Proceedings Symposisa Pure Mathematics. — 1971. — Т. XIX. — С. 187–203. — ISBN 978-0-8218-1419-2. — DOI:10.1090/pspum/019/9959.
• Rouse Ball W.W. Mathematical Recreations and Essays. — London : Macmillan, 1892.
  • Rouse Ball W.W., Coxeter H.S.M. Mathematical Recreations and Essays. — 13th. — Dover, 1987. — С. 287−289. — ISBN 0-486-25357-0. Оригінальне видання:1974
• Тараканов В. Е. Комбинаторные задачи и (0,1) матрицы. — Москва : «Наука», 1985. — (Проблемы науки и технического прогресса)

Посилання

• Erica Klarreich. A design dilemma solved, minus designs. // Quanta Magazine. — 2015. — June.