Поліміно

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

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

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

Назва поліміно[ред. | ред. код]

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

n Назва n Назва
1 мономіно 6 гексаміно[ru]
2 доміно 7 гептаміно[ru]
3 триміно[ru] 8 октаміно[ru]
4 тетраміно 9 нонаміно[en] або еннеоміно
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
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].

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

Приклади просторових (тривимірних) поліформ: полікуби, що складаються з тривимірних кубів; полірони (англ. 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. Процитовано 2013-08-25. 

Література[ред. | ред. код]

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

Посилання[ред. | ред. код]