Паркеты из полимино

В пункте а) попробуйте сложить из фигурок пентамино полосу, бесконечную в обе стороны, копиями которой потом можно было бы покрыть плоскость. То же относится к фигуркам нонамино в пункте б).

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

Чтобы получить много разных замощений, в частности, бесконечно много — как требуется в пункте б), достаточно сконструировать две различные полосы, которые потом можно комбинировать между собой. Три замощения в пункте а) можно получить таким же образом.

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

а) Для начала сложим вместе два наших пентамино — получится восьмиугольник, противоположные стороны которого попарно параллельны (рис. 3).

Рис. 3

Такими восьмиугольниками оказывается удобно мостить плоскость. Для этого будем прикладывать их параллельными сторонами друг к другу, образовывая бесконечно длинные полосы. Наиболее естественно это делать одним из двух способов, изображенных на рис. 4.

Рис. 4

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

Рис. 5

Чтобы получить еще одно замощение, посмотрим, как устроены уже построенные нами полосы. Каждая из них представляет собой что-то вроде «лесенки». Считая длину стороны квадрата, из пяти копий которого составлено пентамино, равной единице, мы можем сказать, что у первой «лесенки» длина «ступеньки» равна 3, а высота — 1. Что касается второй «лесенки», то у нее длина и ширина «ступенек» совпадают и равны 2.

Понятно, что если нам удастся сконструировать еще одну полосу-«лесенку», у которой длина и ширина «ступенек» совпадают с одним из уже указанных вариантов, то потом мы сможем скомбинировать между собой эти полосы и получить новое замощение. Удивительным образом эта полоса обнаруживается в одном из двух уже построенных замощений, хотя сама полоса отличается от двух уже известных нам «лесенок» (рис. 6).

Рис. 6

Поэтому третье из искомых замощений получается таким, как на рис. 7.

Рис. 7

Существуют и более хитрые полосы, которые приводят к замощениям. Один из примеров такого замощения приведен на рис. 8.

Рис. 8

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

Рис. 9

Другой вариант замощения получается, если мы будем чередовать положения наших фигурок: стандартное, повернутое, стандартное, повернутое и так далее — получается рисунок, похожий на мозаику паззлов (рис. 9, справа).

С первого взгляда кажется совершенно непонятным, что общего между этими двумя замощениями (если не считать форму плитки, которая лежит в их основе, конечно). Дело оказывается в том, что полосы в каждом замощении можно выделять разными способами. В частности, в первом из указанных замощений можно найти полосу, которая имеется и во втором замощении (рис. 10).

Рис. 10

Теперь мы можем, чередуя такие полосы с полосами фигурок нонамино, повернутых на 90°, получить бесконечно много разных вариантов замощения плоскости. Например, такой, который изображен на рис. 11.

Рис. 11

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

в) Среди всех 108 возможных фигурок гептамино только четыре обладают тем свойством, что их копиями нельзя замостить плоскость без пробелов и наложений: одна из них изображена справа на рис. 2, а остальные три — на рис. 12. Мы приведём доказательство этого факта только для левой из этих трех фигурок. Для двух других объяснение использует ту же самую идею, хотя и является более громоздким из-за необходимости рассмотрения большего числа случаев.

Рис. 12

Рассмотрим данную фигурку гептамино и одну из клеток, которая к ней примыкает по двум сторонам (зелёная клетка на рис. 13). Эта клетка должна быть покрыта какой-либо копией фигурки гептамино — с точностью до симметрии имеется всего два варианта такого покрытия. Для каждого из этих вариантов рассмотрим одну из клеток, которая примыкает по двум сторонам ко второй фигурке (жёлтые клетки на рис. 13). Она тоже должна быть покрыта некоторой копией данной фигурки гептамино. Однако как бы мы ни располагали третью фигурку, а впоследствии и остальные фигурки, соседняя клетка (красные клетки на рис. 13) окажется не покрыта ничем. Следовательно, данная фигурка гептамино не допускает замощения плоскости без пробелов и наложений.

Рис. 13

