Обложить со всех сторон!

б) Копии фигуры F можно переворачивать.

в) Обратите внимание, что у фигуры F выступов меньше, чем пазов.

в) Допустим, требуемое замощение возможно. Тогда, в частности, копиями фигуры F можно покрыть квадрат любого размера. Считая, что фигура F состоит из четырех единичных квадратиков, покажите, что ее копиями нельзя покрыть квадрат размера 100×100.

а) Пример подходящего многоугольника F₁ показан на рис. 1 (это контур светло-оранжевой фигуры).

Рис. 1.

б) На рис. 2 показано, как можно обложить многоугольник F₁ с рис. 1 вторым слоем копий фигуры F.

Рис. 2.

в) Будем называть копии фигуры F плитками. Предположим, нам удалось замостить плитками всю плоскость без пробелов и наложений. Рассмотрим квадрат S размера 2n×2n. Как часть плоскости этот квадрат целиком покрыт копиями фигуры F, причём без ограничения общности можно считать, что левый нижний угол квадрата совпадает с левым нижним углом одной из плиток.

Поскольку единственный способ заполнить пространство внутри паза любой плитки заключается в приложении туда выступа, число пазов и выступов, находящихся внутри квадрата S, совпадает. Однако сейчас мы оценим количество пазов и количество выступов внутри этого квадрата исходя из других соображений, и это приведет нас к противоречию.

Итак, выступы, находящиеся внутри S, можно условно разделить на две группы: это выступы, торчащие из клеток, лежащих внутри S, и выступы, торчащие из клеток, граничащих с S. Число выступов первого типа не превышает площади квадрата S, то есть 4n². А так как периметр квадрата S равен 8n, то число выступов второго типа не больше 8n. Отсюда мы должны сделать вывод, что общее число выступов, лежащих внутри S, не превышает 4n² + 8n.

С другой стороны, рассмотрим квадрат S' размера (2n − 8)×(2n − 8), расположенный внутри квадрата S так, как это показано на рис. 3. Каждая плитка, пересекающаяся с S', целиком лежит внутри S, а всего таких плиток как минимум \( \frac{(2n-8)^2}{4}=(n-4)^2 \). Поскольку на каждую плитку приходится 5 пазов, это означает, что внутри квадрата S расположено хотя бы 5(n − 4)² пазов.

Рис. 3.

Однако 5(n − 4)² > 4n² + 8n при достаточно больших значениях числа n, что говорит нам о том, что количество пазов внутри квадрата S больше, чем количество выступов. В самом деле, это неравенство можно переписать в виде n² > 48n − 80, и видно, что оно выполнено уже при n = 50, так как

Таким образом, мы не можем покрыть квадрат 100×100 копиями фигуры F. Значит, и всю плоскость замостить этими фигурами не удастся.

Будем говорить, что многоугольник F является протоплиткой, если копиями этого многоугольника можно покрыть всю плоскость без пробелов и наложений. Зададимся вопросом: является ли данный нам произвольный многоугольник F протоплиткой? На первый взгляд, самый естественный способ попытаться ответить на этот вопрос заключается в выполнении следующего алгоритма. Поместим первую плитку в центр. Затем попробуем обложить ее другими плитками со всех сторон так, чтобы не возникало зазоров и наложений. Если это удалось — окружим начальную плитку вторым слоем, затем третьим и так далее. Если в какой-то момент сформировать очередной слой не удается — переложим плитки предыдущего слоя иначе и продолжим построение в том же ключе. Ясно, что если F является протоплиткой, то предложенный алгоритм никогда не закончит свою работу. С другой стороны, если плитками, равными F, замостить плоскость нельзя, и если в какой-то момент мы переберем все возможные способы выложить эти плитки в один слой, в два слоя, в три слоя и так далее, то среди этих способов обнаружится конфигурация, обладающая максимальным числом слоев. Такое число называется числом Хееша плитки F и обозначается H(F).

Рис. 4.

