Поліміно, або поліоміно (англ. 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].
Узагальнення поліміно
Залежно від того, чи дозволяється перевертання або обертання фігур, відрізняються такі три види поліміно[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].
Поліформи також узагальнюються на випадок більш високих розмірностей (наприклад, сформовані з гіперкубів — полігіперкуби).
Порядок поліміно
Порядок поліміно 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].
Див. також
Примітки
- ↑ а б в г д е Голомб С. В. Полимино, 1975
- ↑ а б Weisstein, Eric W. Polyomino(англ.) на сайті Wolfram MathWorld.
- ↑ а б Популярне визначення поліміно за допомогою шахової тури не є строгим: існують незв'язні підмножини квадратного паркету, які може обійти тура (наприклад, група з чотирьох полів шахової дошки a1, a8, h1, h8 не є тетраміно, хоча тура, що стоїть на одному з цих полів, може за три ходи обійти три інших поля). Більш строгим було б визначення поліміно за допомогою фігури «візир», використовуваної в шахах Тамерлана: візир ходить лише на одну клітку по горизонталі або вертикалі.
- ↑ Генри Э. Дьюдени. Кентерберийские головоломки, 1975, стр. 111–113
- ↑ Гарднер М. Математические головоломки и развлечения, 1971. — Глава 12. Полиомино. — с.111—124
- ↑ Гарднер М. Математические новеллы, 1974. — Глава 7. Пентамино и полиомино: пять игр и серия задач. — с. 81—95
- ↑ Наука и жизнь № 2—12 (1967), 1, 6, 9, 11 (1968) и др.
- ↑ Polyforms. Архів оригіналу за 11 вересня 2015. Процитовано 1 травня 2015.
- ↑ Weisstein, Eric W. Polyplet(англ.) на сайті Wolfram MathWorld.
- ↑ Weisstein, Eric W. Polyform(англ.) на сайті Wolfram MathWorld.
- ↑ Col. Sicherman's Home Page. Polyform Curiosities [Архівовано 14 грудня 2014 у Wayback Machine.]. Catalogue of Polyrhons [Архівовано 11 вересня 2015 у Wayback Machine.]
- ↑ Karl Dahlke. Tiling Rectangles With Polyominoes. Архів оригіналу за 15 лютого 2020. Процитовано 1 травня 2015.
- ↑ а б в Голомб С. В. Polyominoes: Puzzles, Patterns, Problems, and Packings. — 2nd ed. — Princeton University Press, 1994. — ISBN 0-691-08573-0.
- ↑ Weisstein, Eric W. L-Polyomino(англ.) на сайті Wolfram MathWorld.
- ↑ 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.
Посилання
- Антология Мартина Гарднера Полимино [Архівовано 31 січня 2014 у Wayback Machine.]
- Библиотека по математике Полимино [Архівовано 9 листопада 2014 у Wayback Machine.]
- RSDN: Этюды для программистов Количество полимино [Архівовано 10 листопада 2014 у Wayback Machine.]
- Michael Reid Polyomino page
- Andrew Clarke The Poly Pages Polyominoes [Архівовано 14 травня 2015 у Wayback Machine.]
- David Eppstein The Geometry Junkyard Polyominoes [Архівовано 3 липня 2015 у Wayback Machine.]
- Miroslav Vicher Puzzles Pages [Архівовано 15 жовтня 2015 у Wayback Machine.]
- Kevin L. Gong Polyominoes [Архівовано 3 травня 2015 у Wayback Machine.]