Русская Википедия:Полимино
Полимино, или полиомино (Шаблон:Lang-en) — плоские геометрические фигуры, образованные путём соединения нескольких одноклеточных квадратов по их сторонам. Это полиформы, сегменты которых являются квадратами[1].
Фигуру полимино можно рассматривать как конечное связное подмножество бесконечной шахматной доски, которое может обойти ладья[1][3].
Названия полимино
Полимино (n-мино) носят названия по числу n квадратов, из которых они состоят:
| n | Название | n | Название |
|---|---|---|---|
| 1 | мономино | 6 | гексамино |
| 2 | домино | 7 | гептамино |
| 3 | тримино | 8 | октамино |
| 4 | тетрамино | 9 | нонамино или эннеомино |
| 5 | пентамино | 10 | декамино |
История
Полимино использовались в занимательной математике по крайней мере с 1907 года[4][5], а известны были ещё в древности. Многие результаты с фигурами, содержащими от 1 до 6 квадратов, были впервые опубликованы в журнале «Fairy Chess Review» в период с 1937 по 1957 г., под названием «проблемы рассечения» (Шаблон:Lang-en). Название «полимино» или «полиомино» (Шаблон:Lang-en) было придумано Соломоном Голомбом[1] в 1953 году и затем популяризировано Мартином Гарднером[6][7].
В 1967 году журнал «Наука и жизнь» опубликовал серию статей о пентамино. В дальнейшем в течение ряда лет публиковались задачи, связанные с полимино и другими полиформами[8].
Обобщения полимино
В зависимости от того, разрешается ли переворачивание или вращение фигур, различаются следующие три вида полимино[1][2]:
- двусторонние полимино, или свободные полимино (Шаблон:Lang-en) — полимино, которые разрешается поворачивать и переворачивать;
- односторонние полимино (Шаблон:Lang-en) — полимино, которые разрешается поворачивать в плоскости, но не разрешается переворачивать;
- фиксированные полимино (Шаблон:Lang-en) — полимино, которые не разрешается ни поворачивать, ни переворачивать.
В зависимости от условий связности соседних ячеек различаются[1][9][10]:
- полимино — наборы квадратов, которые может обойти визирь[3];
- псевдополимино, или полиплеты — наборы квадратов, которые может обойти король;
- квазиполимино — произвольные наборы квадратов бесконечной шахматной доски.
В следующей таблице собраны данные о числе фигур полимино и его обобщений. Число квази-n-мино равно 1 при n = 1 и ∞ при n > 1.
Полиформы
Полиформы — обобщение полимино, ячейками которого могут быть любые одинаковые многоугольники или многогранники. Иначе говоря, полиформа — плоская фигура или пространственное тело, состоящая из нескольких соединённых копий заданной основной формы[11].
Плоские (двумерные) полиформы включают в себя полиамонды, сформированные из равносторонних треугольников; полигексы, сформированные из правильных шестиугольников; полиаболо, состоящие из равнобедренных прямоугольных треугольников, и другие.
Примеры пространственных (трёхмерных) полиформ: поликубы, состоящие из трёхмерных кубов; полироны (Шаблон:Lang-en), состоящие из ромбододекаэдров[12].
Полиформы также обобщаются на случай более высоких размерностей (например, сформированные из гиперкубов — полигиперкубы).
Задачи
Покрытия прямоугольников конгруэнтными полимино
Порядок полимино P — минимальное число конгруэнтных копий P, достаточное для того, чтобы сложить некоторый прямоугольник. Для полимино, из копий которых нельзя сложить ни одного прямоугольника, порядок не определён. Порядок полимино P равен 1 тогда и только тогда, когда P — прямоугольник[13].
Если существует хотя бы один прямоугольник, который можно покрыть нечётным числом конгруэнтных копий P, полимино P называется нечётным полимино; если же прямоугольник можно сложить только из чётного числа копий P, P называется чётным полимино.
Эта терминология была введена в 1968 году Шаблон:Нп5[1][14].
Существует множество полимино порядка 2; примером являются так называемые L-полимино[15]. Шаблон:Unsolved Полимино порядка Шаблон:Ч не существует; доказательство этого было опубликовано в 1992 году[16]. Любое полимино, из трёх копий которого можно составить прямоугольник, само является прямоугольником и имеет порядок 1. Неизвестно, существует ли полимино, порядок которого — нечётное число, большее 3[14].
Существуют полимино порядка Шаблон:Ч, Шаблон:Ч, Шаблон:Ч, Шаблон:Ч, Шаблон:Ч, Шаблон:Ч, Шаблон:Ч, Шаблон:Ч, Шаблон:Ч; существует конструкция, позволяющая получить полимино порядка 4s для любого натурального s[14]. Шаблон:Unsolved Кларнеру удалось найти непрямоугольное полимино порядка 2, из Шаблон:Ч копий которого можно составить прямоугольник[1][14][17], причём никакое ме́ньшее нечётное число копий этого полимино не может покрыть прямоугольник. Шаблон:На неизвестно, существует ли непрямоугольное полимино, из 9, 7 или 5 копий которого можно составить прямоугольник; неизвестны также какие-либо другие примеры полимино с минимальной нечётной кратностью покрытия 11 (кроме найденного Кларнером).
Минимальные области
Минимальная область (англ. minimal region, minimal common superform) для заданного набора полимино — полимино наименьшей возможной площади, содержащее каждое полимино из данного набора[1][14][18]. Задача нахождения минимальной области для набора двенадцати пентамино была впервые поставлена Шаблон:S в журнале Шаблон:Нп5 в 1942 году[18].
Для набора 12 пентамино существуют две минимальные девятиклеточные области, представляющие собой 2 из 1285 нонамино[1][14][18]:
### ### ##### ##### # #
См. также
Примечания
Литература
Ссылки
- Антология Мартина Гарднера Полимино Шаблон:Wayback
- Библиотека по математике Полимино Шаблон:Wayback
- RSDN: Этюды для программистов Количество полимино Шаблон:Wayback
- Хайдар Нурлигареев Паркеты из полимино Шаблон:Wayback
- Michael Reid Polyomino page Шаблон:Wayback
- Andrew Clarke The Poly Pages Polyominoes Шаблон:Wayback
- David Eppstein The Geometry Junkyard Polyominoes Шаблон:Wayback
- Miroslav Vicher Puzzles Pages Шаблон:Wayback
- Kevin L. Gong Polyominoes Шаблон:Wayback
- ↑ 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 1,8 1,9 Ошибка цитирования Неверный тег
<ref>; для сносокgolomb1975не указан текст - ↑ 2,0 2,1 Ошибка цитирования Неверный тег
<ref>; для сносокmw_polyominoне указан текст - ↑ 3,0 3,1 Популярное определение полимино с помощью шахматной ладьи не является строгим: существуют несвязные подмножества квадратного паркетажа, которые может обойти ладья (например, группа из четырёх полей шахматной доски a1, a8, h1, h8 не является тетрамино, хотя ладья, стоящая на одном из этих полей, может за три хода обойти три других поля). Более строгим было бы определение полимино с помощью фигуры «визирь», используемой в шахматах Тамерлана: визирь ходит лишь на одну клетку по горизонтали или вертикали.
- ↑ Ошибка цитирования Неверный тег
<ref>; для сносокcanterbury1979не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>; для сносокpuzzlezapper-pentcolне указан текст - ↑ Ошибка цитирования Неверный тег
<ref>; для сносокgardner_1971_12не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>; для сносокgardner_1974_7не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>; для сносокnkj1967не указан текст - ↑ Шаблон:Cite web
- ↑ Ошибка цитирования Неверный тег
<ref>; для сносокmw_polypletне указан текст - ↑ Ошибка цитирования Неверный тег
<ref>; для сносокmwpfне указан текст - ↑ Col. Sicherman’s Home Page. Polyform Curiosities Шаблон:Wayback. Catalogue of Polyrhons Шаблон:Wayback
- ↑ Ошибка цитирования Неверный тег
<ref>; для сносокeklhadне указан текст - ↑ 14,0 14,1 14,2 14,3 14,4 14,5 Ошибка цитирования Неверный тег
<ref>; для сносокgolomb1994не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>; для сносокmw_Lpolyне указан текст - ↑ Ошибка цитирования Неверный тег
<ref>; для сносокorder3_1992не указан текст - ↑ Ошибка цитирования Неверный тег
<ref>; для сносокreid_p6_rectне указан текст - ↑ 18,0 18,1 18,2 Ошибка цитирования Неверный тег
<ref>; для сносокpuzzlezapper-polycoverне указан текст
Шаблон:Выбор языка Шаблон:Полиформы
