Полимино — это плоская геометрическая фигура , образованная соединением одного или нескольких равных квадратов от края к краю. Это полиформа , ячейки которой имеют квадратную форму. Его можно рассматривать как конечное подмножество правильной квадратной мозаики .
Полимино используются в популярных головоломках по крайней мере с 1907 года, а перечисление пентамино датируется древностью. [1] Многие результаты с фигурами размером от 1 до 6 клеток были впервые опубликованы в журнале Fairy Chess Review в период с 1937 по 1957 год под названием « Задачи о расчленении ». Название полимино было изобретено Соломоном Голомбом в 1953 году [2] и популяризировано Мартином Гарднером в колонке « Математические игры » в журнале Scientific American в ноябре 1960 года . [3]
С полимино связаны полиалмазы , образованные из равносторонних треугольников ; многогексы , образованные из правильных шестиугольников ; и другие плоские полиформы . Полимино были обобщены на более высокие измерения путем объединения кубов в поликубы или гиперкубов в полигиперкубы.
В статистической физике изучение полимино и их многомерных аналогов (которые в этой литературе часто называют решетчатыми животными ) применяется к задачам физики и химии. Полимино использовались в качестве моделей разветвленных полимеров и перколяционных кластеров. [4]
Как и многие головоломки в развлекательной математике , полимино поднимает множество комбинаторных задач. Самый простой — это перебор полимино заданного размера. Никакой формулы не найдено, за исключением особых классов полимино. Известен ряд оценок и существуют алгоритмы их расчета.
Полимино с дырками неудобно для некоторых целей, например, для решения задач мозаики. В некоторых контекстах полимино с отверстиями исключаются, позволяя использовать только односвязные полимино. [5]
Существует три распространенных способа различения полимино для перечисления: [6] [7]
В следующей таблице показано количество полимино разных типов с n ячейками.
По состоянию на 2004 год [обновлять]Иван Дженсен перечислил фиксированные полимино до n = 56 – примерно 6,915 × 10.31 . [8]
Свободные полимино были пронумерованы в 2007 году до n = 28 Томасом Оливейрой и Силвой [9] , в 2012 году до n = 45 Тошихиро Сиракавой [10] и в 2023 году до n = 50 Джоном Мэйсоном. [11]
Вышеупомянутые последовательности OEIS, за исключением A001419, включают счетчик 1 для количества нулевых полимино; нуль-полимино — это полимино, состоящее из нулевых квадратов.
Группа диэдра D 4 — это группа симметрий ( группа симметрии ) квадрата. Эта группа содержит четыре вращения и четыре отражения. Он генерируется попеременными отражениями относительно оси x и диагонали. Одному свободному полимино соответствует не более 8 фиксированных полимино, которые являются его образами при симметриях D 4 . Однако эти изображения не обязательно различны: чем больше симметрии у свободного полимино, тем меньше у него различных фиксированных аналогов. Следовательно, свободное полимино, инвариантное относительно некоторых или всех нетривиальных симметрий D4 , может соответствовать только 4, 2 или 1 фиксированному полимино. Математически свободные полимино представляют собой классы эквивалентности фиксированных полимино в группе D 4 .
Полимино имеют следующие возможные симметрии; [12] в каждом случае указано наименьшее количество квадратов, необходимое в полимино с такой симметрией:
Точно так же количество односторонних полимино зависит от симметрии полимино следующим образом:
В следующей таблице показано количество полимино с n квадратами, отсортированных по группам симметрии.
[13]
Каждое полимино размера n +1 можно получить добавлением квадрата к полимино размера n . Это приводит к алгоритмам индуктивного генерирования полимино.
Проще всего, если имеется список полимино размера n , квадраты могут быть добавлены рядом с каждым полимино в каждой возможной позиции, а полученное полимино размера n +1 добавлено в список, если оно не является дубликатом уже найденного; уточнения в порядке перечисления и маркировки соседних квадратов, которые не следует учитывать, уменьшают количество случаев, которые необходимо проверять на наличие дубликатов. [14] Этот метод можно использовать для подсчета как свободных, так и фиксированных полимино.
Более сложный метод, описанный Редельмейером, использовался многими авторами как способ не только подсчета полимино (без требования, чтобы все полимино размера n были сохранены в размере для подсчета полимино размера n +1), но и для доказательства верхнего ограничения на их количество. Основная идея заключается в том, что мы начинаем с одного квадрата, а затем рекурсивно добавляем квадраты. В зависимости от деталей, он может считать каждое n -мино n раз, по одному разу, начиная с каждого из n квадратов, или может быть настроен на подсчет каждого только один раз.
Самая простая реализация предполагает добавление по одному квадрату за раз. Начиная с начального квадрата, пронумеруйте соседние квадраты по часовой стрелке сверху: 1, 2, 3 и 4. Теперь выберите число от 1 до 4 и добавьте квадрат в этом месте. Пронумеруйте ненумерованные соседние квадраты, начиная с 5. Затем выберите число, большее, чем выбранное ранее число, и добавьте этот квадрат. Продолжайте выбирать число, большее, чем номер текущего квадрата, добавляя этот квадрат, а затем нумеруя новые соседние квадраты. Когда было создано n квадратов, было создано n -омино.
Этот метод гарантирует, что каждое фиксированное полимино будет подсчитано ровно n раз, по одному разу для каждого начального квадрата. Его можно оптимизировать так, чтобы каждое полимино считалось только один раз, а не n раз. Начиная с начального квадрата, объявите его нижним левым квадратом полимино. Просто не нумеруйте квадраты, находящиеся в нижнем ряду или слева от квадратов в том же ряду. Это версия, описанная Редельмейером.
Если вместо этого кто-то хочет подсчитать свободные полимино, то можно проверить симметрию после создания каждого n -омино. Однако быстрее [15] сгенерировать симметричные полимино отдельно (разновидностью этого метода) [16] и таким образом определить количество свободных полимино по лемме Бернсайда .
Самый современный алгоритм подсчета фиксированных полимино был открыт Иваном Дженсеном. [17] Улучшение метода Эндрю Конвея, [18] он экспоненциально быстрее, чем предыдущие методы (однако время его работы по-прежнему экспоненциально зависит от n ).
Версии метода трансфер-матрицы, предложенные Конвеем и Дженсеном, включают подсчет количества полимино, имеющих определенную ширину. Вычисление числа для всех ширин дает общее количество полимино. Основная идея метода заключается в том, что рассматриваются возможные начальные строки, а затем определяется минимальное количество квадратов, необходимое для завершения полимино заданной ширины. В сочетании с использованием генерирующих функций этот метод позволяет подсчитывать множество полимино одновременно, что позволяет ему работать во много раз быстрее, чем методы, которые должны генерировать каждое полимино.
Несмотря на превосходное время работы, компромисс заключается в том, что этот алгоритм использует экспоненциальные объемы памяти (многие гигабайты памяти необходимы для n выше 50), его гораздо сложнее программировать, чем другие методы, и в настоящее время его нельзя использовать для подсчета. бесплатные полимино.
Теоретические аргументы и численные расчеты подтверждают оценку количества фиксированных полимино размера n.
где λ = 4,0626 и с = 0,3169. [19] Однако этот результат не доказан, а значения λ и c являются лишь оценками.
Известные теоретические результаты далеко не так конкретны, как эта оценка. Доказано, что
существует. Другими словами, An растет экспоненциально . Самая известная нижняя граница λ , найденная в 2016 году, равна 4,00253. [20] Самая известная верхняя граница — λ < 4,5252 . [21]
Чтобы установить нижнюю границу, существует простой, но очень эффективный метод — объединение полимино. Определите верхний правый квадрат как самый правый квадрат в самой верхней строке полимино. Аналогичным образом определите нижний левый квадрат. Затем правый верхний квадрат любого полимино размера n можно присоединить к левому нижнему квадрату любого полимино размера m , чтобы получить уникальное ( n + m )-мино. Это доказывает A n A m ≤ A n + m . Используя это уравнение , можно показать λ ≥ ( An ) 1/ n для всех n . Уточнения этой процедуры в сочетании с данными для An дают нижнюю границу, приведенную выше.
Верхняя оценка достигается обобщением индуктивного метода перебора полимино. Вместо того, чтобы добавлять по одному квадрату за раз, за раз добавляется группа квадратов. Это часто называют добавлением веток . Доказывая, что каждое n -мино представляет собой последовательность веточек, и доказывая пределы комбинаций возможных веточек, можно получить верхнюю границу числа n -мино. Например, в изложенном выше алгоритме на каждом шаге мы должны выбирать большее число, и добавляется не более трех новых чисел (поскольку к любому пронумерованному квадрату примыкает не более трех ненумерованных клеток). Это можно использовать для получения верхней границы 6,75. Используя 2,8 миллиона ветвей, Кларнер и Ривест получили верхнюю границу 4,65, [22] которая впоследствии была улучшена Барекетом и Шалахом до 4,5252. [21]
Аппроксимации количества фиксированных и свободных полимино связаны простым образом. Свободное полимино без симметрии (вращение или отражение) соответствует 8 различным фиксированным полимино, а при больших n большинство n -омино не имеют симметрии. Следовательно, количество фиксированных n -амино примерно в 8 раз превышает количество свободных n -амино. Более того, это приближение экспоненциально точнее с увеличением n . [12]
Известны точные формулы перечисления полимино специальных классов, таких как класс выпуклых полимино и класс направленных полимино.
Определение выпуклого полимино отличается от обычного определения выпуклости , но похоже на определение, используемое для ортогональной выпуклой оболочки . Полимино называется выпуклым по вертикали или по столбцу , если его пересечение с любой вертикальной линией выпукло (другими словами, в каждом столбце нет отверстий). Аналогично, полимино называется выпуклым по горизонтали или ряду, если его пересечение с любой горизонтальной линией выпукло. Полимино называется выпуклым , если оно выпукло по строкам и столбцам. [23]
Полимино называется направленным, если оно содержит квадрат, известный как корень , такой, что в любой другой квадрат можно попасть, перемещаясь на один квадрат вверх или вправо, не покидая полимино.
Направленные полимино, [24] столбцы (или строки), выпуклые полимино, [25] и выпуклые полимино [26] эффективно нумеруются по площади n , а также по некоторым другим параметрам, таким как периметр, с использованием производящих функций .
Полимино называется равномерным, если его площадь равна периметру. Равное полимино должно состоять из четного числа квадратов; возможно любое четное число больше 15. Например, 16-мино в форме квадрата 4 × 4 и 18-мино в форме прямоугольника 3 × 6 равны. Для полимино с 15 квадратами или меньше периметр всегда превышает площадь. [27]
В развлекательной математике часто возникают задачи по замощению заданной области или всей плоскости полимино [28] , а связанные с этим проблемы исследуются в математике и информатике .
Головоломки обычно требуют разложить заданную область заданным набором полимино, например 12 пентамино. В книгах Голомба и Гарднера есть много примеров. Типичная головоломка — выложить прямоугольник 6×10 двенадцатью пентамино; 2339 решений этой проблемы были найдены в 1960 году. [29] Там, где разрешено несколько копий полимино в наборе, Голомб определяет иерархию различных областей, которые набор может иметь возможность мозаики, таких как прямоугольники, полосы и целые области. плоскости, и показывает, что вопрос о том, могут ли полимино из заданного набора замостить плоскость, неразрешим , путем сопоставления наборов плиток Ванга с наборами полимино. [30]
Поскольку общая проблема замощения областей плоскости наборами полимино является NP-полной , [31] замощение из более чем нескольких частей быстро становится неразрешимым, и поэтому требуется помощь компьютера. Традиционный подход к мозаике конечных областей плоскости использует метод информатики, называемый обратным поиском . [32]
В Jigsaw Sudokus квадратная сетка состоит из областей в форме многочлена (последовательность A172477 в OEIS ).
Другой класс задач спрашивает, могут ли копии данного полимино замостить прямоугольник , и если да, то какие прямоугольники они могут замостить. [33] Эти проблемы были тщательно изучены для конкретных полимино, [34] и доступны таблицы результатов для отдельных полимино. [35] Кларнер и Гёбель показали, что для любого полимино существует конечное множество простых прямоугольников, которые оно замостило, так что все остальные прямоугольники, которые оно замостило, можно замостить этими простыми прямоугольниками. [36] [37] Каменецкий и Кук показали, как различные непересекающиеся (называемые «дырчатыми») полимино могут замостить прямоугольники. [38]
Помимо прямоугольников, Голомб дал свою иерархию для одиночных полимино: полимино может замостить прямоугольник, половину полосы, изогнутую полосу, увеличенную копию самого себя, квадрант, полосу, полуплоскость , всю плоскость, определенные комбинации или ничего из этого. Среди них есть определенные последствия, как очевидные (например, если полимино замостит полуплоскость, то он замостит всю плоскость), так и менее очевидные (например, если полимино замостит увеличенную копию самого себя, то он замостит квадрант) . В этой иерархии характеризуются полимино размером до 6 (со статусом одного гексомино, которое, как позже выяснилось, замостило прямоугольник, не разрешенное на тот момент). [39]
В 2001 году Кристофер Мур и Джон Майкл Робсон показали, что задача замощения одного полимино копиями другого является NP-полной . [40] [41]
Замощение плоскости копиями одного полимино также много обсуждалось. В 1965 г. было отмечено, что все полимино вплоть до гексомино [42] и все гептамино, кроме четырех, замощают плоскость. [43] Затем Дэвид Берд установил, что все октамино, за исключением 26, украшают плоскость. [44] Росторн обнаружил, что все полимино, кроме 235, имеют размер 9 плиток, [45] и такие результаты были распространены на более высокие области Роудсом (до размера 14) [46] и другими. Полимино, замощающие плоскость, классифицируются по симметрии их замощений и по количеству аспектов (ориентаций), в которых плитки появляются в них. [47] [48]
Изучение того, какие полимино могут замостить плоскость, было облегчено с помощью критерия Конвея : за исключением двух нономино, все мозаичные полимино до размера 9 образуют участок, по крайней мере, из одной плитки, удовлетворяющей этому критерию, с более частыми исключениями большего размера. [49]
Несколько полимино могут замостить более крупные копии самих себя, и повторение этого процесса рекурсивно дает мозаику плоскости в виде рептилий . Например, для каждого положительного целого числа n можно объединить n 2 копий L-тромино, L-тетромино или P-пентамино в одну большую фигуру, аналогичную меньшему полимино, из которого оно было сформировано. [50]
Проблема совместимости состоит в том, чтобы взять два или более полимино и найти фигуру, которую можно объединить в мозаику. Совместимость полимино широко изучается с 1990-х годов. Хорхе Луис Мирелес и Джованни Реста опубликовали на веб-сайтах систематические результаты, [51] [52] , а Ливио Зукка показывает результаты для некоторых сложных случаев, таких как три разных пентамино. [53] Общая проблема может оказаться сложной. Первая фигура совместимости пентамино L и X была опубликована в 2005 году и содержала по 80 плиток каждого вида. [54] Многие пары полимино оказались несовместимыми в результате систематического исчерпания. Неизвестен алгоритм определения совместимости двух произвольных полимино.
Помимо описанных выше проблем с мозаикой, существуют развлекательные математические головоломки, которые требуют сложения полимино для создания других фигур. Гарднер предложил несколько простых игр с набором свободных пентамино и шахматной доской. В некоторых вариантах головоломки судоку на сетке используются участки в форме неномино. Видеоигра «Тетрис» основана на семи односторонних тетромино (в игре пишется «Тетримино»), а в настольной игре « Блокус» используются все свободные полимино вплоть до пентамино.
Слово полимино и названия полимино различных размеров являются обратными образованиями от слова домино , обычной игровой фигуры, состоящей из двух квадратов, первая буква d- причудливо интерпретируется как версия префикса di , означающего «два». ." Считается, что название этой игровой фигуры «домино» произошло от пятнистого домино в маскарадной одежде , от латинского dominus . [55]
Большинство числовых префиксов греческие. Полимино размера 9 и 11 чаще принимают латинские префиксы нона- (нономино) и ундека- (ундекомино), чем греческие префиксы эннеа- (эннеомино) и хендека- (хендекомино). [ почему? ]