Термин полимино (англ.: polyomino) был введен в широкое обращение американским математиком Соломоном Голомбом в 1953 году, а затем популяризирован Мартином Гарднером. Однако это вовсе не означает, что до середины XX века человечество было совершенно незнакомо с этим понятием. Как справедливо отмечал сам Голомб, задачи о пентамино упоминаются еще в книге «Кентерберийские головоломки» английского изобретателя головоломок и развлечений Генри Дьюдени (Henry Dudeney), изданной в 1907 году, и есть основания полагать, что Дьюдени был не первым человеком, заинтересовавшимся этой темой. Кроме того, в период с 1937-го по 1957 годы в английском журнале Fairy Chess Review появился ряд статей, в которых рассматривались задачи разбиения различных фигур на части, имеющие форму n-мино для n = 1, ..., 6.

Различают три вида полимино в зависимости от того, разрешается ли переворачивать и вращать фигурки. Двусторонние полимино (англ.: free polyominoes) можно как переворачивать, так и поворачивать, односторонние полимино (англ.: one-sided polyominoes) можно только поворачивать в плоскости, а фиксированные полимино (англ.: fixed polyominoes) нельзя ни поворачивать, ни переворачивать. Существует ровно по одному типу двусторонних мономино и домино, два типа тримино и пять типов тетрамино (рис. 1). Количество различных фигурок двустороннего пентамино равно уже двенадцати (рис. 14). Чтобы запомнить их все, Голомб предложил использовать следующее мнемонеческое правило: каждой фигурке пентамино сопоставим букву латинского алфавита; семь из этих букв (TUVWXYZ) составляют конец латинского алфавита, а еще пять (FILPN) входят в имя Filipino (в оригинале книги Голомба слово «Filipino» означает «филиппинец»). К слову, тетрамино тоже иногда обозначают латинскими буквами: I, O, T, L и Z.

Рис. 14

Чем больше число n, тем большее количество различных n-мино можно составить из n единичных квадратиков, причем зависимость является экспоненциальной. Так, существует 35 различных разновидностей двустороннего гексамино, 108 разновидностей двустороннего гептамино, 369 разновидностей двустороннего октамино и более тысячи видов фигурок двустороннего нонамино. Точную формулу, которая бы отражала зависимость количества различных фигурок n-мино от числа n, пока еще никому не удалось найти, а потому в каждом конкретном случае приходится пускаться в утомительные вычисления, отнимающие уйму времени. На сегодняшний день с использованием суперкомпьютеров удалось перечислить всевозможные двусторонние полимино для всех n ≤ 28, а также всевозможные фиксированные полимино для всех n ≤ 56 — количество разновидностей последних составляет приблизительно 7·10³¹ штук.

Рис. 15. Шахматная раскраска доски без двух углов

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

1. Задача, уже ставшая классической: можно ли покрыть фигурками домино 1×2 шахматную доску 8×8, из которой вырезана пара противоположных угловых клеток? Ответ на поставленный вопрос отрицательный: раскрасив доску так, как это показано на рис. 15, легко убедиться, что эта доска содержит 32 черные и 30 белых клеток, в то время как каждая фигура домино занимает по одной клетке каждого цвета, как бы мы ее ни располагали.

2. Другая задача, похожая на первую: какую клетку из шахматной доски 8×8 нужно вырезать, чтобы ее можно было покрыть фигурками тримино 1×3? Чтобы решить ее, оказывается полезным раскрасить доску в три цвета так, как изображено слева на рис. 16. При такой раскраске черных и белых клеток поровну — по 21 штуке, а серых клеток больше — их 22. Поскольку каждая фигурка тримино занимает по одной клеточке каждого цвета, мы должны вырезать серую клетку. Однако подойдет не любая серая клетка, а лишь такие, которые при повороте доски перейдут в серые клетки — таких всего четыре (рис. 16, в середине). Одно из возможных покрытий показано справа на рис. 16.

Рис. 16

3. Шахматную доску можно покрыть копиями каждого вида тетрамино, кроме Z-тетрамино. При этом нельзя покрыть ее одним квадратом и 15-ю T-тетрамино, одним квадратом и 15-ю L-тетрамино, а также одним квадратом и 15-ю I-тетрамино (для доказательства этих фактов также используются различные раскраски доски 8×8).

