# Розділ 7. Комбінаторика злиття

У цьому розділі ми детально дослідимо операцію злиття фігур – єдиний спосіб збільшити вагу фігури та наблизитися до перемоги. Ми побудуємо повну таблицю злиття для 4 типів, класифікуємо злиття за приростом ваги, проаналізуємо ефективність різних комбінацій та розглянемо ланцюжки злить, що ведуть до перемоги.

## 7.1. Повна таблиця злиття

Маски фігур будемо позначати десятковими числами (від 1 до 15), де кожне число відповідає 4-бітовій масці. Відповідність:

| Десяткове | Бінарне (4321) | Типи      | Короткий запис |
| --------- | -------------- | --------- | -------------- |
| 1         | 0001           | {0}       | \[0]           |
| 2         | 0010           | {1}       | \[1]           |
| 4         | 0100           | {2}       | \[2]           |
| 8         | 1000           | {3}       | \[3]           |
| 3         | 0011           | {0,1}     | \[01]          |
| 5         | 0101           | {0,2}     | \[02]          |
| 6         | 0110           | {1,2}     | \[12]          |
| 9         | 1001           | {0,3}     | \[03]          |
| 10        | 1010           | {1,3}     | \[13]          |
| 12        | 1100           | {2,3}     | \[23]          |
| 7         | 0111           | {0,1,2}   | \[012]         |
| 11        | 1011           | {0,1,3}   | \[013]         |
| 13        | 1101           | {0,2,3}   | \[023]         |
| 14        | 1110           | {1,2,3}   | \[123]         |
| 15        | 1111           | {0,1,2,3} | \[∗]           |

**Таблиця злиття a | b** (де a – рядок, b – стовпець). У клітинці – результат OR.

| a\b | 1  | 2  | 4  | 8  | 3  | 5  | 6  | 9  | 10 | 12 | 7  | 11 | 13 | 14 | 15 |
| --- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- |
| 1   | 1  | 3  | 5  | 9  | 3  | 5  | 7  | 9  | 11 | 13 | 7  | 11 | 13 | 15 | 15 |
| 2   | 3  | 2  | 6  | 10 | 3  | 7  | 6  | 11 | 10 | 14 | 7  | 11 | 15 | 14 | 15 |
| 4   | 5  | 6  | 4  | 12 | 7  | 5  | 6  | 13 | 14 | 12 | 7  | 15 | 13 | 14 | 15 |
| 8   | 9  | 10 | 12 | 8  | 11 | 13 | 14 | 9  | 10 | 12 | 15 | 11 | 13 | 14 | 15 |
| 3   | 3  | 3  | 7  | 11 | 3  | 7  | 7  | 11 | 11 | 15 | 7  | 11 | 15 | 15 | 15 |
| 5   | 5  | 7  | 5  | 13 | 7  | 5  | 7  | 13 | 15 | 13 | 7  | 15 | 13 | 15 | 15 |
| 6   | 7  | 6  | 6  | 14 | 7  | 7  | 6  | 15 | 14 | 14 | 7  | 15 | 15 | 14 | 15 |
| 9   | 9  | 11 | 13 | 9  | 11 | 13 | 15 | 9  | 11 | 13 | 15 | 11 | 13 | 15 | 15 |
| 10  | 11 | 10 | 14 | 10 | 11 | 15 | 14 | 11 | 10 | 14 | 15 | 11 | 15 | 14 | 15 |
| 12  | 13 | 14 | 12 | 12 | 15 | 13 | 14 | 13 | 14 | 12 | 15 | 15 | 13 | 14 | 15 |
| 7   | 7  | 7  | 7  | 15 | 7  | 7  | 7  | 15 | 15 | 15 | 7  | 15 | 15 | 15 | 15 |
| 11  | 11 | 11 | 15 | 11 | 11 | 15 | 15 | 11 | 11 | 15 | 15 | 11 | 15 | 15 | 15 |
| 13  | 13 | 15 | 13 | 13 | 15 | 13 | 15 | 13 | 15 | 13 | 15 | 15 | 13 | 15 | 15 |
| 14  | 15 | 14 | 14 | 14 | 15 | 15 | 14 | 15 | 14 | 14 | 15 | 15 | 15 | 14 | 15 |
| 15  | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 | 15 |

