Парадокс укладання Z -тетраміно в квадрати

Цілком очевидно, що ніякий картатий квадрат не можна розрізати по лініях клітинок на фігурки Z-тетраміно весь без залишку. «Зигзаг» — фігурка крива, незручна, замостити нею квадрат цілком неможливо. Але скільки саме «зайвих» клітин залишиться в найкращому випадку? І як це залежить від розмірів квадрата?

Швидше за все, більшості людей інтуїція підкаже, що неминуче залишиться «кілька» клітин. Що в дуже великому квадраті ми майже по всій площі квадрата укладемо наші зигзаги щільно, як паркет, і тільки десь по кутах ми зіткнемося з неприємними «крайовими ефектами», що не дозволяють обійтися без зайвих клітин. І що зі збільшенням розмірів квадрата кількість цих зайвих клітин навряд чи сильно зросте. Кутів у будь-якого квадрата рівно чотири…

Отже, завдання:

У нас є картатий квадрат 2019 року 2019. Яке мінімальне число зайвих клітин може залишитися після вирізання з нього максимально можливого числа Z-тетраміно?

Спробуємо для початку квадрати поменше. У квадраті 3 ст.13 вміщується лише одна фігурка. У квадраті 4 ст.14 — три. У квадраті 5 ст.15, як не старайся, не виходить вмістити більше чотирьох. Щось забагато зайвих клітин залишається — цілих 9, тобто більш ніж на дві фігурки ще.

У квадраті 6 ст.16 запросто вміщуються 8 зигзагів, і залишаються 4 зайві клітини — результат навіть кращий, ніж у квадраті 5 ст.15! Втім, в квадраті 4 ст.14 теж залишилося менше, ніж в 3 ст.13 — чотири проти п’яти. Швидше за все, «чіткі» квадрати явно зручніші для наших фігурок, і це легко зрозуміло. Але головне питання — як залежить кількість зайвих клітин від розмірів квадрата взагалі (наприклад, якщо розглядати тільки «непарні» квадрати)?

Візьмемо квадрат 7 ст.17. Можна спробувати різні варіанти укладання, але на жаль — більше дев’яти фігурок ніяк не поміщається (тобто 13 клітин залишаються зайвими). Оскільки перебрати всі варіанти укладання тут вже важко, необхідно якось суворо довести, що це дійсно межа.

Тут приходить на допомогу типовий для подібних завдань метод розмальовки. Якщо в непарному квадраті (наприклад, 7 ст.17) пофарбувати деякі клітини так, як показано на малюнку, то в будь-яку фігурку Z-тетраміно обов’язково потрапить зелена клітина, і, отже, фігурок не може бути більше, ніж таких клітин. Приклад, коли фігурок рівно стільки, скільки зелених клітин, легко будується (намалюйте його!).

Оскільки така розмальовка підходить для будь-якого непарного квадрата, можна вирішити завдання в загальному вигляді. Якщо сторона квадрата 2n ‑ 1, зелених клітин буде (n ‑ 1) 2. З площі квадрата віднімемо число зелених клітин, помножене на 4, і отримаємо відповідь:

(2n − 1)² − 4(n − 1)² = 4n − 3.

І ось тут стає ясно, що інтуїція цього разу нас дуже сильно підвела. Виявляється, в квадраті 2019 2019 при розрізанні на зигзаги неминуче залишиться мінімум 4037 зайвих клітин! Абсолютно несподіваний результат. Здається неймовірним, що таке величезне число клітин — чотири тисячі! — ніяк не вдасться якось так згрупувати, щоб вирізати з них хоча б ще одну фігурку…

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

Художник Євген Паненко