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] .
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 |
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] .
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 ä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).
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).
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] :
### ### ##### ##### # #
![]() | |
---|---|
I bibliografiska kataloger |
Polyformer | |
---|---|
Typer av polyformer | |
Polyomino efter antal celler | |
Pussel med polykuber | |
Staplingsuppgift |
|
Personligheter |
|
Relaterade ämnen | |
Andra pussel och spel |