Шарнирные пентамино

Необходимое условие замощения: количество клеток в зубчатом квадрате должно делиться на 5.

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

Рис. 2.

Начнем с формулы для числа клеток в зубчатом квадрате порядка n. Проще всего раскрасить клетки зубчатого квадрата в шахматном порядке (как на рис. 2) и внимательно посмотреть на то, что получилось. Видно, что клетки каждого цвета образуют квадраты (поставленные на угловую клетку): на стороне одного помещается n клеток, на стороне второго — \(n+1\) клеток. Значит, в зубчатом квадрате \(N=n^2+(n+1)^2\) клеток. Ясно, что в нашей задаче это число должно делиться на 5.

Любое натуральное число можно разделить на 5 с остатком, то есть представить в виде \(5k+r\), где \(k\) — частное, а \(r\) — остаток. Поскольку остаток всегда меньше делителя, то \(r\in 0, 1, 2, 3, 4\). Нетрудно проверить, что только при \(n=5k+1\) и \(n=5k+3\) число \(N\) кратно 5. Действительно, если \(n=5k+1\), то \(N=(5k+1)^2+(5k+2)^2 =50k^2+30k+5\), а если \(n=5k+3\), то \(N=(5k+3)^2 +(5k+4)^2 = 50k^2+70k+25\).

Очевидно, что крест из пяти клеток, который заодно является зубчатым квадратом порядка 1, нельзя замостить гирляндой. А вот прямоугольник 1×5 клеток можно замостить одной гирляндой. На рис. 3 показаны еще две фигуры из 25 клеток, каждая из которых замощается пятью гирляндами. Правая из фигур — зубчатый квадрат порядка 3.

Рис. 3.

Фигуры с рис. 3 служат строительными блоками для зубчатых квадратов большего размера. На рис. 4 показано, как при помощи двух треугольников и 14 прямоугольников 1×5 окаймить зубчатый квадратом порядка 3, чтобы получился зубчатый квадрат порядка 8. Продолжая окаймлять этот квадрат по аналогии, получим замощения всех зубчатых квадратов порядка \(n=5k+3\).

Рис. 4.

Такими же окаймлениями можно получить замощения и квадратов порядка \(n=5k+1\). Только в этом случае надо начинать с \(n=6\), поскольку, как уже говорилось, квадрат для \(n=1\) не замощается. Построение зубчатого квадрата порядка 6 показано на рис. 5: нужно окружить квадрат порядка 3 гирляндами в три ряда.

Рис. 5.

Говоря о шарнирных пентамино, нельзя не обсудить их связь с классическим набором пентамино. В нем 12 фигурок, они показаны на рис. 6. Проведя небольшое исследование, можно заметить, что только пять из них можно получить из шарнирного пентамино (выделены цветом на рис. 6).

Рис. 6.

Набор пентамино встречается во многих головоломках и задачах (см. Паркеты из полимино). В частности, есть аналогичная танграму головоломка, которая так и называется «Пентамино». Ее цель — складывать из всех 12 фигурок пентамино разнообразные фигуры, составленные из 60 клеток. Примеры таких заданий показаны на рис. 7.

Рис. 7. Примеры заданий для головоломки «Пентамино»: требуется сложить «бабочку», «верблюда» и «оленя». Рисунки с сайта ot2do6.ru

Шарнирное пентамино заменяет собой всего пять из 12 элементов классического набора пентамино, но несмотря на это, многие задания головоломки можно выполнить, используя только шарнирные пентамино. Дело в том, что «достаточно плотная» фигура из 60 клеток часто допускает много замощений фигурками пентамино, причем не только полным набором, но и разными его подмножествами (в этих случаях некоторые фигурки можно использовать больше одного раза). Пример фигуры, которую нельзя замостить шарнирными пентамино, — олень, изображенный на рис. 7 справа (докажите, что это правда так). Желающие поразвлекаться и порешать обсуждаемые головоломки могут попробовать замостить фигуры с рис. 7 классическим набором пентамино, а потом — «верблюда» и «бабочку» при помощи шарнирных пентамино.

Слово «полимино» было придумано американским математиком, специалистом по комбинаторному анализу и теории чисел Соломоном Голомбом в 1953 году. Сами эти фигурки, естественно, встречались в задачках и головоломках и раньше. Он же позже написал книгу с таким же названием, ставшую фактически энциклопедией пентамино и родственных с ней наборов составленных из единичных квадратов фигурок, в которой рассматриваются их многочисленные свойства и обобщения.

В этой книге, в частности, приводится 60-клеточная фигура неправильной формы, сложенная из элементов пентамино и являющаяся разверткой куба с ребром \(\sqrt{10}\). Она показана слева на рис. 8. Для сравнения, из 12 шарнирных пентамино можно сложить симметричную «вертушку» (рис. 8, справа), которая тоже является разверткой куба.

Рис. 8.

Также в этой книге с помощью долгих рассуждений доказывается, что зубчатый квадрат с дыркой в центре (рис. 9, слева) нельзя сложить из классического набора пентамино. С использованием шарнирных пентамино, как несложно убедиться, эта задача становится разрешимой. На рис. 9 справа показано как это сделать: зубчатый квадрат разделен на четыре части, каждую из которых можно замостить гирляндами шарнирного пентамино.

Рис. 9.

В книге Голомба есть и список нерешенных проблем: в него он включил задачи, которые на тот момент никто не решил с помощью пентамино, но их неразрешимость тоже не была доказана. Там же есть и некоторые фигуры, про которые уже было доказано, что их невозможно замостить классическим набором пентамино. С некоторым из них шарнирные пентамино позволяют легко справиться. Примеры, замощения которых мы предлагаем придумать читателям, показаны на рис. 10. Фигура слева называется «ацтекским бриллиантом», она из списка нерешенных задач Голомба. Про фигуру справа — зубчатый прямоугольник — доказано, что ее нельзя замостить обычными пентамино.

Рис. 10.