Ксоня та двокольорова фігура

Автор та розробник: Святослав Бідзіля

Спочатку знайдемо, коли відповіді немає.

Порахуємо найбільшу площу фігури, в якій $$$x$$$ чорних клітинок. Будемо фарбувати нашу фігуру. На першому кроці зафарбуємо будь-яку чорну клітинку в жовтий колір, а всіх її сусідів(білі клітинки) в синій. На кожному наступному колі будемо фарбувати будь-яку чорну клітинку, яка сусідня з синьою в жовтий, і всіх її сусідів в синій. Так, рівно за $$$x$$$ кроків ми розфарбуємо всю фігуру (бо чорних клітинок рівно $$$x$$$). На першому колі ми фарбуємо максимум 5 клітинок, на кожному наступному - максимум по 4. Тому, максимальна площа такої фігури - $$$4x + 1$$$.

Якщо $$$4 \cdot min(w, b) + 1 < w + b$$$ відповіді немає. Інакше, покажемо одну з конструкцій, як можна досягти будь-якої відповіді. Без обмеження загальності, нехай $$$w < b$$$. Розташуємо білі клітинки в ряд, через одну. Між ними поставимо чорні клітинки. (Це можливо, бо $$$w < b$$$). Далі, всі чорні клітинки, що залишилися можна додати до будь-якої вільної чорної клітинки зверху, знизу, або збоку. Очевидно, що така фігура досягає потрібної площі і подібне рішення нескладно реалізується.

Тут зображений варіант конструкції. Жовтим відмічені місця, куди можна додавати чорні клітинки.