Polyomino

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 juli 2019; kontroller kräver 3 redigeringar .

Polyomino , eller polyomino ( engelska  polyomino ) - platta geometriska former som bildas genom att koppla ihop flera encelliga rutor på deras sidor. Dessa är polyformer vars segment är kvadrater [1] .

En polyominopjäs kan ses som en ändlig ansluten delmängd av ett oändligt schackbräde som kan förbigås av ett torn [1] [3] .

Namn på polyominoer

Polyominoer ( n -minos) är uppkallade efter numret n av kvadraterna de består av:

n namn n namn
ett monomino 6 hexamino
2 dominobrickor 7 heptamino
3 tromino åtta oktamino
fyra tetramino 9 nonamino eller enneomino
5 pentomino tio decamino

Historik

Polyominoer har använts i underhållande matematik sedan åtminstone 1907 [4] [5] och har varit kända sedan antiken. Många resultat med figurer som innehåller från 1 till 6 rutor publicerades först i Fairy Chess Review mellan 1937 och 1957 under titeln " dissektionsproblem " .  Namnet "polyomino" eller "polyomino" ( eng. polyomino ) myntades av Solomon Golomb [1] 1953 och populariserades sedan av Martin Gardner [6] [7] .  

1967 publicerade tidskriften Science and Life en serie artiklar om pentominoer . Senare publicerades problem relaterade till polyominoer och andra polyformer under ett antal år [8] .

Generaliseringar av polyominoer

Beroende på om vändning eller rotation av figurer är tillåten, särskiljs följande tre typer av polyominoer [1] [2] :

Beroende på anslutningsförhållandena för närliggande celler särskiljs följande [1] [9] [10] :

Följande tabell samlar in data om antalet polyominofigurer och dess generaliseringar. Antalet kvasi - n -minos är 1 för n  = 1 och ∞ för n  > 1.

n polyominoer pseudopolyomino
bilateral ensidig fast bilateral ensidig fast
Allt med hål utan hål
A000105 A001419 A000104 A000988 A001168 A030222 A030233 A006770
ett ett 0 ett ett ett ett ett ett
2 ett 0 ett ett 2 2 2 fyra
3 2 0 2 2 6 5 6 tjugo
fyra 5 0 5 7 19 22 34 110
5 12 0 12 arton 63 94 166 638
6 35 0 35 60 216 524 991 3832
7 108 ett 107 196 760 3031 5931 23 592
åtta 369 6 363 704 2725 18 770 37 196 147 941
9 1285 37 1248 2500 9910 118 133 235 456 940 982
tio 4655 195 4460 9189 36 446 758 381 1 514 618 6 053 180
elva 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

Polyformer

Polyformer  är en generalisering av polyominoer, vars celler kan vara vilka som helst identiska polygoner eller polyedrar. En polyform är med andra ord en platt figur eller en rumslig kropp, bestående av flera sammanhängande kopior av en given grundform [11] .

Plana (tvådimensionella) polyformer inkluderar polyamonds , bildade av liksidiga trianglar; polyhexer , bildade av vanliga hexagoner; polyabolo , bestående av likbenta rätvinkliga trianglar och andra.

Exempel på rumsliga (tredimensionella) polyformer: polykuber, bestående av tredimensionella kuber; polyroner ( eng.  polyrhons ), bestående av rombododekaedrar [12] .

Polyformer är också generaliserade till fallet med högre dimensioner (till exempel de som bildas av hyperkuber - polyhyperkuber).

Uppgifter

Täckningar av rektanglar av kongruenta polyominoer

Ordningen för polyomino P  är det minsta antalet kongruenta kopior av P som är tillräckligt för att vika någon rektangel. För polyominoer, från kopior av vilka ingen rektangel kan läggas till, är ordningen inte definierad. Ordningen på polyomino P är lika med 1 om och endast om P  är en rektangel [13] .

Om det finns minst en rektangel som kan täckas av ett udda antal kongruenta kopior av P , kallas polyomino P för en udda polyomino ; om rektangeln bara kan vikas från ett jämnt antal kopior P , kallas P en jämn polyomino .

Denna terminologi introducerades 1968 av D. A. Klarner [1] [14] .

Det finns en uppsättning polyominoer av ordning 2; ett exempel är de så kallade L - polyominoerna [15] .

Olösta problem i matematik : Finns det en polyomino vars ordning är ett udda tal?

Polyominoer av ordning 3 existerar inte; ett bevis på detta publicerades 1992 [16] . Varje polyomino vars tre kopior kan bilda en rektangel är i sig en rektangel och har ordning 1. Det är inte känt om det finns en polyomino vars ordning är ett udda tal större än 3 [14] .

Det finns polyominoer av ordningen 4 , 10 , 18 , 24 , 28 , 50 , 76 , 92 , 312 ; det finns en konstruktion som gör det möjligt att erhålla en polyomino av storleksordningen 4 s för alla naturliga s [14] .

