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

Матеріал з testwiki
Перейти до навігації Перейти до пошуку
Оригінальна публікація задачі

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

П'ятнадцять дівчаток у школі ходять по три в ряд сім днів (щодня), потрібно розподілити їх на кожну прогулянку так, щоб жодні дві дівчинки не йшли в тому самому ряду Шаблон:Harvard citation.

Розв'язок

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

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

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

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

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

Історія

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примітки

Шаблон:Reflist

Література

Шаблон:Refbegin

Шаблон:Refend

Посилання

Шаблон:Бібліоінформація

Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Задача_Кіркмана_про_школярок&oldid=9872