Для произвольно выбранной плитки F с точки зрения ее числа Хееша наиболее типичны две ситуации: H(F) = 0 и H(F) не определено. Последнее означает, что F допускает замощение плоскости, то есть является протоплиткой, и в этом случае мы будем неформально считать, что число Хееша равно бесконечности, записывая это коротким равенством H(F) = ∞. Две указанные выше ситуации легко проиллюстрировать на примере правильных многоугольников. Так, треугольниками, квадратами и шестиугольниками плоскость можно замостить без труда (рис. 5), что означает, что для этих фигур число Хееша равно бесконечности. А вот, скажем, копиями пятиугольника не удается выложить вокруг исходной плитки даже один слой (рис. 4), то есть число Хееша правильного пятиугольника равно нулю. Другие примеры многоугольников указанных выше двух типов можно найти в задаче Замощения.

Рис. 5.

Естественно полюбопытствовать, существуют ли многоугольники, для которых число Хееша равно 1, 2, 3, ... В математике этот вопрос известен как задача Хееша, и ответить на него оказывается совсем непросто. До того, как Генрих Хееш (Heinrich Heesch) сформулировал его в 1968 году, был известен пример лишь одной плитки, для которой число Хееша отличалось бы от нуля и бесконечности (рис. 6). Плитка эта не является даже многоугольником, и впервые она появилась в книге Вальтера Литцмана «Забавные и странные числа и формы», опубликованной в 1922 году.

Рис. 6.

Хееш привел пример другой плитки F, для которой H(F) = 1: это многоугольник, составленный из квадрата, правильного треугольника и еще одной половинки такого же треугольника (рис. 7).

Рис. 7.

Пример Хееша хорош еще и тем, что из таких многоугольников можно сложить бесконечную полосу, которая отделяется от непокрытых областей слоем плиток того же вида (рис. 8).

Рис. 8.

Первый пример плиток F, для которых H(F) = 2, привела в 1991 году Анн Фонтен. Она показала, что подобным свойством обладает бесконечное множество различных фигурок полимино U-образной формы, удовлетворяющих определенным условиям. Именно, для сторон такого полимино должны выполняться соотношения c = h, b = f = c + g = a + e, 2c > b и a > g (рис. 9).

Рис. 9.

В том же году Роберт Амманн предъявил правильный шестиугольник с выступами и пазами (рис. 10), для которого число Хееша равно 3 (на рисунке 10 вокруг центральной плитки выложено четыре слоя, но в самом внешнем из них есть дырки, поэтому число Хееша действительно равно 3). Идея Амманна заключалась в том, чтобы рассмотреть комбинаторно несбалансированную плитку, то есть такую плитку, у которой число выступов не совпадает с числом пазов. Это свойство влечет за собой невозможность замостить всю плоскость такими плитками без пробелов и наложений. А отсюда, в свою очередь, следует, что число Хееша для указанного Амманном многоугольника должно быть конечным.

Рис. 10.

Опираясь на идеи комбинаторной несбалансированности, Кейзи Манну удалось получить серию новых плиток с конечным числом Хееша, отличным от нуля. Манн показал, что если сложить вместе n квадратиков, а потом полученный прямоугольник n×1 снабдить выступами и пазами так, как это было сделано в условии настоящей задачи, то число Хееша полученной плитки F_n будет равно двум для n = 2 и n = 3, а для n ≥ 4 будет справедливо соотношение H(F_n) = 3. Если же вместо квадратиков складывать шестиугольники, то результат будет еще более впечатляющим. Так, для плитки, изображенной на рис. 11, число Хееша равно 5. На сегодняшний день это плитка с самым большим известным человечеству числом Хееша.

Рис. 11.

При подготовке статьи были использованы следующие материалы:
1) A. Fontaine. An Infinite Number of Plane Figures with Heesch Number Two // Journal of Combinatorics Theory, Series A. 1991.
2) Grunbaum Branco, G. C. Shephard. Tilings and Patterns. New-York: W. H. Freeman and Company. 1986.
3) H. Heesch. Reguläres Parkettierungsproblem. Köln und Opladen: Westdeutscher Verlag. 1968.
4) W. Lietzmann. Lustiges und Merkwürdiges von Zahlen und Formen. Breslau: Ferd. Hirt. 1922.
5) C. Mann. Heesch's Tiling Problem. American Mathematical Monthly. 2004. V. 111. P. 509–517.