Olösta problem i matematik : Vilken är den minsta möjliga udda multipliciteten av att täcka en rektangel med en icke-rektangulär polyomino?

Klarner lyckades hitta en icke-rektangulär polyomino av ordning 2, varav 11 kopior kan bilda en rektangel [1] [14] [17] , och inget mindre udda antal kopior av denna polyomino kan täcka rektangeln. Från och med oktober 2015 är det inte känt om det finns en icke-rektangulär polyomino vars 9, 7 eller 5 kopior kan bilda en rektangel; inga andra exempel på polyominoer med en minsta udda multiplicitet som täcker 11 är kända (förutom det som Klarner hittade).

Minsta ytor

Minimal region ( eng. minimal region , minimal common superform ) för en given uppsättning polyominoer - polyominoer med minsta möjliga yta, innehållande varje polyomino från den givna uppsättningen [1] [14] [18] . Problemet med att hitta minimiarean för en uppsättning av tolv pentominoer ställdes först av T. R. Dawson i Fairy Chess Review 1942 [18] .

För en uppsättning av 12 pentominoer finns det två minimala niocellsregioner, som representerar 2 av 1285 nonominoer [1] [14] [18] :

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

Se även

Anteckningar

  1. ↑ 1 2 3 4 5 6 7 8 9 10 Golomb S. V. Polimino, 1975
  2. ↑ 1 2 Weisstein, Eric W. Polyomino  (engelska) på Wolfram MathWorld- webbplatsen .
  3. ↑ 1 2 Den populära definitionen av polyominoer som använder ett schacktorn är inte strikt: det finns frånkopplade delmängder av kvadratisk parkett som ett torn kan kringgå (till exempel är en grupp med fyra rutor på ett schackbräde a1, a8, h1, h8 inte en tetramino , även om ett torn som står på ett av dessa fält, kan kringgå tre andra fält i tre drag). En mer rigorös definition av polyominoer skulle vara med hjälp av "visir"-figuren som används i Tamerlanes schack : vesiren flyttar bara en cell horisontellt eller vertikalt.
  4. ↑ Henry E. Dudeney. Canterbury Puzzles, 1975, s. 111–113
  5. ↑ Alexandre Owen Muñiz. Några trevliga Pentomino-färgningsproblem . Hämtad 24 oktober 2015. Arkiverad från originalet 4 mars 2016.
  6. ↑ Gardner M. Matematiska pussel och underhållning, 1971. - Kapitel 12. Polyomino. - s. 111-124
  7. ↑ Gardner M. Matematiska romaner, 1974. - Kapitel 7. Pentominoes och polyominoes: fem spel och en serie problem. - s. 81-95
  8. ↑ Science and Life nr. 2-12 (1967), 1, 6, 9, 11 (1968), etc.
  9. ↑ Polyformer . Hämtad 22 augusti 2013. Arkiverad från originalet 11 september 2015.
  10. ↑ Weisstein, Eric W. Polyplet  på Wolfram MathWorld -webbplatsen .
  11. ↑ Weisstein, Eric W. Polyform  på Wolfram MathWorld -webbplatsen .
  12. ↑ Kol. Sichermans hemsida. Polyform Curiosities Arkiverad 14 december 2014 på Wayback Machine . Katalog över Polyrhons Arkiverad 11 september 2015 på Wayback Machine
  13. ↑ Karl Dahlke. Plattläggning av rektanglar med polyominoer . Hämtad 25 augusti 2013. Arkiverad från originalet 15 februari 2020.
  14. ↑ 1 2 3 4 5 6 Golomb, S. V. Polyominoes : Pussel, mönster, problem och packningar  . - 2:a upplagan - Princeton University Press, 1994. - ISBN 0-691-08573-0 .
  15. ↑ Weisstein, Eric W. L-Polyomino  på Wolfram MathWorld -webbplatsen .
  16. ↑ I Stewart, A. Wormstein. Polyominoer av ordning 3 finns inte  //  Journal of Combinatorial Theory, serie A  : tidskrift. - 1992. - September ( vol. 61 , nr 1 ). - S. 130-136 .
  17. ↑ Michael Reid. Primer av P hexomino . Hämtad 24 oktober 2015. Arkiverad från originalet 22 mars 2016.
  18. ↑ 1 2 3 Alexandre Owen Muñiz. Polyomino vanliga superformer . Hämtad 24 oktober 2015. Arkiverad från originalet 21 maj 2017.

Litteratur

Länkar


  Gå till Wikidata-objektet  Ordböcker och uppslagsverk
I bibliografiska kataloger
 Polyformer
Typer av polyformer
Polyomino efter antal celler
Pussel med polykuber
Staplingsuppgift
  • Exakt täckningsproblem
  • Algoritm
  • länkar
Personligheter
Relaterade ämnen
Andra pussel och spel