Полимино

Полимино (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 году Д. А. Кларнером^[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]:

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