4. Шахматную доску можно покрыть полным набором двусторонних пентамино и квадратным тетрамино, использовав каждую фигурку ровно один раз. При этом квадрат может быть расположен в любой части доски. Обобщение этой головоломки — покрыть полным набором двусторонних пентамино шахматную доску с произвольными четырьмя вырезанными клетками. Большинство таких задач имеют решение. Несколько примеров приведено на рис. 17.

Рис. 17. Примеры заполнения шахматной доски с четырьмя вырезанными клетками набором двусторонних пентамино. Рисунок с сайта ru.wikipedia.org

5. Полным набором двусторонних пентамино можно покрыть прямоугольники размера 6×10, 5×12, 4×15 и 3×20. При этом количество возможных решений (с точностью до поворота и отражения данного прямоугольника) для случая 6×10 составляет 2339 различных укладок, для случая 5×12 — 1010 укладок, для случая 4×15 — 368 укладок, а для случая 3×20 — всего 2 укладки. Примеры показаны на рис. 18

Рис. 18. Примеры заполнения разных прямоугольников набором двусторонних пентамино. Рисунок с сайта ru.wikipedia.org

6. Задача об утроении заключается в следующем: выбрав одну из 12 фигур пентамино, необходимо построить из каких-либо 9 оставшихся пентамино фигуру, подобную выбранной, но в 3 раза большей длины и ширины. Решение существует для любого из 12 пентамино, причем оно далеко не единственно (количество решений варьируется от 15 для Х-пентамино до 497 для Р-пентамино). На рис. 19 показано решение, найденное А. ван де Ветерингом. Оно обладает интересным свойством: каждое пентамино используется для утроения девяти из остальных, по одному разу в каждой. То есть из девяти комплектов пентамино можно одновременно сложить все 12 утроенных пентамино.

Рис. 19. Задача об утроении пентамино. Решение А. ван де Ветеринга. Рисунок с сайта ru.wikipedia.org

7. Полным набором двусторонних гексамино никакой прямоугольник покрыть нельзя. Для доказательства достаточно использовать обычную шахматную раскраску. В любом прямоугольнике при такой раскраске количество черных и белых клеток будет совпадать. А вот в наборе гексамино эти числа обязательно будут различаться, потому что 24 фигурки гексамино занимают по 3 белые и черные клетки, а оставшиеся 11 фигурок — 2 клетки одного цвета и 4 клетки другого цвета.

8. Зато полным набором двусторонних гексамино можно покрыть разные другие интересные симметричные фигуры (рис. 20).

Рис. 20. Покрытие симметричных фигур полным набором гексамино. Рисунок с сайта stepanov.lk.net

9. Особое место среди задач этой тематики занимают покрытия разных объектов фигурками домино. Так, количество покрытий прямоугольника 2×n фигурками домино выражается (n + 1)-м числом Фибоначчи. Существует также формула для числа покрытий фигурками домино прямоугольника 2m×2n, она имеет следующий вид:

10. Любая из фигурок мономино, домино, тримино, тетрамино и пентамино допускает моноэдральное замощение плоскости. Это означает, что какую из перечисленных фигурок мы ни возьмем, плоскость можно покрыть ее копиями без пробелов и наложений. При этом для всех фигурок, за исключением X-пентамино, таких замощений бесконечно много.

11. Любая из 35 фигурок гексамино допускает моноэдральное замощение плоскости. Среди 108 фигурок гептамино четыре таким свойством не обладают. Это же можно сказать про 26 из 369 фигурок октамино и 235 из 1285 фигурок нонамино.

12. Существуют наборы из нескольких фигурок полимино, которые допускают только непериодические замощения. Например, таковыми являются наборы фигурок полимино, изображённые на рис. 21.

Рис. 21. Наборы полимино, допускающие только непериодические заполнения плоскости

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

При подготовке задачи были использованы следующие материалы:
1) М. Гарднер, «Математические головоломки и развлечения», М: Мир, 1971.
2) М. Гарднер, «Математические новеллы», М: Мир, 1974.
3) С. В. Голомб, «Полимино», М: Мир, 1975.
4) Г. Дьюдени, «Кентерберийские головоломки», М: Мир, 1979.
5) B. Grünbaum, G. C. Shephard, Tilings and Patterns, 1987.