Поліміно

Укладка 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], що складаються з рівнобедрених прямокутних трикутників, та інші.

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

Див. також

Поліміно
у сестринських Вікіпроєктах
CMNS: Файли у Вікісховищі?

Примітки

  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.

Посилання

Read other articles:

Auguste-René-Marie Dubourg

His EminenceAuguste-René-Marie DubourgUskup Agung RennesGerejaGereja Katolik RomaKeuskupan agungRennesTakhtaRennesPenunjukan6 Agustus 1906Masa jabatan berakhir22 September 1921PendahuluJoseph-Guillaume LabouréPenerusAlexis-Armand CharostJabatan lainKardinal-Imam Santa Balbina (1916-21)ImamatTahbisan imam22 Desember 1866Tahbisan uskup16 April 1893oleh Pierre-Marie-Frédéric FallièresPelantikan kardinal4 Desember 1916oleh Paus Benediktus XVPeringkatKardinal-ImamInformasi pribadiNama la...

 

Walker Art Center

Cet article est une ébauche concernant un musée, l’art et le Minnesota. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Walker Art CenterLe Walker Art Center.Informations généralesType Musée d'art, galerie d'art, salle de cinémaOuverture 1927Site web www.walkerart.orgBâtimentArchitecte Edward Larrabee Barnes (en)LocalisationPays  États-UnisDivision administrative MinnesotaCommune MinneapolisCoordo...

 

Kuntilanak Beranak

Artikel ini hampir seluruhnya merupakan ringkasan alur. Artikel ini harus diperluas untuk menyediakan cakupan konteks dunia nyata yang lebih seimbang. Please edit the article to focus on discussing the work rather than merely reiterating the plot. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Kuntilanak BeranakSutradaraIan JacobsProduserZainal SusantoDitulis olehInne DamarPemeranGarneta HaruniMonique HenryDion WiyokoVikri RastaIsmi MelindaDistributorMitra PicturesTanggal...

Pembagian oleh singa

Pembagian oleh singa adalah sebuah ekspresi idiomatik yang merujuk kepada pembagian besar terhadap sesuatu. Peribahasa tersebut berasal dari alur sejumlah fabel-fabel yang dikaitkan dengan Aesop dan dipakai disini sebagai judul generik. Terdapat dua jenis cerita utama, yang timbul dalam beberapa versi berbeda. Fabel-fabel lainnya muncul di dunia Timur yang menampilkan pembagian mangsa dengan cara semacam itu agar pihak yang membaginya mendapatkan bagian yang lebih besar atau bahkan secara kes...

 

Buff-breasted mountain tanager

