Вікіпедія

Поліміно

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

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

Фігуру поліміно можна розглядати як скінченну зв'язну підмножину нескінченної шахівниці, яку може обійти тура[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], що складаються з рівнобедрених прямокутних трикутників, та інші.

Приклади просторових (тривимірних) поліформ: полікуби, що складаються з тривимірних кубів; полірони (англ. 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. Архів оригіналу за 11 вересня 2015. Процитовано 1 травня 2015.
  9. ↑ Weisstein, Eric W. Polyplet(англ.) на сайті Wolfram MathWorld.
  10. ↑ Weisstein, Eric W. Polyform(англ.) на сайті Wolfram MathWorld.
  11. ↑ Col. Sicherman's Home Page. Polyform Curiosities [Архівовано 14 грудня 2014 у Wayback Machine.]. Catalogue of Polyrhons [Архівовано 11 вересня 2015 у Wayback Machine.]
  12. ↑ Karl Dahlke. Tiling Rectangles With Polyominoes. Архів оригіналу за 15 лютого 2020. Процитовано 1 травня 2015.
  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.

Посилання ред.

Отримано з https://uk.wikipedia.org/w/index.php?title=Поліміно&oldid=36677574