Полимино, или полиомино (англ. polyomino) — плоские геометрические фигуры, образованные путём соединения нескольких одноклеточных квадратов по их сторонам. Это полиформы, сегменты которых являются квадратами[1].
Фигуру полимино можно рассматривать как конечное связное подмножество бесконечной шахматной доски, которое может обойти ладья[1][3].
Названия полимино
Полимино (n-мино) носят названия по числу n квадратов, из которых они состоят:
История
Полимино использовались в занимательной математике по крайней мере с 1907 года[4][5], а известны были ещё в древности. Многие результаты с фигурами, содержащими от 1 до 6 квадратов, были впервые опубликованы в журнале «Fairy Chess Review» в период с 1937 по 1957 г., под названием «проблемы рассечения» (англ. «dissection problems»). Название «полимино» или «полиомино» (англ. polyomino) было придумано Соломоном Голомбом[1] в 1953 году и затем популяризировано Мартином Гарднером[6][7].
В 1967 году журнал «Наука и жизнь» опубликовал серию статей о пентамино. В дальнейшем в течение ряда лет публиковались задачи, связанные с полимино и другими полиформами[8].
Обобщения полимино
В зависимости от того, разрешается ли переворачивание или вращение фигур, различаются следующие три вида полимино[1][2]:
- двусторонние полимино, или свободные полимино (англ. free polyominoes) — полимино, которые разрешается поворачивать и переворачивать;
- односторонние полимино (англ. one-sided polyominoes) — полимино, которые разрешается поворачивать в плоскости, но не разрешается переворачивать;
- фиксированные полимино (англ. fixed polyominoes) — полимино, которые не разрешается ни поворачивать, ни переворачивать.
В зависимости от условий связности соседних ячеек различаются[1][9][10]:
- полимино — наборы квадратов, которые может обойти визирь[3];
- псевдополимино, или полиплеты — наборы квадратов, которые может обойти король;
- квазиполимино — произвольные наборы квадратов бесконечной шахматной доски.
В следующей таблице собраны данные о числе фигур полимино и его обобщений. Число квази-n-мино равно 1 при n = 1 и ∞ при n > 1.
| n | полимино | псевдополимино | ||||||
|---|---|---|---|---|---|---|---|---|
| двусторонние | односторонние | фиксированные | двусторонние | односторонние | фиксированные | |||
| все | с отверстиями | без отверстий | ||||||
| A000105 | A001419 | A000104 | A000988 | A001168 | A030222 | A030233 | A006770 | |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 0 | 1 | 1 | 2 | 2 | 2 | 4 |
| 3 | 2 | 0 | 2 | 2 | 6 | 5 | 6 | 20 |
| 4 | 5 | 0 | 5 | 7 | 19 | 22 | 34 | 110 |
| 5 | 12 | 0 | 12 | 18 | 63 | 94 | 166 | 638 |
| 6 | 35 | 0 | 35 | 60 | 216 | 524 | 991 | 3832 |
| 7 | 108 | 1 | 107 | 196 | 760 | 3031 | 5931 | 23 592 |
| 8 | 369 | 6 | 363 | 704 | 2725 | 18 770 | 37 196 | 147 941 |
| 9 | 1285 | 37 | 1248 | 2500 | 9910 | 118 133 | 235 456 | 940 982 |
| 10 | 4655 | 195 | 4460 | 9189 | 36 446 | 758 381 | 1 514 618 | 6 053 180 |
| 11 | 17 073 | 979 | 16 094 | 33 896 | 135 268 | 4 915 652 | 9 826 177 | 39 299 408 |
| 12 | 63 600 | 4 663 | 58 937 | 126 759 | 505 861 | 32 149 296 | 64 284 947 | 257 105 146 |
Полиформы
Полиформы — обобщение полимино, ячейками которого могут быть любые одинаковые многоугольники или многогранники. Иначе говоря, полиформа — плоская фигура или пространственное тело, состоящая из нескольких соединённых копий заданной основной формы[11].
Плоские (двумерные) полиформы включают в себя полиамонды, сформированные из равносторонних треугольников; полигексы, сформированные из правильных шестиугольников; полиаболо, состоящие из равнобедренных прямоугольных треугольников, и другие.
Примеры пространственных (трёхмерных) полиформ: поликубы, состоящие из трёхмерных кубов; полироны (англ. polyrhons), состоящие из ромбододекаэдров[12].
Полиформы также обобщаются на случай более высоких размерностей (например, сформированные из гиперкубов — полигиперкубы).
Задачи
Покрытия прямоугольников конгруэнтными полимино
Порядок полимино P — минимальное число конгруэнтных копий P, достаточное для того, чтобы сложить некоторый прямоугольник. Для полимино, из копий которых нельзя сложить ни одного прямоугольника, порядок не определён. Порядок полимино P равен 1 тогда и только тогда, когда P — прямоугольник[13].
Если существует хотя бы один прямоугольник, который можно покрыть нечётным числом конгруэнтных копий P, полимино P называется нечётным полимино; если же прямоугольник можно сложить только из чётного числа копий P, P называется чётным полимино.
Эта терминология была введена в 1968 году Д. А. Кларнером[англ.][1][14].
Существует множество полимино порядка 2; примером являются так называемые L-полимино[15].
Полимино порядка 3 не существует; доказательство этого было опубликовано в 1992 году[16]. Любое полимино, из трёх копий которого можно составить прямоугольник, само является прямоугольником и имеет порядок 1. Неизвестно, существует ли полимино, порядок которого — нечётное число, большее 3[14].
Существуют полимино порядка 4, 10, 18, 24, 28, 50, 76, 92, 312; существует конструкция, позволяющая получить полимино порядка 4s для любого натурального s[14].
Кларнеру удалось найти непрямоугольное полимино порядка 2, из 11 копий которого можно составить прямоугольник[1][14][17], причём никакое ме́ньшее нечётное число копий этого полимино не может покрыть прямоугольник. На октябрь 2015 года неизвестно, существует ли непрямоугольное полимино, из 9, 7 или 5 копий которого можно составить прямоугольник; неизвестны также какие-либо другие примеры полимино с минимальной нечётной кратностью покрытия 11 (кроме найденного Кларнером).
Минимальные области
Минимальная область (англ. minimal region, minimal common superform) для заданного набора полимино — полимино наименьшей возможной площади, содержащее каждое полимино из данного набора[1][14][18]. Задача нахождения минимальной области для набора двенадцати пентамино была впервые поставлена Т. Р. Доусоном в журнале Fairy Chess Review[англ.] в 1942 году[18].
Для набора 12 пентамино существуют две минимальные девятиклеточные области, представляющие собой 2 из 1285 нонамино[1][14][18]:
### ### ##### ##### # #
См. также
Примечания
Литература
Ссылки
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
