Задача о школьницах. Ее можно решать не только перебором.
Fifteen young ladies in a school walk out three abreast for seven days in succession: it is required to arrange them daily so that no two shall walk twice abreast (в оригинальной формулировке)
("Пятнадцать школьниц каждый день в течение недели разбиваются на тройки и гуляют. Надо сделать так, чтобы каждая с каждой гуляла в одной тройке не более раза"). Найдено в википедии.
И дополнение.
Задача Сильвестра: 15 школьниц гуляют каждый день по трое. Надо составить такое расписание на 13-недельный семестр, чтобы в каждой неделе каждая пара школьниц погуляла в одной тройке ровно раз, и за весь семестр каждая тройка школьниц гуляла вместе ровно раз. Забавно, как красиво здесь сходится арифметика происходящего. Задача решена, но, кстати, не так уж давно.
Да, наверняка это можно сделать компьютерным перебором. Здесь же будет жесть и немного рандома.
ОтветитьУдалитьПусть GF(n) --- конечное поле с n элементами, GF(n)^k --- координатное векторное пространство размерности k над этим полем, PGF(n)^{k-1} --- соответствующее ему проективное пространство, а GL(n,k) --- группа обратимых матриц размера k над полем GF(n). Заметим, что PGF(2)^3 можно отождествить с GF(2)^4 \ {0}, т.к. у поля из двух элементов есть только один ненулевой элемент (он при проективизации ничего не отождествляет). Проективная прямая в PGF(2)^3 соответствует, по определению, двумерной плоскости L в GF(2)^4 без нуля, то есть тройке векторов v,w,v+w.
Отождествим наших школьниц с точками PGF(2)^3 (или, что то же самое с ненулевыми векторами пространства GF(2)^4, то есть со строчками из четырех нулей/единиц, не все из которых --- нули) --- их всего 15, так что пока все хорошо. Вначале две вспомогательные леммы:
Лемма 1. Проективное пространство PGF(2)^3 можно представить в виде объединения 5 попарно непересекающихся проективных прямых: PGF(2)^3 = L1 U L2 U L3 U L4 U L5.
Как нетрудно догадаться, это и будет разбиение школьниц на тройки (в один день).
Лемма 2. В группе GL(2,4) есть элемент A порядка 7.
Как эти леммы помогают решить задачу? Самым непосредственным образом. Пусть L1 U L2 U L3 U L4 U L5 --- разбиение школьниц в нулевой день. Пусть A(L1) U A(L2) U A(L3) U A(L4) U A(L5) --- разбиение школьниц в первый день (подействовали на исходное разбиение оператором A --- получили снова расслоение на проективные прямые, т.к. A --- линейный оператор). Пусть A^i(L1) U A^i(L2) U A^i(L3) U A^i(L4) U A^i(L5) --- разбиение школьниц в i день (действуем i-ой степенью оператора A на исходное разбиение) при 0<i<7.
Далее, как я думал, все очевидно, но нет. Оказалось, что подобранные данные (см. доказательства лемм ниже) дают действительно правильное расписание, но это верно не всегда, так что мне, в какой-то степени повезло. Тем не менее, привожу доказательства лемм, из которых можно извлечь явное расписание, будучи достаточно упоротым:
ОтветитьУдалитьЛ1. Заметим, что GF(2)^4 = GF(4)^2, как векторные пространства над GF(2). В пространстве GF(4)^2 рассмотрим все GF(4)-прямые, проходящие через 0. Все пространство GF(4)^2 \ {0} таким образом разбивается на непересекающиеся множества, каждое из которых --- GF(4)-прямая без нуля. Но каждая GF(4)-прямая --- это 2-мерная GF(2)-плоскость, поэтому получаем требуемое разбиение GF(2)^4 \ {0} на проективные прямые. Это разбиение можно явно описать: L1= {(1,0,0,0),(0,1,0,0),(1,1,0,0)}, L2={(0,0,1,0),(0,0,0,1),(0,0,1,1)}, L3={(1,0,1,0),(0,1,0,1),(1,1,1,1)}, L4={(1,0,0,1),(0,1,1,1),(1,1,1,0)}, L5={(1,0,1,1),(0,1,1,0),(1,1,0,1)}.
Л2. Группа GL(2,4) имеет порядок (16-1)х(16-2)х(16-4)х(16-8)=5х3^2x7x2^6. Это --- стандартное вычисление --- считаем, сколько вариантов для первого столбца матрицы (любой ненулевой вектор), сколько вариантов для второго столбца (любой вектор, не лежащий в векторном подпространстве, порожденном первым столбцом), и т.д. Искомый элемент существует по теореме Силова.
Теперь конструктивное построение. Построим матрицу 3х3 порядка 7, а потом припишем на диагональ 1. Как построить матрицу 3х3? Рассмотрим поле GF(8) (оно изоморфно GF(2)^3 как векторное пространство над GF(2)) и рассмотрим оператор A' умножения на примитивный элемент t в поле GF(8). Известно, что t^7=1, поэтому соответствующий оператор имеет порядок 7. Поле GF(8) можно задать, например, как GF(2)[t]/(t^3+t+1) --- многочлен t^3+t+1 не имеет корней, значит неприводим. В качестве базиса GF(2)-векторного пространства GF(8) рассмотрим 1,t,t^2. Тогда домножение на t действует на базисе так 1-->t, t-->t^2, t^2 --> t^3= t+1, а значит, матрица оператора имеет вид
|0 0 1|
|1 0 1| = A'
|0 1 0|
Желающие могут руками проверитть, что A'^7 = E. Итоговый оператор A задается блочной матрицей
|1 0 0 0|
|0 0 0 1|
|0 1 0 1|
|0 0 1 0|
Теперь, чтобы записать нужное расписание на всю неделю, надо применять степени оператора A из леммы 2 к разбиению из леммы 1. Построение окончено.
Почему получается то, что нужно --- это еще нужно доказать. Если вкратце: допустим, что две девицы все-таки попали в одну тройку дважды. Тогда и третья их компаньонша одна и та же в обоих случаях, т.к. она по условию равна их сумме как векторов GF(2)^4 оба раза. Тогда получилось бы, что некоторая степень оператора A переводит плоскость Li в плоскость Lj. Задача --- показать, что такого не бывает.
Матрица А транзитивно действует на множестве {(0,0,0,1),(0,0,1,0),(0,0,1,1),(0,1,0,0),(0,1,0,1),(0,1,1,0),(0,1,1,1)}, циклически переставляя его элементы. Аналогично: она действует циклическим сдвигом на множестве {(1,0,0,1),(1,0,1,0),(1,0,1,1),(1,1,0,0),(1,1,0,1),(1,1,1,0),(1,1,1,1)}. Таким образом, на этих множествах получается циклический порядок, инвариантный относительно действия A. Относительно этих порядков проективные прямые L1,L2,L3,L4,L5 как множества "выглядят по-разному" (не буду это пояснять, дочитавшие досюда могут сами понять), поэтому действие нетривиальных степеней A не может переводить одну проективную прямую в другую. С другой стороны, степени A не могут переводить 2-подпространство в себя. Действительно, в этом случае получилось бы инвариантное 2-подпространство; по теореме Машке GF(2)^4 разложилось бы в сумму двумерных представлений (с характеристикой поля все ок); но на пространстве GF(2)^2 не бывает операторов степени 7 из соображений арифметики, поэтому такого тоже не бывает.
вот до чего людей комбинаторные дизайны доводят
ОтветитьУдалитьА вот решение задачи Сильвестра
ОтветитьУдалитьhttps://www.sciencedirect.com/science/article/pii/0012365X74900041
Короче, запустили компьютер и нашли ответ.