Як розібрати двадцятичотиривимірний симплекс на окремі трикутники

А почалося все з того, що я вигадала таку задачку. З корабля передають умовний сигнал. Для цього підняли на леєрі комбінацію з трьох сигнальних прапорців. Припустимо, всього комплект містить стільки-то прапорців, а умови такі, що спостерігач може помітити тільки два прапорці з трьох, та й то не розібрати, який з них вище, а який нижче. Скільки різних сигналів може бути включено в кодову таблицю?

Потім виявилось, що є ще складніша знаменита задачка Кіркмана з середини XIX століття про 15 юних леді, які щодня виходять на шпацир рядочками по троє. (Це чудесна задачка, а про узагальнений випадок пишеться: «нерозв'язана математична проблема»). То складніше. У мене просто задача про трійки Штейнера.

Такого по телевізору не покажуть. Бачили коли-небудь двадцятичотиривимірний симплекс? Так отож!

(n-вимірний симплекс, коли хто не зна,— це фігура, утворена отак просто: з геометричного центра (n-1)-вимірного симплексу будується перпендикуляр в наступний вимір, на цьому перпендикулярі береться нова вершина, і з'єднується ребрами з усіма вершинами (n-1)-симплексу. Трикутник (між іншим — двовимірний симплекс) — це замкнена ламана з трьох ребер. А окремий трикутник — той, що торкається до інших лише вершинами).

Ось, навчилась. Сотня трійок Штейнера для множини з двадцяти п'яти елементів. Кожне число від 00 до 24 входить в дванадцять трійок із ста, причому з двома щоразу іншими числами. Це такий розклад зустрічей для 25 друзів, який дає можливість зустрітися кожному з кожним по одному разу при тому, що більше трьох не збиратися!

Я написала. Пальчиками. Перед тим спробувала застосувати комп'ютерний брутфорс: перебравши 11 з гаком мільярдів трійок, вдалося побудувати лише систему максимум з 95 трійок, 100 не влазить, деякі пари не поєднуються, коли комп'ютер дорахував до 20 чи 30 мільярдів — вимкнула його. Це надзвичайні відчуття, коли програмочка 40 кілобайт завбільшки крутиться цілу годину переставляючи 25 чисел і кінця-краю тому не видно!

Треба було знайти товсту спеціальну книжку і прочитати її. Власне, усієї інструкції там пів сторіночки, але ж спробуй тої півсторіночки знайти!!

1

(Проста інструкція для особливих випадків)

Якщо a _i a _j a _k і b _l b _m b _n — трійки Штейнера для множин відповідно з v ₁ і v₂ елементів, то c _il c _jm c _kn (дві букви в індексі означають конкатенацію, а не множення) також буде трійкою Штейнера для множини з v ₁·v ₂ (отут множення) елементів, якщо

1. i = j = k і b _l b _m b _n — згадана вище трійка;
2. l = m = n і a _i a _j a _k — згадана вище трійка;
3. a _i a _j a _k і одночасно b _l b _m b _n є такими трійками.

Так можна, наприклад, маючи системи для 3 і 7 елементів (які легко знайти), можна побудувати систему з 21 елемента.

Спробуємо. Для 3 існує одна-єдина трійка — це очевидно. Позначимо її ABC. Для 7 — сім (див. малюнок): 012, 034, 056, 145, 136, 235, 246.

Для 21:

1. (Однакові букви) A0A1A2, A0A3A4, A0A5A6, A1A4A5, A1A3A6, A2A3A5, A2A4A6, B0B1B2, B0B3B4, B0B5B6, B1B4B5, B1B3B6, B2B3B5, B2B4B6, C0C1C2, C0C3C4, C0C5C6, C1C4C5, C1C3C6, C2C3C5, C2C4C6,
2. (Однакові цифри) A0B0C0, A1B1C1, A2B2C2, A3B3C3, A4B4C4, A5B5C5, A6B6C6,
3. (Комбінування трійки літер з кожною трійкою цифр дає по шість комбінацій — усі можливі перестановки) A0B1C2, A0B3C4, A0B5C6, A1B4C5, A1B3C6, A2B3C5, A2B4C6, A0C1B2, A0C3B4, A0C5B6, A1C4B5, A1C3B6, A2C3B5, A2C4B6, B0A1C2, B0A3C4, B0A5C6, B1A4C5, B1A3C6, B2A3C5, B2A4C6, B0C1A2, B0C3A4, B0C5A6, B1C4A5, B1C3A6, B2C3A5, B2C4A6, C0A1B2, C0A3B4, C0A5B6, C1A4B5, C1A3B6, C2A3B5, C2A4B6, C0B1A2, C0B3A4, C0B5A6, C1B4A5, C1B3A6, C2B3A5, C2B4A6,

Усього 70 комбінацій.

2

(Складна інструкція, що несподівано охоплює усі випадки)

Будь-яку кількість елементів можна записати у формі таблиці, в якій нульовий рядок містить v ₁ елементів (або один елемент), а кожен з наступних v ₂ рядків по v ₃ - v ₁ елементів. (За умови, що системи Штейнера з v ₃ елементів, яка містить підсистеми з v ₁ елемента, та з v ₂ елементів існують). Тоді до системи будуть включені усі трійки:

1. системи, утвореної нульовим рядком — з v ₁ елементів (крім випадку, коли в цьому рядку лише один елемент);
2. системи, утворені нульовим рядком разом з кожним іншим рядком — з v ₃ елементів кожна, з них вилучаються повтори трійок, які вже обрані за першим правилом;
3. усі трійки, взяті з таблиці так, щоб номери обраних рядків були трійкою в системі з v ₂ елементів, а сума номерів стовпчиків ділилася на v ₃ - v ₁ без остачі

Знаючи цю таємницю послідовності виписування цифр, я й змогла:

00 01 02 - 00 03 04 - 00 05 06 - 00 07 08 - 00 09 10 -
00 11 12 - 00 13 14 - 00 15 16 - 00 17 18 - 00 19 22 -
00 20 23 - 00 21 24 - 01 03 05 - 01 04 08 - 01 06 07 -
01 09 24 - 01 10 23 - 01 11 22 - 01 12 19 - 01 13 18 -
01 14 21 - 01 15 17 - 01 16 20 - 02 03 07 - 02 04 06 -
02 05 08 - 02 09 23 - 02 10 22 - 02 11 19 - 02 12 18 -
02 13 17 - 02 14 20 - 02 15 21 - 02 16 24 - 03 06 08 -
03 09 22 - 03 10 19 - 03 11 18 - 03 12 17 - 03 13 21 -
03 14 24 - 03 15 20 - 03 16 23 - 04 05 07 - 04 09 19 -
04 10 18 - 04 11 17 - 04 12 21 - 04 13 20 - 04 14 23 -
04 15 24 - 04 16 22 - 05 09 18 - 05 10 17 - 05 11 21 -
05 12 20 - 05 13 24 - 05 14 22 - 05 15 23 - 05 16 19 -
06 09 21 - 06 10 20 - 06 11 24 - 06 12 23 - 06 13 22 -
06 14 18 - 06 15 19 - 06 16 17 - 07 09 17 - 07 10 21 -
07 11 20 - 07 12 24 - 07 13 23 - 07 14 19 - 07 15 22 -
07 16 18 - 08 09 20 - 08 10 24 - 08 11 23 - 08 12 22 -
08 13 19 - 08 14 17 - 08 15 18 - 08 16 21 - 09 11 13 -
09 12 16 - 09 14 15 - 10 11 15 - 10 12 14 - 10 13 16 -
11 14 16 - 12 13 15 - 17 19 23 - 17 20 24 - 17 21 22 -
18 19 24 - 18 20 22 - 18 21 23 - 19 20 21 - 22 23 24 .

(не намагайтесь знайти закономірність, я декілька цифр поміняла місцями просто для краси).

Чи спробуємо? 25 = 1 + 3 · 8. Тут v ₁ = 1, v ₂ = 3, v ₃ = 9. (Нагадую, що ці числа мусять бути виду 6n + 1 чи 6n + 3.)

00
01	02	03	04	05	06	07	08
09	10	11	12	13	14	15	16
17	18	19	20	21	22	23	24

1. У нульовому рядку лише один елемент.
2. Cистеми, утворені дев’ятьма елементами: 00 01 02 03 04 05 06 07 08, 00 09 10 11 12 13 14 15 16 і 00 17 18 19 20 21 22 23 24, розбиваються на трійки, тут можна скористатися першим способом, 9 = 3 · 3. Кожна дев’ятка дає 12 трійок, отже маємо перші 36 трійок.
3. Трійки беруться по одному елементу з кожного рядка: 01 09 17, 01 10 24, 01 11 23 і т. д. Кожен стовпчик першого рядка комбінується з кожним стовпчиком другого рядка, а номер третього рядка обирається так, щоб сума номерів ділилась на 8. Це ще 64 трійки.

Усього 100.