Полимино, или полиомино () — плоские геометрические фигуры, образованные путём соединения нескольких одноклеточных квадратов по их сторонам. Это полиформы, сегменты которых являются квадратами.
Фигуру полимино можно рассматривать как конечное связное подмножество бесконечной шахматной доски, которое может обойти ладьяПопулярное определение полимино с помощью шахматной ладьи не является строгим: существуют несвязные подмножества квадратного паркетажа, которые может обойти ладья (например, группа из четырёх полей шахматной доски a1, a8, h1, h8 не является тетрамино, хотя ладья, стоящая на одном из этих полей, может за три хода обойти три других поля). Более строгим было бы определение полимино с помощью фигуры «визирь», используемой в шахматах Тамерлана: визирь ходит лишь на одну клетку по горизонтали или вертикали..
Названия полимино Полимино (n-мино) носят названия по числу n квадратов, из которых они состоят: nНазваниеnНазвание1 мономино 6 гексамино2 домино 7 гептамино3 тримино 8 октамино4 тетрамино 9 нонамино5 пентамино 10 декамино
История Полимино использовались в занимательной математике по крайней мере с 1907 года, а известны были ещё в древности. Многие результаты с фигурами, содержащими от 1 до 6 квадратов, были впервые опубликованы в журнале «Fairy Chess Review» в период с 1937 по 1957 г., под названием «проблемы рассечения» (). Название «полимино» или «полиомино» () было придумано Соломоном Голомбом в 1953 году и затем популяризировано Мартином Гарднером.
В 1967 году журнал «Наука и жизнь» опубликовал серию статей о пентамино. В дальнейшем в течение ряда лет публиковались задачи, связанные с полимино и другими полиформами.
Обобщения полимино
В зависимости от того, разрешается ли переворачивание или вращение фигур, различаются следующие три вида полимино: двусторонние полимино, или свободные полимино () — полимино, которые разрешается поворачивать и переворачивать; односторонние полимино () — полимино, которые разрешается поворачивать в плоскости, но не разрешается переворачивать; фиксированные полимино () — полимино, которые не разрешается ни поворачивать, ни переворачивать.
В зависимости от условий связности соседних ячеек различаются: полимино — наборы квадратов, которые может обойти визирь; псевдополимино, или полиплеты — наборы квадратов, которые может обойти король; квазиполимино — произвольные наборы квадратов бесконечной шахматной доски.
В следующей таблице собраны данные о числе фигур полимино и его обобщений. Число квази-n-мино равно 1 при n = 1 и ∞ при n > 1.
n полимино псевдополиминодвусторонние односторонние фиксированные двусторонние односторонние фиксированныевсе с отверстиями без отверстий 1 1 0 1 1 1 1 1 12 0 1 1 2 2 2 3 0 2 2 4 0 5 0 6 0 7 1 23 5928 18 770 37 196 147 9419 118 133 235 456 940 98210 36 446 758 381 1 514 618 6 053 18011 17 073 16 094 33 896 135 268 4 915 652 9 826 177 39 299 40812 63 600 4 663 58 937 126 759 505 861 32 149 296 64 284 947 257 105 146
Полиформы
Полиформы — обобщение полимино, ячейками которого могут быть любые одинаковые многоугольники или многогранники. Иначе говоря, полиформа — плоская фигура или пространственное тело, состоящая из нескольких соединённых копий заданной основной формы.
Плоские (двумерные) полиформы включают в себя полиамонды, сформированные из равносторонних треугольников; полигексы, сформированные из правильных шестиугольников; полиаболо, состоящие из равнобедренных прямоугольных треугольников, и другие.
Примеры пространственных (трёхмерных) полиформ: поликубы, состоящие из трёхмерных кубов; полироны (), состоящие из ромбододекаэдровCol. Sicherman’s Home Page. Polyform Curiosities . Catalogue of Polyrhons .
Полиформы также обобщаются на случай более высоких размерностей, сформированные из гиперкубов — полигиперкубы.
Задачи
Покрытия прямоугольников конгруэнтными полимино
Порядок полимино P — минимальное число конгруэнтных копий P, достаточное для того, чтобы сложить некоторый прямоугольник. Для полимино, из копий которых нельзя сложить ни одного прямоугольника, порядок не определён. Порядок полимино P равен 1 тогда и только тогда, когда P — прямоугольник.
Если существует хотя бы один прямоугольник, который можно покрыть нечётным числом конгруэнтных копий P, полимино P называется нечётным полимино; если же прямоугольник можно сложить только из чётного числа копий P, P называется чётным полимино.
Эта терминология была введена в 1968 году .
Существует множество полимино порядка 2; примером являются так называемые L-полимино.
Полимино порядка не существует; доказательство этого было опубликовано в 1992 году. Любое полимино, из трёх копий которого можно составить прямоугольник, само является прямоугольником и имеет порядок 1. Неизвестно, существует ли полимино, порядок которого — нечётное число, большее 3.
Существуют полимино порядка , , , , , , , , ; существует конструкция, позволяющая получить полимино порядка 4s для любого натурального s.
Кларнеру удалось найти непрямоугольное полимино порядка 2, из копий которого можно составить прямоугольник, причём никакое ме́ньшее нечётное число копий этого полимино не может покрыть прямоугольник. неизвестно, существует ли непрямоугольное полимино, из 9, 7 или 5 копий которого можно составить прямоугольник; неизвестны также какие-либо другие примеры полимино с минимальной нечётной кратностью покрытия 11 (кроме найденного Кларнером).
Минимальные области Минимальная область (англ. minimal region, minimal common superform) для заданного набора полимино — полимино наименьшей возможной площади, содержащее каждое полимино из данного набора. Задача нахождения минимальной области для набора двенадцати пентамино была впервые поставлена в журнале в 1942 году.
Для набора 12 пентамино существуют две минимальные девятиклеточные области, представляющие собой 2 из 1285 нонамино:
См. также
Пентамино Полиамонды Полигексы Полиаболо Кубики сома Танграм
Примечания
Литература
Ссылки Антология Мартина Гарднера Полимино Библиотека по математике Полимино RSDN: Этюды для программистов Количество полимино Хайдар Нурлигареев Паркеты из полимино Michael Reid Polyomino page Andrew Clarke The Poly Pages Polyominoes David Eppstein The Geometry Junkyard Polyominoes Miroslav Vicher Puzzles Pages Kevin L. Gong Polyominoes
Категория:Головоломки Категория:Математические игры Мино