*Примітка*. Таблиця симетрична, тому наведено лише повний квадрат.

## 7.2. Класифікація злить за приростом ваги

**Означення 7.1 (Приріст)**. При злитті a та b приріст ваги відносно a дорівнює Δ = w(b) - w(a & b). Для злиття в цілому нова вага w(a|b) = w(a) + w(b) - w(a\&b).

Розіб’ємо всі пари (a,b) на класи за приростом (незалежно від порядку). Оскільки ваги масок бувають 1,2,3,4, розглянемо можливі прирости:

* **Приріст 0** (марне злиття): a ⊆ b. Тоді a|b = b, вага не збільшується. Наприклад, a=1, b=3 (w=2, a|b=3). Такі злиття не наближають до перемоги, але можуть бути корисними для переміщення фігури (оскільки зменшують кількість фігур на 1 і дозволяють фігурі b опинитися на місці a, якщо ми пересуваємо a на b). Стратегічно вони часто марні, але іноді необхідні для маневру.
* **Приріст 1**: новий тип додається. Найчастіше це злиття маски ваги k з маскою ваги 1, що містить тип, відсутній у першій. Наприклад, 1 (тип 0) з 2 (тип 1) → 3 (типи 0,1) – приріст 1. Також можливе злиття двох масок ваги 2, якщо вони мають один спільний тип (наприклад, 3 (01) і 5 (02) → 7 (012) – приріст 1, оскільки w=3).
* **Приріст 2**: злиття, що додає два нових типи. Це можливо, коли маски не перетинаються, і кожна має вагу 1 (1+1=2) або одна вага 1, інша вага 2 з неперетинними типами (наприклад, 1 (0) і 6 (12) → 7 (012) – додано два типи, приріст 2). Або дві маски ваги 2 з нульовим перетином (наприклад, 3 (01) і 12 (23) → 15 (0123) – приріст 2, оскільки w=4). Максимальний приріст – 3 (коли a ваги 1, b ваги 3 з неперетинними множинами, наприклад, 1 (0) і 14 (123) → 15, приріст 3). Але оскільки w(a|b) не може перевищувати 4, максимальний приріст для a ваги 1 дорівнює 3, для a ваги 2 – 2, для a ваги 3 – 1.

**Таблиця приростів** (для a ваги 1):

| b  | w(b) | a\&b | приріст | новий w |
| -- | ---- | ---- | ------- | ------- |
| 1  | 1    | 1    | 0       | 1       |
| 2  | 1    | 0    | 1       | 2       |
| 4  | 1    | 0    | 1       | 2       |
| 8  | 1    | 0    | 1       | 2       |
| 3  | 2    | 1    | 1       | 2       |
| 5  | 2    | 1    | 1       | 2       |
| 6  | 2    | 0    | 2       | 3       |
| 9  | 2    | 1    | 1       | 2       |
| 10 | 2    | 0    | 2       | 3       |
| 12 | 2    | 0    | 2       | 3       |
| 7  | 3    | 1    | 2       | 3       |
| 11 | 3    | 1    | 2       | 3       |
| 13 | 3    | 1    | 2       | 3       |
| 14 | 3    | 0    | 3       | 4       |
| 15 | 4    | 1    | 3       | 4       |

(Приклад для a=1, аналогічно для інших a за симетрією).

## 7.3. Ефективність злиття

**Означення 7.2 (Ефективне злиття)**. Злиття називається ефективним, якщо приріст ваги > 0. Найефективнішим є злиття, що дає максимальний приріст для даних масок, тобто коли a & b = ∅. Тоді w(a|b) = w(a) + w(b), і приріст = w(b).

Злиття, де a ⊆ b, дає приріст 0 – воно марне для наближення до перемоги, але може використовуватися для переміщення фігури b у позицію a (оскільки після злиття фігура b опиняється на місці a, якщо ми переміщували a).

