Задача Кіркмана про школярок
Зада́ча Кі́ркмана про школя́рок — це комбінаторна задача, яку Томас Пенінгтон Кіркман[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].
Інші застосування
ред.- Кооперативне навчання — стратегія для підвищення співпраці учнів у класі
- Організація спортивних змагань
Примітки
ред.- ↑ а б Rouse Ball, Coxeter, 1987, с. 287−289.
- ↑ Weisstein, Eric W. Задача Кіркмана про школярок(англ.) на сайті Wolfram MathWorld.
- ↑ Cole, 1922, с. 435–437.
- ↑ Falcone, Pavone, 2011, с. 887–900.
- ↑ Cayley, 1850, с. 50–53.
- ↑ Kirkman, 1850.
- ↑ а б Kirkman, 1847.
- ↑ Lucas, 1883, с. 183–188.
- ↑ Rouse Ball, 1892.
- ↑ Ahrens, 1901.
- ↑ Dudeney, 1917.
- ↑ Cummings, 1918.
- ↑ Conwell, 1910, с. 60–76.
- ↑ Conwell, 1910, с. 67.
- ↑ Conwell, 1910, с. 69.
- ↑ Conwell, 1910, с. 74.
- ↑ Тараканов, 1985, с. 109.
- ↑ Ray-Chaudhuri, Wilson, 1971.
- ↑ Lu, 1990.
- ↑ Colbourn, Dinitz, 2007, с. 13.
- ↑ Hartman, 1980.
- ↑ Bryant, Danziger, 2011.
Література
ред.- Cole F.W. Kirkman parades // Bulletin of the American Mathematical Society. — 1922. — Т. 28. — DOI: .
- Giovanni Falcone, Marco Pavone. Kirkman's Tetrahedron and the Fifteen Schoolgirl Problem // The American Mathematical Monthly. — 2011. — Т. 118. — DOI: .
- George M. Conwell. The 3-space PG(3,2) and its Groups // Annals of Mathematics. — 1910. — Т. 11. — DOI: .
- Cayley A. On the triadic arrangements of seven and fifteen things // Philosophical Magazine. — 1850. — Т. 37. — DOI: .
- 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 and the Oberwolfach problem // Journal of Graph Theory. — 2011. — Т. 68, вип. 1. — С. 22–37. — DOI: .
- 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: .
- 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:
- 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.