PROFILPELAJAR.COM

Полный набор 35 (двусторонних) гексамино. Если запретить переворачивать фигуры гексамино, полный набор будет состоять из 60 «односторонних» гексамино^[1]^[2].

Полимино, или полиомино (англ. polyomino) — плоские геометрические фигуры, образованные путём соединения нескольких одноклеточных квадратов по их сторонам. Это полиформы, сегменты которых являются квадратами^[1].

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

Названия полимино

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

n	Название	n	Название
1	мономино	6	гексамино
2	домино	7	гептамино
3	тримино	8	октамино
4	тетрамино	9	нонамино
5	пентамино	10	декамино

История

Полимино использовались в занимательной математике по крайней мере с 1907 года^[4]^[5], а известны были ещё в древности. Многие результаты с фигурами, содержащими от 1 до 6 квадратов, были впервые опубликованы в журнале «Fairy Chess Review» в период с 1937 по 1957 г., под названием «проблемы рассечения» (англ. «dissection problems»). Название «полимино» или «полиомино» (англ. polyomino) было придумано Соломоном Голомбом^[1] в 1953 году и затем популяризировано Мартином Гарднером^[6]^[7].

В 1967 году журнал «Наука и жизнь» опубликовал серию статей о пентамино. В дальнейшем в течение ряда лет публиковались задачи, связанные с полимино и другими полиформами^[8].

Обобщения полимино

Укладка всех 94 двусторонних псевдопентамино

В зависимости от того, разрешается ли переворачивание или вращение фигур, различаются следующие три вида полимино^[1]^[2]:

двусторонние полимино, или свободные полимино (англ. free polyominoes) — полимино, которые разрешается поворачивать и переворачивать;
односторонние полимино (англ. one-sided polyominoes) — полимино, которые разрешается поворачивать в плоскости, но не разрешается переворачивать;
фиксированные полимино (англ. fixed polyominoes) — полимино, которые не разрешается ни поворачивать, ни переворачивать.

В зависимости от условий связности соседних ячеек различаются^[1]^[9]^[10]:

полимино — наборы квадратов, которые может обойти визирь^[3];
псевдополимино, или полиплеты — наборы квадратов, которые может обойти король;
квазиполимино — произвольные наборы квадратов бесконечной шахматной доски.

В следующей таблице собраны данные о числе фигур полимино и его обобщений. Число квази-n-мино равно 1 при n = 1 и ∞ при n > 1.

n	полимино					псевдополимино
	двусторонние			односторонние	фиксированные	двусторонние	односторонние	фиксированные
	все	с отверстиями	без отверстий	односторонние	фиксированные	двусторонние	односторонние	фиксированные
	A000105	A001419	A000104	A000988	A001168	A030222	A030233	A006770
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	3832
7	108	1	107	196	760	3031	5931	23 592
8	369	6	363	704	2725	18 770	37 196	147 941
9	1285	37	1248	2500	9910	118 133	235 456	940 982
10	4655	195	4460	9189	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

Полиформы

Полиформы — обобщение полимино, ячейками которого могут быть любые одинаковые многоугольники или многогранники. Иначе говоря, полиформа — плоская фигура или пространственное тело, состоящая из нескольких соединённых копий заданной основной формы^[11].

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

Примеры пространственных (трёхмерных) полиформ: поликубы, состоящие из трёхмерных кубов; полироны (англ. polyrhons), состоящие из ромбододекаэдров^[12].

Полиформы также обобщаются на случай более высоких размерностей, сформированные из гиперкубов — полигиперкубы.

Задачи

Покрытия прямоугольников конгруэнтными полимино

L-полимино, являющиеся полимино порядка 2

Порядок полимино P — минимальное число конгруэнтных копий P, достаточное для того, чтобы сложить некоторый прямоугольник. Для полимино, из копий которых нельзя сложить ни одного прямоугольника, порядок не определён. Порядок полимино P равен 1 тогда и только тогда, когда P — прямоугольник^[13].

Если существует хотя бы один прямоугольник, который можно покрыть нечётным числом конгруэнтных копий P, полимино P называется нечётным полимино; если же прямоугольник можно сложить только из чётного числа копий P, P называется чётным полимино.

Обнаруженное Кларнером гексамино порядка 2, допускающее покрытие прямоугольника с нечётной кратностью 11.

Эта терминология была введена в 1968 году Д. А. Кларнером^[англ.]^[1]^[14].

