Минимальный продуктовый набор
- 1 year ago
- 0
- 0
Набор плиток с самозамощением ( англ. setiset ) порядка n — это набор из n фигур, обычно плоских, каждая из которых допускает замощение меньшими копиями тех же n фигур. Более точно, n фигур могут быть собраны n различными способами, дающими большие копии фигур из того же набора, и коэффициент увеличения один и тот же. Рисунок 1 показывает пример для n = 4 с использованием декамино различной формы. Концепцию можно обобщить и использовать фигуры большей размерности. Название setisets дал ( англ. ) в 2012 году , но задача нахождения таких наборов для n = 4 поставил задолго до этого Дадли Лэнгфорд ( англ. C. Dudley Langford ), а примеры для фигур полиаболо (найдены Мартином Гарднером , Уэйдом Филпоттом и др.) и полимино (найдены Маурисом Пова ( англ. Maurice J. Povah )) опубликованы до этого Гарднером .
Из определения выше следует, что набор плиток с самозамощением, состоящий из n одинаковых фигур, является «делящейся» плиткой , для которой плитки с самозамощением являются обобщением . Наборы из n различных фигур, такие как на рисунке 1, называются совершенными . Рисунок 2 показывает пример для n = 4 и он не является совершенным , поскольку две плитки в наборе имеют ту же самую форму.
Фигуры в наборах не обязательно должны быть связными областями. Разъединённые фигуры, составленные из двух и более отдельных островков, разрешаются также. Такие фигуры считаются разъединёнными или слабо связанными (если островки имеют одну общую точку), как показано на рисунке 3.
Наименьшее число плиток в наборе — 2. Рисунок 4 включает бесконечное семейство наборов порядка 2, каждый из которых состоит из двух треугольников P и Q . Как показано на рисунке, треугольники можно шарнирно соединить так, что вращение вокруг шарнира даёт те же треугольники P или Q (большего размера). Эти треугольники дают пример шарнирного разрезания .
Свойства наборов плиток с самозамощением означают, что эти плитки обладают свойством подстановки , то есть образуют мозаику , в которой могут быть разрезаны или скомбинированы с получением копии себя (меньшего или большего размера). Ясно, что повторяя процесс комбинирования плиток можно получить всё большие и большие копии (процесс называется расширением) или меньшие и меньшие (сжатие), и эти процессы можно продолжать бесконечно. Таким способом наборы с самозамощением могут образовывать непериодические мозаики. Однако ни одна из этих найденных непериодичных мозаик не является апериодичной , поскольку протоплитки можно скомбинировать с образованием периодичной мозаики. Рисунок 5 показывает первые две стадии расширения набора порядка 4, которое ведёт к непериодичной мозаике.
Кроме наборов с самозамощением, которые можно считать петлями длины 1, существуют более длинные петли или замкнутые цепочки наборов плиток, в которых каждый набор замощает предыдущий . Рисунок 6 показывает пару взаимно замощающих наборов плиток декамино , другими словами, петлю длины 2. Сэллоус и Шотель ( англ. Schotel ) провели исчерпывающий поиск наборов порядка 4, состоящих из октамино . Кроме семи обычных наборов (с петлями длины 1) они нашли удивительно большое число наборов с петлями всех длин вплоть до 14. Общее число обнаруженных петель насчитывает около полутора миллионов. Дальнейшие исследования в этом направлении не завершены, но похоже на истину, что и другие наборы плиток могут содержать петли .
До настоящего времени использовались два метода для получения самозамощаемых наборов плиток. В случае, когда набор состоит из фигур типа полимино , в которых число частей закреплено, возможен поиск прямым компьютерным перебором. Легко показать, что число плиток n должно быть квадратом . Рисунки 1, 2, 3, 5 и 6 являются примерами, найденными таким образом.
Другой способ заключается в разрезании нескольких копий «делящейся» плитки неким способом, который приводит к самозамощаемому набору. Рисунки 7 и 8 показывают наборы, полученные таким образом. В них каждая плитка является объединением двух и трёх «делящихся» плиток соответственно. На рисунке 8 можно видеть, каким образом 9 плиток (сверху) вместе замощают 3 «делящиеся» плитки (снизу), в то время как сами эти 9 плиток образуются объединением тех же самых трёх «делящихся» плиток. Таким образом каждая плитка может быть получена замощением каждой формы меньшими плитками из того же набора 9 плиток .