Полимино

Полимино, или полиомино (англ. 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.

Полиформы

Полиформы — обобщение полимино, ячейками которого могут быть любые одинаковые многоугольники или многогранники. Иначе говоря, полиформа — плоская фигура или пространственное тело, состоящая из нескольких соединённых копий заданной основной формы^[11].

Плоские (двумерные) полиформы включают в себя полиамонды, сформированные из равносторонних треугольников; полигексы, сформированные из правильных шестиугольников; полиаболо, состоящие из равнобедренных прямоугольных треугольников, и другие.

Примеры пространственных (трёхмерных) полиформ: поликубы, состоящие из трёхмерных кубов; полироны (англ. polyrhons), состоящие из ромбододекаэдров^[12].

Полиформы также обобщаются на случай более высоких размерностей (например, сформированные из гиперкубов — полигиперкубы).

Задачи

Покрытия прямоугольников конгруэнтными полимино

Порядок полимино P — минимальное число конгруэнтных копий P, достаточное для того, чтобы сложить некоторый прямоугольник. Для полимино, из копий которых нельзя сложить ни одного прямоугольника, порядок не определён. Порядок полимино P равен 1 тогда и только тогда, когда P — прямоугольник^[13].

Если существует хотя бы один прямоугольник, который можно покрыть нечётным числом конгруэнтных копий P, полимино P называется нечётным полимино; если же прямоугольник можно сложить только из чётного числа копий P, P называется чётным полимино.

Эта терминология была введена в 1968 году Д. А. Кларнером^[en][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^[en] в 1942 году^[18].

Для набора 12 пентамино существуют две минимальные девятиклеточные области, представляющие собой 2 из 1285 нонамино^[1][14][18]:

  ###     ###
#####    #####
  #       #

См. также

• Пентамино
• Полиамонды
• Полигексы
• Полиаболо
• Кубики сома
• Танграм

Примечания

Литература

• Голомб С.В. Полимино = Polyominoes / Пер. с англ. В. Фирсова. Предисл. и ред. И. Яглома. — М.: Мир, 1975. — 207 с.
• Генри Э. Дьюдени. Кентерберийские головоломки = The Canterbury Puzzles and Other Curious Problems / Пер. с англ. Ю.Н.Сударева. — М.: Мир, 1979. — 353 с.
• Гарднер М. Математические головоломки и развлечения = Mathematical Puzzles and Diversions / Пер. с англ. Ю.А.Данилова. — М.: Мир, 1971. — 511 с.
• Гарднер М. Математические новеллы / Пер. с англ. Ю.А.Данилова. Под ред. Я.А.Смородинского. — М.: Мир, 1974. — 456 с.

Ссылки

• Антология Мартина Гарднера Полимино Архивная копия от 31 января 2014 на Wayback Machine
• Библиотека по математике Полимино Архивная копия от 9 ноября 2014 на Wayback Machine
• RSDN: Этюды для программистов Количество полимино Архивная копия от 10 ноября 2014 на Wayback Machine
• Хайдар Нурлигареев Паркеты из полимино Архивная копия от 5 октября 2015 на Wayback Machine
• Michael Reid Polyomino page Архивная копия от 25 декабря 2018 на Wayback Machine
• Andrew Clarke The Poly Pages Polyominoes Архивная копия от 14 мая 2015 на Wayback Machine
• David Eppstein The Geometry Junkyard Polyominoes Архивная копия от 3 июля 2015 на Wayback Machine
• Miroslav Vicher Puzzles Pages Архивная копия от 15 октября 2015 на Wayback Machine
• Kevin L. Gong Polyominoes Архивная копия от 3 мая 2015 на Wayback Machine

Эта страница в последний раз была отредактирована 3 апреля 2022 в 16:31.