Существует множество полимино порядка 2; примером являются так называемые L-полимино^[15].

Нерешённые проблемы математики: Существует ли полимино, порядок которого — нечётное число?

Полимино порядка 3 не существует; доказательство этого было опубликовано в 1992 году^[16]. Любое полимино, из трёх копий которого можно составить прямоугольник, само является прямоугольником и имеет порядок 1. Неизвестно, существует ли полимино, порядок которого — нечётное число, большее 3^[14].

Существуют полимино порядка 4, 10, 18, 24, 28, 50, 76, 92, 312; существует конструкция, позволяющая получить полимино порядка 4s для любого натурального s^[14].

Нерешённые проблемы математики: Какова наименьшая возможная нечётная кратность покрытия прямоугольника непрямоугольным полимино?

Кларнеру удалось найти непрямоугольное полимино порядка 2, из 11 копий которого можно составить прямоугольник^[1]^[14]^[17], причём никакое ме́ньшее нечётное число копий этого полимино не может покрыть прямоугольник. На октябрь 2015 года неизвестно, существует ли непрямоугольное полимино, из 9, 7 или 5 копий которого можно составить прямоугольник; неизвестны также какие-либо другие примеры полимино с минимальной нечётной кратностью покрытия 11 (кроме найденного Кларнером).

Минимальные области

Минимальная область (англ. minimal region, minimal common superform) для заданного набора полимино — полимино наименьшей возможной площади, содержащее каждое полимино из данного набора^[1]^[14]^[18]. Задача нахождения минимальной области для набора двенадцати пентамино была впервые поставлена Т. Р. Доусоном в журнале Fairy Chess Review^[англ.] в 1942 году^[18].

Для набора 12 пентамино существуют две минимальные девятиклеточные области, представляющие собой 2 из 1285 нонамино^[1]^[14]^[18]:

  ###     ###
#####    #####
  #       #

См. также

Примечания

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ Голомб С. В. Полимино, 1975
↑ ¹ ² Weisstein, Eric W. Polyomino (англ.) на сайте Wolfram MathWorld.
↑ ¹ ² Популярное определение полимино с помощью шахматной ладьи не является строгим: существуют несвязные подмножества квадратного паркетажа, которые может обойти ладья (например, группа из четырёх полей шахматной доски a1, a8, h1, h8 не является тетрамино, хотя ладья, стоящая на одном из этих полей, может за три хода обойти три других поля). Более строгим было бы определение полимино с помощью фигуры «визирь», используемой в шахматах Тамерлана: визирь ходит лишь на одну клетку по горизонтали или вертикали.
↑ Генри Э. Дьюдени. Кентерберийские головоломки, 1975, стр. 111–113
↑ Alexandre Owen Muñiz. Some Nice Pentomino Coloring Problems (неопр.). Дата обращения: 24 октября 2015. Архивировано 4 марта 2016 года.
↑ Гарднер М. Математические головоломки и развлечения, 1971. — Глава 12. Полиомино. — с.111—124
↑ Гарднер М. Математические новеллы, 1974. — Глава 7. Пентамино и полиомино: пять игр и серия задач. — с.81—95
↑ Наука и жизнь №№ 2—12 (1967), 1, 6, 9, 11 (1968) и др.
↑ Polyforms (неопр.). Дата обращения: 22 августа 2013. Архивировано 11 сентября 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 (неопр.). Дата обращения: 25 августа 2013. Архивировано 15 февраля 2020 года.
↑ ¹ ² ³ ⁴ ⁵ ⁶ Голомб С. В. 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. Polyominoes of Order 3 Do Not Exist (англ.) // Journal of Combinatorial Theory, Series A : journal. — 1992. — September (vol. 61, no. 1). — P. 130—136.
↑ Michael Reid. Primes of the P hexomino (неопр.). Дата обращения: 24 октября 2015. Архивировано 22 марта 2016 года.
↑ ¹ ² ³ Alexandre Owen Muñiz. Polyomino Common Superforms (неопр.). Дата обращения: 24 октября 2015. Архивировано 21 мая 2017 года.

Литература

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

Ссылки

Антология Мартина Гарднера Полимино Архивная копия от 31 января 2014 на Wayback Machine
Библиотека по математике Полимино Архивная копия от 9 ноября 2014 на Wayback Machine
RSDN: Этюды для программистов Количество полимино Архивная копия от 10 ноября 2014 на Wayback Machine
Хайдар Нурлигареев Паркеты из полимино Архивная копия от 5 октября 2015 на Wayback Machine
Michael Reid Polyomino page Архивная копия от 25 декабря 2018 на Wayback Machine
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

