Polyomino

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. července 2019; kontroly vyžadují 3 úpravy .

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] .

Jména polyominů

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

Historie

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] .

Zobecnění polyominoes

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

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í).

Úkoly

Pokrytí obdélníků kongruentními polyominy

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í plochy

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] :

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

Viz také

Poznámky

  1. ↑ 1 2 3 4 5 6 7 8 9 10 Golomb S. V. Polimino, 1975
  2. ↑ 1 2 Weisstein, Eric W. Polyomino  (anglicky) na webu Wolfram MathWorld .
  3. ↑ 1 2 Populární definice polyominoes pomocí šachové věže není přísná: existují odpojené podmnožiny čtvercové parkety, které věž může obejít (například skupina čtyř polí na šachovnici a1, a8, h1, h8 není a tetramino , ačkoli věž stojí na jednom z těchto polí, může obejít tři další pole ve třech tazích). Přesnější definice polyominoes by byla s pomocí figury „vezíra“ používaného v Tamerlánových šachách : vezír se pohybuje vodorovně nebo svisle pouze o jednu buňku.
  4. ↑ Henry E. Dudeney. Canterbury Puzzles, 1975, s. 111–113
  5. ↑ Alexandre Owen Muñiz. Některé pěkné problémy s barvením Pentomino . Získáno 24. října 2015. Archivováno z originálu dne 4. března 2016.
  6. ↑ Gardner M. Matematické hádanky a zábava, 1971. - Kapitola 12. Polyomino. - str. 111-124
  7. ↑ Gardner M. Matematické romány, 1974. - Kapitola 7. Pentomina a polyomina: pět her a řada problémů. - str.81-95
  8. ↑ Věda a život č. 2-12 (1967), 1, 6, 9, 11 (1968) atd.
  9. ↑ Polyformy . Získáno 22. srpna 2013. Archivováno z originálu 11. září 2015.
  10. ↑ Weisstein, Eric W. Polyplet  na webu Wolfram MathWorld .
  11. ↑ Weisstein, Eric W. Polyform  na webu Wolfram MathWorld .
  12. ↑ plk. Domovská stránka Sichermana. Polyform Curiosities Archived 14. prosince 2014 na Wayback Machine . Katalog Polyrhons Archivováno 11. září 2015 na Wayback Machine
  13. ↑ Karl Dahlke. Obdélníky Obdélníky Polyominoes . Získáno 25. srpna 2013. Archivováno z originálu 15. února 2020.
  14. ↑ 1 2 3 4 5 6 Golomb, S. V. Polyominoes : Hádanky, vzory, problémy a balení  . - 2. vyd. - Princeton University Press, 1994. - ISBN 0-691-08573-0 .
  15. ↑ Weisstein, Eric W. L-Polyomino  na webu Wolfram MathWorld .
  16. ↑ IN Stewart, A. Wormstein. Polyominoes řádu 3 neexistují  //  Journal of Combinatorial Theory, Series A  : journal. - 1992. - září ( roč. 61 , č. 1 ). - S. 130-136 .
  17. ↑ Michael Reid. Prvočísla P hexomino . Získáno 24. října 2015. Archivováno z originálu dne 22. března 2016.
  18. ↑ 1 2 3 Alexandre Owen Muñiz. Společné superformy Polyomino . Získáno 24. října 2015. Archivováno z originálu 21. května 2017.

Literatura

Odkazy


  Přejděte na položku Wikidata  Slovníky a encyklopedie
V bibliografických katalozích
 Polyformy
Typy polyformů
Polyomino podle počtu buněk
Puzzle s polycubes
Úkol skládání
  • Přesný problém pokrytí
  • Algoritmus
  • odkazy
Osobnosti
související témata
Další hádanky a hry