Набор плиток с самозамощением
Набор плиток с самозамощением (англ. 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 (большего размера). Эти треугольники дают пример шарнирного разрезания.
 |
 |
 |
Расширение и cжатие
править
Свойства наборов плиток с самозамощением означают, что эти плитки обладают свойством подстановки, то есть образуют мозаику, в которой протоплитки[англ.] могут быть разрезаны или скомбинированы с получением копии себя (меньшего или большего размера). Ясно, что повторяя процесс комбинирования плиток можно получить всё большие и большие копии (процесс называется расширением) или меньшие и меньшие (сжатие), и эти процессы можно продолжать бесконечно. Таким способом наборы с самозамощением могут образовывать непериодические мозаики. Однако ни одна из этих найденных непериодичных мозаик не является апериодичной, поскольку протоплитки можно скомбинировать с образованием периодичной мозаики. Рисунок 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].
Примечания
править- ↑ Sallows, 2012.
- ↑ Alejandro Erickson on Self-tiling tile sets. Дата обращения: 25 января 2016. Архивировано 27 апреля 2014 года.
- ↑ Gardner, 1989, с. 146—159.
- ↑ 1 2 3 Sallows, 2014, с. 100—112.
- ↑ Geometric Hidden Gems by Jean-Paul Delahaye in Scilogs Архивная копия от 31 января 2016 на Wayback Machine, April 07, 2013
- ↑ Self-Tiling Tile Sets website. Дата обращения: 25 января 2016. Архивировано 1 февраля 2016 года.
Литература
править- 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