Набор плиток с самозамощением

Набор плиток с самозамощением (англ. setiset) порядка n — это набор из n фигур, обычно плоских, каждая из которых допускает замощение меньшими копиями тех же n фигур. Более точно, n фигур могут быть собраны n различными способами, дающими большие копии фигур из того же набора, и коэффициент увеличения один и тот же. Рисунок 1 показывает пример для n = 4 с использованием декамино различной формы. Концепцию можно обобщить и использовать фигуры большей размерности. Название setisets дал Ли Сэллоус (англ. Lee Sallows) в 2012 году^[1][2], но задача нахождения таких наборов для n = 4 поставил задолго до этого Дадли Лэнгфорд (англ. C. Dudley Langford), а примеры для фигур полиаболо (найдены Мартином Гарднером, Уэйдом Филпоттом и др.) и полимино (найдены Маурисом Пова (англ. Maurice J. Povah)) опубликованы до этого Гарднером^[3].

Из определения выше следует, что набор плиток с самозамощением, состоящий из n одинаковых фигур, является «делящейся» плиткой, для которой плитки с самозамощением являются обобщением^[4]. Наборы из n различных фигур, такие как на рисунке 1, называются совершенными. Рисунок 2 показывает пример для n = 4 и он не является совершенным, поскольку две плитки в наборе имеют ту же самую форму.

Фигуры в наборах не обязательно должны быть связными областями. Разъединённые фигуры, составленные из двух и более отдельных островков, разрешаются также. Такие фигуры считаются разъединёнными или слабо связанными (если островки имеют одну общую точку), как показано на рисунке 3.

Наименьшее число плиток в наборе — 2. Рисунок 4 включает бесконечное семейство наборов порядка 2, каждый из которых состоит из двух треугольников P и Q. Как показано на рисунке, треугольники можно шарнирно соединить так, что вращение вокруг шарнира даёт те же треугольники P или Q (большего размера). Эти треугольники дают пример шарнирного разрезания.

Свойства наборов плиток с самозамощением означают, что эти плитки обладают свойством подстановки, то есть образуют мозаику, в которой протоплитки^[англ.] могут быть разрезаны или скомбинированы с получением копии себя (меньшего или большего размера). Ясно, что повторяя процесс комбинирования плиток можно получить всё большие и большие копии (процесс называется расширением) или меньшие и меньшие (сжатие), и эти процессы можно продолжать бесконечно. Таким способом наборы с самозамощением могут образовывать непериодические мозаики. Однако ни одна из этих найденных непериодичных мозаик не является апериодичной, поскольку протоплитки можно скомбинировать с образованием периодичной мозаики. Рисунок 5 показывает первые две стадии расширения набора порядка 4, которое ведёт к непериодичной мозаике.

Кроме наборов с самозамощением, которые можно считать петлями длины 1, существуют более длинные петли или замкнутые цепочки наборов плиток, в которых каждый набор замощает предыдущий^[5]. Рисунок 6 показывает пару взаимно замощающих наборов плиток декамино, другими словами, петлю длины 2. Сэллоус и Шотель (англ. Schotel) провели исчерпывающий поиск наборов порядка 4, состоящих из октамино. Кроме семи обычных наборов (с петлями длины 1) они нашли удивительно большое число наборов с петлями всех длин вплоть до 14. Общее число обнаруженных петель насчитывает около полутора миллионов. Дальнейшие исследования в этом направлении не завершены, но похоже на истину, что и другие наборы плиток могут содержать петли^[6].

До настоящего времени использовались два метода для получения самозамощаемых наборов плиток. В случае, когда набор состоит из фигур типа полимино, в которых число частей закреплено, возможен поиск прямым компьютерным перебором. Легко показать, что число плиток n должно быть квадратом^[4]. Рисунки 1, 2, 3, 5 и 6 являются примерами, найденными таким образом.

Другой способ заключается в разрезании нескольких копий «делящейся» плитки неким способом, который приводит к самозамощаемому набору. Рисунки 7 и 8 показывают наборы, полученные таким образом. В них каждая плитка является объединением двух и трёх «делящихся» плиток соответственно. На рисунке 8 можно видеть, каким образом 9 плиток (сверху) вместе замощают 3 «делящиеся» плитки (снизу), в то время как сами эти 9 плиток образуются объединением тех же самых трёх «делящихся» плиток. Таким образом каждая плитка может быть получена замощением каждой формы меньшими плитками из того же набора 9 плиток^[4].

• Martin Gardner. Глава «Polyhexes and Polyaboloes» // Mathematical Magic Show. — Washington, D. C.: The Mathematical Association of Americf, 1989. — ISBN 0-88385-448-1. (Переиздание, книги 1977, издательство Alfred A. Knopf)
• Lee Sallows. More On Self-Tiling Tile Sets // Mathematics Magazine. — 2014. — Т. 87, вып. 2.
• Lee Sallows. On Self-Tiling Tile Sets // Mathematics Magazine. — 2012. — Т. 85, вып. 5. — С. 323—333.
• Geometric Hidden Gems by Jean-Paul Delahaye in Scilogs, April 07, 2013

• Self-Tiling Tile Sets website