[golomb1975-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ Голомб С. В. Полимино, 1975

[mw_polyomino-2] ¹ ² Weisstein, Eric W. Polyomino (англ.) на сайте Wolfram MathWorld.

[note_wazir-3] ¹ ² Популярное определение полимино с помощью шахматной ладьи не является строгим: существуют несвязные подмножества квадратного паркетажа, которые может обойти ладья (например, группа из четырёх полей шахматной доски a1, a8, h1, h8 не является тетрамино, хотя ладья, стоящая на одном из этих полей, может за три хода обойти три других поля). Более строгим было бы определение полимино с помощью фигуры «визирь», используемой в шахматах Тамерлана: визирь ходит лишь на одну клетку по горизонтали или вертикали.

[canterbury1979-4] Генри Э. Дьюдени. Кентерберийские головоломки, 1975, стр. 111–113

[puzzlezapper-pentcol-5] Alexandre Owen Muñiz. Some Nice Pentomino Coloring Problems (неопр.). Дата обращения: 24 октября 2015. Архивировано 4 марта 2016 года.

[gardner_1971_12-6] Гарднер М. Математические головоломки и развлечения, 1971. — Глава 12. Полиомино. — с.111—124

[gardner_1974_7-7] Гарднер М. Математические новеллы, 1974. — Глава 7. Пентамино и полиомино: пять игр и серия задач. — с.81—95

[nkj1967-8] Наука и жизнь №№ 2—12 (1967), 1, 6, 9, 11 (1968) и др.

[9] Polyforms (неопр.). Дата обращения: 22 августа 2013. Архивировано 11 сентября 2015 года.

[mw_polyplet-10] Weisstein, Eric W. Polyplet (англ.) на сайте Wolfram MathWorld.

[mwpf-11] Weisstein, Eric W. Polyform (англ.) на сайте Wolfram MathWorld.

[12] Col. Sicherman’s Home Page. Polyform Curiosities Архивная копия от 14 декабря 2014 на Wayback Machine. Catalogue of Polyrhons Архивная копия от 11 сентября 2015 на Wayback Machine

[eklhad-13] Karl Dahlke. Tiling Rectangles With Polyominoes (неопр.). Дата обращения: 25 августа 2013. Архивировано 15 февраля 2020 года.

[golomb1994-14] ¹ ² ³ ⁴ ⁵ ⁶ Голомб С. В. Polyominoes: Puzzles, Patterns, Problems, and Packings (англ.). — 2nd ed.. — Princeton University Press, 1994. — ISBN 0-691-08573-0.

[mw_Lpoly-15] Weisstein, Eric W. L-Polyomino (англ.) на сайте Wolfram MathWorld.

[order3_1992-16] I. N. Stewart, A. Wormstein. Polyominoes of Order 3 Do Not Exist (англ.) // Journal of Combinatorial Theory, Series A : journal. — 1992. — September (vol. 61, no. 1). — P. 130—136.

[reid_p6_rect-17] Michael Reid. Primes of the P hexomino (неопр.). Дата обращения: 24 октября 2015. Архивировано 22 марта 2016 года.

[puzzlezapper-polycover-18] ¹ ² ³ Alexandre Owen Muñiz. Polyomino Common Superforms (неопр.). Дата обращения: 24 октября 2015. Архивировано 21 мая 2017 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

PROFILPELAJAR.COM

Полимино

Содержание

Названия полимино

История

Обобщения полимино

Полиформы

Задачи

Покрытия прямоугольников конгруэнтными полимино

Минимальные области

См. также

Примечания

Литература

Ссылки

Read other articles:

Pembunuhan XXXTentacion

OneShot

Gempa bumi Asia Selatan 2022

Pegunungan Taebaek

Titi Kuning, Medan Johor, Medan

Bank Investasi Infrastruktur Asia

العلاقات الألمانية الجزائرية

Enzo Biagi

Mayapan

Pepsi

Révolution de Mars

Fiat Pulse

Juglans nigra

Jewel of Vicenza

Communist (Maoist) Party of Afghanistan

Talakag, Bukidnon

Jeff Smith (boxe anglaise)

ウエストワン

Ersilia Salvato

JW Marriott Panama