Поліміно

Поліміно, або поліоміно (англ. polyomino) — плоскі геометричні фігури, утворені шляхом з'єднання декількох одноклітинних квадратів по їх сторонам. Це поліформи, сегменти яких є квадратами[1].

Укладка 12 пентаміно на шаховій дошці 8×8 з вирізаним центральним квадратом 2×2
Повний набір 35 (двосторонніх) гексаміно. Якщо заборонити перевертати фігури гексаміно, повний набір буде складатися з 60 «односторонніх» гексаміно[1][2].

Фігуру поліміно можна розглядати як скінченну зв'язну підмножину нескінченної шахівниці, яку може обійти тура[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 з Онлайн енциклопедії послідовностей цілих чисел, OEISпослідовність A001419 з Онлайн енциклопедії послідовностей цілих чисел, OEISпослідовність A000104 з Онлайн енциклопедії послідовностей цілих чисел, OEISпослідовність A000988 з Онлайн енциклопедії послідовностей цілих чисел, OEISпослідовність A001168 з Онлайн енциклопедії послідовностей цілих чисел, OEISпослідовність A030222 з Онлайн енциклопедії послідовностей цілих чисел, OEISпослідовність A030233 з Онлайн енциклопедії послідовностей цілих чисел, OEISпослідовність A006770 з Онлайн енциклопедії послідовностей цілих чисел, OEIS
110111111
210112224
3202265620
45057192234110
512012186394166638
635035602165249913 832
710811071967603 0315 93123 592
836963637042 72518 77037 196147 941
91 285371 2482 5009 910118 133235 456940 982
104 6551954 4609 18936 446758 3811 514 6186 053 180
1117 07397916 09433 896135 2684 915 6529 826 17739 299 408
1263 6004 66358 937126 759505 86132 149 29664 284 947257 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. Голомб С. В. Полимино, 1975
  2. Weisstein, Eric W. Polyomino(англ.) на сайті Wolfram MathWorld.
  3. Популярне визначення поліміно за допомогою шахової тури не є строгим: існують незв'язні підмножини квадратного паркету, які може обійти тура (наприклад, група з чотирьох полів шахової дошки 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. Голомб С. В. 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. Процитовано 25 серпня 2013.

Література
  • Голомб С.В. Полимино / Пер. с англ. В. Фирсова. Предисл. и ред. И. Яглома. — М. : Мир, 1975. — С. 207.
  • Генри Э. Дьюдени. Кентерберийские головоломки / Пер. с англ. Ю.Н.Сударева. — М. : Мир, 1979. — С. 353.
  • Гарднер М. Математические головоломки и развлечения / Пер. с англ. Ю.А.Данилова. — М. : Мир, 1971. — С. 511.
  • Гарднер М. Математические новеллы / Пер. с англ. Ю.А.Данилова. Под ред. Я.А.Смородинского. — М. : Мир, 1974. — С. 456.

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.