Polyomino , nebo polyomino ( anglicky polyomino ) - ploché geometrické tvary vzniklé spojením několika jednobuněčných čtverců na jejich stranách. Jedná se o polyformy , jejichž segmenty jsou čtverce [1] .
Na polyomino figurku lze pohlížet jako na konečnou spojenou podmnožinu nekonečné šachovnice , kterou lze obejít věží [1] [3] .
Polyominoes ( n -minos) jsou pojmenovány podle čísla n čtverců, ze kterých se skládají:
n | název | n | název |
---|---|---|---|
jeden | monomino | 6 | hexaamino |
2 | domino | 7 | heptamino |
3 | třemino | osm | octamino |
čtyři | tetramino | 9 | nonamino nebo enneomino |
5 | pentomino | deset | decamino |
Polyominoes se v zábavné matematice používají minimálně od roku 1907 [4] [5] a jsou známy již od starověku. Mnoho výsledků s čísly obsahujícími od 1 do 6 čtverců bylo poprvé publikováno v Fairy Chess Review v letech 1937 až 1957 pod názvem „ problémy pitvy “ . Název „polyomino“ nebo „polyomino“ (anglicky polyomino ) vymyslel Solomon Golomb [1] v roce 1953 a poté jej zpopularizoval Martin Gardner [6] [7] .
V roce 1967 časopis Science and Life publikoval sérii článků o pentominech . Později byly po řadu let publikovány problémy související s polyominy a jinými polyformami [8] .
V závislosti na tom, zda je povoleno překlápění nebo otáčení figur, se rozlišují následující tři typy polyominoes [1] [2] :
V závislosti na podmínkách připojení sousedních buněk se rozlišují následující [1] [9] [10] :
Následující tabulka shromažďuje údaje o počtu polyomino figur a jejich zobecnění. Počet kvazi - n - minos je 1 pro n = 1 a ∞ pro n > 1.
n | polyominoes | pseudopolyomino | ||||||
---|---|---|---|---|---|---|---|---|
bilaterální | jednostranný | pevný | bilaterální | jednostranný | pevný | |||
Všechno | s otvory | bez děr | ||||||
A000105 | A001419 | A000104 | A000988 | A001168 | A030222 | A030233 | A006770 | |
jeden | jeden | 0 | jeden | jeden | jeden | jeden | jeden | jeden |
2 | jeden | 0 | jeden | jeden | 2 | 2 | 2 | čtyři |
3 | 2 | 0 | 2 | 2 | 6 | 5 | 6 | dvacet |
čtyři | 5 | 0 | 5 | 7 | 19 | 22 | 34 | 110 |
5 | 12 | 0 | 12 | osmnáct | 63 | 94 | 166 | 638 |
6 | 35 | 0 | 35 | 60 | 216 | 524 | 991 | 3832 |
7 | 108 | jeden | 107 | 196 | 760 | 3031 | 5931 | 23 592 |
osm | 369 | 6 | 363 | 704 | 2725 | 18 770 | 37 196 | 147 941 |
9 | 1285 | 37 | 1248 | 2500 | 9910 | 118 133 | 235 456 | 940 982 |
deset | 4655 | 195 | 4460 | 9189 | 36 446 | 758 381 | 1 514 618 | 6 053 180 |
jedenáct | 17 073 | 979 | 16 094 | 33 896 | 135 268 | 4 915 652 | 9 826 177 | 39 299 408 |
12 | 63 600 | 4663 | 58 937 | 126 759 | 505 861 | 32 149 296 | 64 284 947 | 257 105 146 |
Polyformy jsou zobecněním polyominoes, jejichž buňkami mohou být libovolné identické mnohoúhelníky nebo mnohostěny. Jinými slovy, polyforma je plochá postava nebo prostorové těleso, skládající se z několika spojených kopií daného základního tvaru [11] .
Rovinné (dvourozměrné) polyformy zahrnují polyamandy , vytvořené z rovnostranných trojúhelníků; polyhexes , vytvořené z pravidelných šestiúhelníků; polyabolo , skládající se z rovnoramenných pravoúhlých trojúhelníků a další.
Příklady prostorových (trojrozměrných) polyforem: polycubes, skládající se z trojrozměrných krychlí; polyrony ( angl. polyrhons ), sestávající z kosočtverců [12] .
Polyformy se zobecňují i pro případ vyšších dimenzí (například ty tvořené z hyperkrychlí – polyhyperkrychlí).
Pořadí polyomino P je minimální počet kongruentních kopií P dostatečný k tomu, aby se složil nějaký obdélník. U polyominoes, z jejichž kopií nelze přidat žádný obdélník, není pořadí definováno. Řád polyomina P je roven 1 právě tehdy, když P je obdélník [13] .
Pokud existuje alespoň jeden obdélník, který může být pokryt lichým počtem shodných kopií P , polyomino P se nazývá liché polyomino ; pokud lze obdélník složit pouze ze sudého počtu kopií P , nazývá se P sudé polyomino .
Tuto terminologii zavedl v roce 1968 D. A. Klarner [1] [14] .
Existuje soubor polyominů řádu 2; příkladem jsou tzv. L - polyominoes [15] .
Nevyřešené problémy v matematice : Existuje polyomino, jehož pořadí je liché číslo?Polyominoes řádu 3 neexistují; důkaz toho byl publikován v roce 1992 [16] . Každé polyomino, jehož tři kopie mohou tvořit obdélník, je samo o sobě obdélník a má pořadí 1. Není známo, zda existuje polyomino, jehož pořadí je liché číslo větší než 3 [14] .
Existují polyominy řádu 4 , 10 , 18 , 24 , 28 , 50 , 76 , 92 , 312 ; existuje konstrukce, která umožňuje získat polyomino řádu 4 s pro jakékoli přirozené s [14] .
Nevyřešené úlohy v matematice : Jaká je nejmenší možná lichá násobnost pokrytí obdélníku nepravoúhlým polyominem?Klarnerovi se podařilo najít nepravoúhlé polyomino řádu 2, jehož 11 kopií může tvořit obdélník [1] [14] [17] , přičemž menší lichý počet kopií tohoto polyomina nemůže pokrýt obdélník. Od října 2015 není známo, zda existuje nepravoúhlé polyomino, jehož 9, 7 nebo 5 kopií může tvořit obdélník; žádné další příklady polyominoes s minimální lichou násobností pokrytí 11 nejsou známy (kromě jednoho nalezeného Klarnerem).
Minimální oblast ( angl. minimal region , minimal common superform ) pro danou množinu polyomino - polyomino o co nejmenší ploše, obsahující každé polyomino z dané množiny [1] [14] [18] . Problém najít minimální plochu pro sadu dvanácti pentomin poprvé položil T. R. Dawson v Fairy Chess Review v roce 1942 [18] .
Pro sadu 12 pentominoes existují dvě minimální devítibuněčné oblasti, které představují 2 z 1285 nonominoes [1] [14] [18] :
### ### ##### ##### # #
![]() | |
---|---|
V bibliografických katalozích |
Polyformy | |
---|---|
Typy polyformů | |
Polyomino podle počtu buněk | |
Puzzle s polycubes | |
Úkol skládání |
|
Osobnosti |
|
související témata | |
Další hádanky a hry |