**Лема 7.1 (Максимальний приріст)**. Для фігури ваги w максимальний можливий приріст при злитті дорівнює 4 - w, досягається, коли друга фігура містить усі типи, відсутні в першій (тобто її маска є доповненням до a в множині T).

## 7.4. Комбінаторна оптимізація: мінімальна кількість злить до перемоги

Починаючи з 16 фігур ваги 1, нам потрібно отримати одну фігуру ваги 4. Кожне злиття зменшує кількість фігур на 1. Мінімальна кількість злить для досягнення однієї фігури з 16 становить 15. Але це лише зменшення кількості фігур, а не збір усіх типів. Для отримання ваги 4 потрібно, щоб у фінальній фігурі були всі 4 типи. Оскільки початково кожен тип присутній 4 рази, ми можемо втрачати типи при злитті (спільні типи не подвоюються, але вони не зникають). Насправді, щоб зібрати всі 4 типи, нам потрібно виконати принаймні 3 злиття, які додають нові типи (наприклад, злити два типи → \[01], потім додати третій → \[012], потім додати четвертий → \[0123]). Але через позиційні обмеження може знадобитися більше злить.

**Лема 7.2 (Нижня межа кількості злить)**. Для створення фігури ваги 4 необхідно виконати не менше 3 злить, що додають нові типи. Загальна кількість злить у партії (включаючи марні) може бути будь-якою від 3 до 15.

*Доведення*. Почнемо з однієї фігури. Кожне злиття, що додає новий тип, збільшує вагу на 1. Щоб досягти ваги 4, потрібно 3 таких злиття. Марні злиття (без збільшення ваги) можна вставляти між ними, але вони не наближають до перемоги. ∎

**Оптимальний ланцюжок злить** (ігноруючи позицію) – це послідовність злить, яка за мінімальну кількість кроків (3) створює фігуру ваги 4. Наприклад: \[0] + \[1] → \[01]; \[01] + \[2] → \[012]; \[012] + \[3] → \[0123].

## 7.5. Марні злиття та їхнє стратегічне значення

Марні злиття (a ⊆ b) не збільшують вагу, але вони змінюють розташування фігур: після злиття фігура b опиняється на місці a (якщо ми переміщували a). Це дозволяє пересунути «сильну» фігуру без втрати її складу. Наприклад, якщо у нас є фігура \[012] на клітинці X, а порожня клітинка Y знаходиться на відстані ходу коня, ми не можемо просто перемістити \[012] на Y, оскільки Y порожня – це дозволено. Але якщо Y зайнята фігурою, яка є підмножиною \[012] (наприклад, \[0]), то злиття \[012] з \[0] дасть \[012] на місці Y, а X стане порожнім. Таким чином, ми фактично перемістили фігуру \[012] на Y, використавши марне злиття. Це важливий маневр.

**Висновок**: марні злиття можуть бути корисними для зміни позиції сильної фігури, коли пряме переміщення на порожню клітинку неможливе через відсутність порожньої клітинки на потрібній відстані.

## 7.6. Ланцюжки злить у реальній грі

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

**Приклад**: початкове розташування дозволяє злити деякі пари безпосередньо. З клітинки (0,0) типу 0 можна злитися з клітинками типів 1 і 3 (див. розділ 4). Тому перше злиття може бути \[0] з \[1] або \[0] з \[3]. Після цього нова фігура опиняється на місці цілі. Далі потрібно підвести до неї третій тип тощо. У розділі 11 (дебют) ми розглянемо типові дебютні ланцюжки.

## 7.7. Висновки

У цьому розділі ми:

* навели повну таблицю злиття для 4 типів;
* класифікували злиття за приростом ваги та ефективністю;
* визначили марні злиття та їхнє стратегічне значення;
* встановили мінімальну кількість злить для перемоги (3) та верхню межу (15);
* обґрунтували, що реальні ланцюжки злить залежать від геометрії.

Цей аналіз є основою для розуміння тактичних можливостей (розділ 9) та стратегічних фаз (розділи 11–13).

***


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nautilus-3.gitbook.io/subit64/aether-tour/docs/compedium/07_merging_combinatorics.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.