Поліміно

Поліміно, або поліоміно (англ. 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.

Посилання

• Антология Мартина Гарднера Полимино [Архівовано 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.]