Полимино

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Укладка 12 пентамино на шахматной доске 8×8 с вырезанным центральным квадратом 2×2
Полный набор 35 (двусторонних) гексамино. Если запретить переворачивать фигуры гексамино, полный набор будет состоять из 60 «односторонних» гексамино[1][2].

Полимино, или полиомино (англ. polyomino) — плоские геометрические фигуры, образованные путём соединения нескольких одноклеточных квадратов по их сторонам. Это полиформы, сегменты которых являются квадратами[1].

Фигуру полимино можно рассматривать как конечное связное подмножество бесконечной шахматной доски, которое может обойти ладья[1][3].

Названия полимино[править | править исходный текст]

Полимино (n-мино) носят названия по числу n квадратов, из которых они состоят:

n Название n Название
1 мономино 6 гексамино
2 домино 7 гептамино
3 тримино 8 октамино
4 тетрамино 9 нонамино или эннеомино
5 пентамино 10 декамино

История[править | править исходный текст]

Полимино использовались в занимательной математике по крайней мере с 1907 года[4], а известны были ещё в древности. Многие результаты с фигурами, содержащими от 1 до 6 квадратов, были впервые опубликованы в журнале «Fairy Chess Review» в период с 1937 по 1957 г., под названием «проблемы рассечения» (англ. «dissection problems»). Название «полимино» или «полиомино» (англ. polyomino) было придумано Соломоном Голомбом[1] в 1953 году и затем популяризировано Мартином Гарднером[5][6].

В 1967 году журнал «Наука и жизнь» опубликовал серию статей о пентамино. В дальнейшем в течение ряда лет публиковались задачи, связанные с полимино и другими полиформами[7].

Обобщения полимино[править | править исходный текст]

Укладка всех 94 двусторонних псевдопентамино

В зависимости от того, разрешается ли переворачивание или вращение фигур, различаются следующие три вида полимино[1][2]:

  • двусторонние полимино, или свободные полимино (англ. free polyominoes) — полимино, которые разрешается поворачивать и переворачивать;
  • односторонние полимино (англ. one-sided polyominoes) — полимино, которые разрешается поворачивать в плоскости, но не разрешается переворачивать;
  • фиксированные полимино (англ. fixed polyominoes) — полимино, которые не разрешается ни поворачивать, ни переворачивать.

В зависимости от условий связности соседних ячеек различаются[1][8][9]:

  • полимино — наборы квадратов, которые может обойти визирь[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 3 832
7 108 1 107 196 760 3 031 5 931 23 592
8 369 6 363 704 2 725 18 770 37 196 147 941
9 1 285 37 1 248 2 500 9 910 118 133 235 456 940 982
10 4 655 195 4 460 9 189 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

Полиформы[править | править исходный текст]

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

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

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

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

Порядок полимино[править | править исходный текст]

L–полимино, являющиеся полимино порядка 2

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

Термин был предложен в 1968 году Д. А. Клэрнером[13]. Существует множество полимино порядка 2; примером являются так называемые L–полимино[14].

Полимино порядка 3 не существует; доказательство этого было опубликовано в 1992 году[15]. Любое полимино, из трёх копий которого можно составить прямоугольник, само является прямоугольником и имеет порядок 1[13].

Существуют также полимино порядка 4, 10, 18, 24, 28, 50, 76, 92, 312; существует конструкция, позволяющая получить полимино порядка 4s для любого натурального s[13].

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. 1 2 3 4 5 6 Голомб С. В. Полимино, 1975
  2. 1 2 Weisstein, Eric W. Polyomino (англ.) на сайте Wolfram MathWorld.
  3. 1 2 Популярное определение полимино с помощью шахматной ладьи не является строгим: существуют несвязные подмножества квадратного паркетажа, которые может обойти ладья (например, группа из четырёх полей шахматной доски a1, a8, h1, h8 не является тетрамино, хотя ладья, стоящая на одном из этих полей, может за три хода обойти три других поля). Более строгим было бы определение полимино с помощью фигуры «визирь», используемой в шахматах Тамерлана: визирь ходит лишь на одну клетку по горизонтали или вертикали.
  4. Генри Э. Дьюдени. Кентерберийские головоломки, 1975, стр. 111–113
  5. Гарднер М. Математические головоломки и развлечения, 1971. — Глава 12. Полиомино. — с.111—124
  6. Гарднер М. Математические новеллы, 1974. — Глава 7. Пентамино и полиомино: пять игр и серия задач. — с.81—95
  7. Наука и жизнь №№ 2—12 (1967), 1, 6, 9, 11 (1968) и др.
  8. Polyforms
  9. Weisstein, Eric W. Polyplet (англ.) на сайте Wolfram MathWorld.
  10. Weisstein, Eric W. Polyform (англ.) на сайте Wolfram MathWorld.
  11. Col. Sicherman's Home Page. Polyform Curiosities. Catalogue of Polyrhons
  12. Karl Dahlke. Tiling Rectangles With Polyominoes.
  13. 1 2 3 Голомб С. В. Polyominoes: Puzzles, Patterns, Problems, and Packings. — 2nd ed.. — Princeton University Press, 1994. — ISBN 0-691-08573-0
  14. Weisstein, Eric W. L-Polyomino (англ.) на сайте Wolfram MathWorld.
  15. I. N. Stewart, A. Wormstein (9 1992). «Polyominoes of Order 3 Do Not Exist». Journal of Combinatorial Theory, Series A 61 (1): 130-136. Проверено 2013-08-25.

Литература[править | править исходный текст]

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

Ссылки[править | править исходный текст]