Species of bird Buff-breasted mountain tanager Conservation status Least Concern  (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Aves Order: Passeriformes Family: Thraupidae Genus: Dubusia Species: D. taeniata Binomial name Dubusia taeniata(Boissonneau, 1840) The buff-breasted mountain tanager (Dubusia taeniata) is a species of Neotropical bird in the tanager family Thraupidae. It is found in Bolivia, Colombia, Ecuador, Pe...

 

Élections législatives partielles de 1986 dans la Haute-Garonne

Cet article est une ébauche concernant la politique française et la Haute-Garonne. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. 03/1986 1988 Élections législatives partielles de 1986 dans la Haute-Garonne 8 sièges de députés à l'Assemblée nationale 28 septembre 1986 Corps électoral et résultats Population 824 501 Inscrits 561 774 Votants 386 472   68,79 %  11,4 Votes...

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

 

Elys Guzmán

Questa voce sull'argomento cestisti dominicani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Elys Guzmán Nazionalità  Rep. Dominicana Altezza 204 cm Peso 105 kg Pallacanestro Ruolo Ala grande Squadra  Soles S. Domingo Carriera Squadre di club 2011-2012 Toros de Aragua2012 Leones S. Domingo2013 Pant. de Miranda2013Mavort Quito2014 Huracanes Tampico2014Mavort Quito2015Je...

 

Souain-Perthes-lès-Hurlus

Commune in Grand Est, FranceSouain-Perthes-lès-HurlusCommuneThe town hall in SouainLocation of Souain-Perthes-lès-Hurlus Souain-Perthes-lès-HurlusShow map of FranceSouain-Perthes-lès-HurlusShow map of Grand EstCoordinates: 49°11′04″N 4°32′39″E / 49.1844°N 4.5442°E / 49.1844; 4.5442CountryFranceRegionGrand EstDepartmentMarneArrondissementChâlons-en-ChampagneCantonArgonne Suippe et VesleIntercommunalityRégion de SuippesGovernment • Mayor (2...

1994 Vermont gubernatorial election

For related races, see 1994 United States gubernatorial elections. 1994 Vermont gubernatorial election ← 1992 November 8, 1994 1996 →   Nominee Howard Dean David F. Kelley Thomas J. Morse Party Democratic Republican Independent Popular vote 145,661 40,292 15,000 Percentage 68.7% 19.0% 7.1% County results Municipality resultsDean:      30-40%      40-50%      50-60%    ...

 

Sinophone

Person who speaks at least one variety of Sinitic languages For the extinct mammal genus, see Sinophoneus.Not to be confused with Sinophobe or Sinophile. Map of the Chinese-speaking world.   Countries and regions with a native Chinese-speaking majority   Countries and regions where Chinese is not native but an official or educational language   Countries with significant Chinese-speaking minorities Sinophone, which means Chinese-speaking, typically refers to an i...

 

WKCY (AM)

Radio station in Harrisonburg, VirginiaWKCYHarrisonburg, VirginiaBroadcast areaHarrisonburg, VirginiaRockingham County, VirginiaFrequency1300 AM kHzBrandingNewsRadio WKCYProgrammingFormatNews/talk[1]AffiliationsFox News RadioCompass Media NetworksPremiere NetworksOwnershipOwneriHeartMedia, Inc.(iHM Licenses, LLC)Sister stationsWACL, WAZR, WKCI, WKCY-FM, WKDW, WSVOHistoryFirst air dateMay 11, 1967[2]Technical informationFacility ID41815ClassDPower6,400 watts daytime5 watts nigh...

1971 en Inde

Troisième guerre indo-pakistanaise (Attaque de chasseurs à Narayanganj. Chronologie de l'Inde ◄◄ 1967 1968 1969 1970 1971 1972 1973 1974 1975 ►► Chronologies Données clés 1968 1969 1970  1971  1972 1973 1974Décennies :1940 1950 1960  1970  1980 1990 2000Siècles :XVIIIe XIXe  XXe  XXIe XXIIeMillénaires :-Ier Ier  IIe  IIIe Chronologies géographiques Afrique Afrique du Sud, Algérie, Angola, Bénin, Botswana, Burkina Faso, B...

 

Afroféminisme

Ne doit pas être confondu avec Black feminism. L’afroféminisme ou afro-féminisme est un mouvement apparu pendant la période d’émancipation féministe des années 1970, à la même période que le Black feminism aux États-Unis. L’afroféminisme, porté par des afro-descendantes (d’Afrique, des Caraïbes, d'Europe et des diasporas), est un mouvement militant qui lutte à la fois contre les systèmes d’oppression sexiste, négrophobe et parfois capitaliste. Il se situe notamment...

 

Virginia Bruce

Untuk aktivis transgender yang memakai Virginia Bruce sebagai nama pena, lihat Virginia Prince. Virginia BruceFoto publisitas Virginia Bruce untuk Argentinean MagazineLahirHelen Virginia Briggs(1909-09-29)29 September 1909[1]Minneapolis, Minnesota, Amerika SerikatMeninggal24 Februari 1982(1982-02-24) (umur 72)Woodland Hills, California, Amerika SerikatPekerjaanPemeran, penyanyiTahun aktif1929–1981Suami/istriJohn Gilbert ​ ​(m. 1932; bercera...

إدموند لانغلي

دوق يورك أيرل كامبردج إدموند لانغلي (بالإنجليزية: Edmund of Langley)‏  إدموند لانغلي دوق يورك فترة الحكم6 أغسطس 1385- 1 أغسطس 1402   إدوارد من نوريتش ريتشارد يورك معلومات شخصية الميلاد 5 يونيو 1341(1341-06-05)لانغلي , هيرتفوردشاير الوفاة 1 أغسطس 1402 (61 سنة) (61 عاماً)لانغلي , هيرتفوردشاير اللق�...

 

Бердниково

У этого топонима есть и другие значения, см. Бердниково. ДеревняБердниково 54°25′05″ с. ш. 74°26′00″ в. д.HGЯO Страна  Россия Субъект Федерации Омская область Муниципальный район Черлакский Сельское поселение Иртышское История и география Основан 1908 Часовой пояс ...

 

Brighton MET College

Further education college in BrightonBrighton MET CollegeMain entrance of Brighton MET College Central Brighton Campus on Pelham StreetAddressCentral Brighton Campus Pelham Street,Brighton, BN1 4FAInformationOther nameBrighton Metropolitan CollegeFormer nameCity College Brighton & Hove, Brighton College of Technology, before that Brighton Technical College, Brighton School of Art & ScienceTypeFurther Education CollegeEstablished1858PrincipalPaul RileyGenderCoeducationalAge16+Enrolmen...

عيد الصعود

عيد الصعود   اليوم السنوي عيد الفصح + 39  [لغات أخرى]‏[1]  تعديل مصدري - تعديل   عيد الصعود[2] (ويعرف أيضا بعيد صعود يسوع المسيح ، يوم الصعود ، خميس الصعود ، أو أحيانًا الخميس المقدس) هو عيد مسيحي يحتفل فيه بذكرى صعود المسيح بالجسد إلى السماء بعد عيد القيامة...

 

الولايات الأمريكية المتجاورة

الولايات الأمريكية المتجاورةمعلومات عامةجزء من continental United States (en) البلد الولايات المتحدة تقع في التقسيم الإداري الولايات المتحدة المنطقة الزمنية منطقة زمنية وسطىالمنطقة الزمنية الجبليةزمن منطقة المحيط الهادئمنطقة زمنية شرقية الإحداثيات 39°N 98°W / 39°N 98°W / 39; -98...