Парадокс укладки Z-тетрамино в квадраты
Владимир Ковальджи
«Квантик» №1, 2020
Вполне очевидно, что никакой клетчатый квадрат нельзя разрезать по линиям клеточек на фигурки Z-тетрамино весь без остатка. «Зигзаг» — фигурка кривая, неудобная, замостить ею квадрат целиком невозможно. Но сколько именно «лишних» клеток останется в самом лучшем случае? И как это зависит от размеров квадрата?
Скорее всего, большинству людей интуиция подскажет, что неизбежно останется «несколько» клеток. Что в очень большом квадрате мы почти по всей площади квадрата уложим наши зигзаги плотно, как паркет, и только где-то по углам мы столкнёмся с неприятными «краевыми эффектами», не позволяющими обойтись без лишних клеток. И что с увеличением размеров квадрата число этих лишних клеток вряд ли сильно вырастет. Углов-то у любого квадрата ровно четыре...
Итак, задача:
Попробуем для начала квадраты поменьше. В квадрате 3 × 3 умещается лишь одна фигурка. В квадрате 4 × 4 — три. В квадрате 5 × 5, как ни старайся, не получается уместить более четырёх. Что-то многовато лишних клеток остаётся — целых 9, то есть более чем на две фигурки ещё.
В квадрате 6 × 6 запросто умещаются 8 зигзагов, и остаются 4 лишние клетки — результат даже лучше, чем в квадрате 5 × 5! Впрочем, в квадрате 4 × 4 тоже осталось меньше, чем в 3 × 3 — четыре против пяти. Скорее всего, «чётные» квадраты явно удобнее для наших фигурок, и это легко объяснимо. Но главный вопрос — как зависит количество лишних клеток от размеров квадрата вообще (например, если рассматривать только «нечётные» квадраты)?
Возьмём квадрат 7 × 7. Можно попробовать самые разные варианты укладки, но увы — больше девяти фигурок никак не помещается (то есть 13 клеток остаются лишними). Поскольку перебрать все варианты укладки тут уже затруднительно, необходимо как-то строго доказать, что это действительно предел.
Тут приходит на помощь типичный для подобных задач метод раскраски. Если в нечётном квадрате (например, 7 × 7) покрасить некоторые клетки так, как показано на рисунке, то в любую фигурку Z-тетрамино обязательно попадёт зелёная клетка, и, следовательно, фигурок не может быть больше, чем таких клеток. Пример, когда фигурок ровно столько, сколько зелёных клеток, легко строится (нарисуйте его!).
Поскольку такая раскраска подходит для любого нечётного квадрата, можно решить задачу в общем виде. Если сторона квадрата 2n − 1, то зелёных клеток будет (n − 1)2. Из площади квадрата вычтем число зелёных клеток, помноженное на 4, и получим ответ:
(2n − 1)2 − 4(n − 1)2 = 4n − 3.
И вот тут становится ясно, что интуиция на сей раз нас очень сильно подвела. Оказывается, в квадрате 2019 × 2019 при разрезании на зигзаги неизбежно останется минимум 4037 лишних клеток! Совершенно неожиданный результат. Кажется невероятным, что такое огромное число клеток — четыре тысячи! — никак не удастся как-нибудь так сгруппировать, чтобы вырезать из них хотя бы ещё одну фигурку...
Что касается чётных квадратов со стороной 2n, то легко показать масштабируемую конструкцию, при которой остаётся 2n + 2 либо 2n лишних клеточек (в зависимости от делимости на 4). Что, конечно, экономнее, но всё равно количество лишних клеточек растёт прямо пропорционально стороне квадрата, становясь сколь угодно большим вопреки первоначальному интуитивному предположению.
Художник Евгений Паненко
