Polyomino

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. juli 2019; checks kræver 3 redigeringer .

Polyomino eller polyomino ( engelsk  polyomino ) - flade geometriske former dannet ved at forbinde flere encellede firkanter på deres sider. Disse er polyformer , hvis segmenter er firkanter [1] .

En polyominobrik kan ses som en endelig forbundet delmængde af et uendeligt skakbræt , der kan omgås af et tårn [1] [3] .

Navne på polyominoer

Polyominoer ( n -minos) er opkaldt efter tallet n af de kvadrater, de består af:

n Navn n Navn
en monomino 6 hexamino
2 dominobrikker 7 heptamino
3 tromino otte octamino
fire tetramino 9 nonamino eller enneomino
5 pentomino ti decamino

Historie

Polyominoer har været brugt i underholdende matematik siden mindst 1907 [4] [5] og har været kendt siden antikken. Mange resultater med figurer indeholdende fra 1 til 6 felter blev først offentliggjort i Fairy Chess Review mellem 1937 og 1957 under titlen " dissektionsproblemer " .  Navnet "polyomino" eller "polyomino" ( eng. polyomino ) blev opfundet af Solomon Golomb [1] i 1953 og derefter populariseret af Martin Gardner [6] [7] .  

I 1967 publicerede magasinet Science and Life en række artikler om pentominoer . Senere blev problemer relateret til polyominoer og andre polyformer publiceret i en årrække [8] .

Generaliseringer af polyominoer

Afhængigt af om vending eller rotation af figurer er tilladt, skelnes de følgende tre typer polyominoer [1] [2] :

Afhængigt af tilslutningsbetingelserne for naboceller skelnes følgende [1] [9] [10] :

Følgende tabel indsamler data om antallet af polyomino-figurer og dets generaliseringer. Antallet af kvasi - n -minoer er 1 for n  = 1 og ∞ for n  > 1.

n polyominoer pseudopolyomino
bilateralt ensidigt fast bilateralt ensidigt fast
alle med huller uden huller
A000105 A001419 A000104 A000988 A001168 A030222 A030233 A006770
en en 0 en en en en en en
2 en 0 en en 2 2 2 fire
3 2 0 2 2 6 5 6 tyve
fire 5 0 5 7 19 22 34 110
5 12 0 12 atten 63 94 166 638
6 35 0 35 60 216 524 991 3832
7 108 en 107 196 760 3031 5931 23 592
otte 369 6 363 704 2725 18 770 37 196 147 941
9 1285 37 1248 2500 9910 118 133 235 456 940 982
ti 4655 195 4460 9189 36 446 758 381 1 514 618 6 053 180
elleve 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  er en generalisering af polyominoer, hvis celler kan være alle identiske polygoner eller polyedre. En polyform er med andre ord en flad figur eller et rumligt legeme, bestående af flere sammenhængende kopier af en given grundform [11] .

Plane (todimensionelle) polyformer omfatter polyamanter , dannet af ligesidede trekanter; polyhexer , dannet af regulære sekskanter; polyabolo , bestående af ligebenede retvinklede trekanter og andre.

Eksempler på rumlige (tredimensionelle) polyformer: polykuber, bestående af tredimensionelle terninger; polyroner ( eng.  polyrhons ), bestående af rhombododecahedrons [12] .

Polyformer er også generaliseret til tilfælde af højere dimensioner (for eksempel dem, der er dannet af hyperkuber - polyhyperkuber).

Opgaver

Dækning af rektangler med kongruente polyominoer

Rækkefølgen af ​​polyomino P  er det mindste antal kongruente kopier af P , der er tilstrækkeligt til at folde et eller andet rektangel. For polyominoer, fra kopier, hvoraf der ikke kan tilføjes et rektangel, er rækkefølgen ikke defineret. Rækkefølgen af ​​polyomino P er lig med 1, hvis og kun hvis P  er et rektangel [13] .

Hvis der er mindst et rektangel, der kan dækkes af et ulige antal kongruente kopier af P , kaldes polyominoen P en ulige polyomino ; hvis rektanglet kun kan foldes fra et lige antal kopier P , kaldes P en lige polyomino .

Denne terminologi blev introduceret i 1968 af D. A. Klarner [1] [14] .

Der er et sæt polyominoer af orden 2; et eksempel er de såkaldte L - polyominoer [15] .

Uløste problemer i matematik : Findes der en polyomino, hvis rækkefølge er et ulige tal?

Polyominoer af orden 3 eksisterer ikke; et bevis på dette blev offentliggjort i 1992 [16] . Enhver polyomino, hvis tre kopier kan danne et rektangel, er i sig selv et rektangel og har orden 1. Det vides ikke, om der findes en polyomino, hvis rækkefølge er et ulige tal større end 3 [14] .

Der er polyominoer af orden 4 , 10 , 18 , 24 , 28 , 50 , 76 , 92 , 312 ; der er en konstruktion, der gør det muligt at opnå en polyomino af størrelsesordenen 4 s for enhver naturlig s [14] .

Uløste problemer i matematik : Hvad er den mindst mulige ulige multiplicitet af at dække et rektangel med en ikke-rektangulær polyomino?

Klarner formåede at finde en ikke-rektangulær polyomino af orden 2, hvoraf 11 kopier kan danne et rektangel [1] [14] [17] , og intet mindre ulige antal kopier af denne polyomino kan dække rektanglet. Fra oktober 2015 vides det ikke, om der er en ikke-rektangulær polyomino, hvis 9, 7 eller 5 kopier kan danne et rektangel; der kendes ingen andre eksempler på polyominoer med en mindste ulige multiplicitet på 11 (bortset fra den, Klarner fandt).

Minimumsarealer

Minimal region (eng. minimal region , minimal common superform ) for et givet sæt polyominoer - polyominoer med det mindst mulige areal, der indeholder hver polyomino fra det givne sæt [1] [14] [18] . Problemet med at finde minimumsarealet for et sæt på tolv pentominoer blev først stillet af T. R. Dawson i Fairy Chess Review i 1942 [18] .

For et sæt på 12 pentominoer er der to minimale nicelleregioner, der repræsenterer 2 ud af 1285 nonominoer [1] [14] [18] :

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

Se også

Noter

  1. ↑ 1 2 3 4 5 6 7 8 9 10 Golomb S. V. Polimino, 1975
  2. ↑ 1 2 Weisstein, Eric W. Polyomino  (engelsk) på Wolfram MathWorld- webstedet .
  3. ↑ 1 2 Den populære definition af polyominoer ved brug af et skaktårn er ikke streng: der er afbrudte delmængder af kvadratisk parket, som et tårn kan omgå (f.eks. er en gruppe på fire kvadrater på et skakbræt a1, a8, h1, h8 ikke en tetramino , selvom et tårn står på et af disse felter, kan omgå tre andre felter i tre træk). En mere stringent definition af polyominoer ville være ved hjælp af "vesiren"-figuren brugt i Tamerlanes skak : vesiren flytter kun én celle vandret eller lodret.
  4. ↑ Henry E. Dudeney. Canterbury Puzzles, 1975, s. 111-113
  5. ↑ Alexandre Owen Muñiz. Nogle gode Pentomino-farveproblemer . Hentet 24. oktober 2015. Arkiveret fra originalen 4. marts 2016.
  6. ↑ Gardner M. Matematiske gåder og underholdning, 1971. - Kapitel 12. Polyomino. - s. 111-124
  7. ↑ Gardner M. Matematiske romaner, 1974. - Kapitel 7. Pentominoer og polyominoer: fem spil og en række problemer. - s.81-95
  8. ↑ Science and Life nr. 2-12 (1967), 1, 6, 9, 11 (1968) osv.
  9. ↑ Polyformer . Hentet 22. august 2013. Arkiveret fra originalen 11. september 2015.
  10. ↑ Weisstein, Eric W. Polyplet  på Wolfram MathWorld -webstedet .
  11. ↑ Weisstein, Eric W. Polyform  på Wolfram MathWorld- webstedet .
  12. ↑ Kol. Sichermans hjemmeside. Polyform Curiosities Arkiveret 14. december 2014 på Wayback Machine . Katalog over Polyrhons Arkiveret 11. september 2015 på Wayback Machine
  13. ↑ Karl Dahlke. Flisebelægning af rektangler med polyominoer . Hentet 25. august 2013. Arkiveret fra originalen 15. februar 2020.
  14. ↑ 1 2 3 4 5 6 Golomb, S. V. Polyominoes : Gåder, mønstre, problemer og pakninger  . - 2. udgave - Princeton University Press, 1994. - ISBN 0-691-08573-0 .
  15. ↑ Weisstein, Eric W. L-Polyomino  på Wolfram MathWorld -webstedet .
  16. ↑ I Stewart, A. Wormstein. Polyominoer af orden 3 eksisterer ikke  //  Journal of Combinatorial Theory, serie A  : tidsskrift. - 1992. - September ( bind 61 , nr. 1 ). - S. 130-136 .
  17. ↑ Michael Reid. Primtal for P-hexominoen . Hentet 24. oktober 2015. Arkiveret fra originalen 22. marts 2016.
  18. ↑ 1 2 3 Alexandre Owen Muñiz. Polyomino almindelige superformer . Hentet 24. oktober 2015. Arkiveret fra originalen 21. maj 2017.

Litteratur

Links


  Gå til Wikidata-elementet  Ordbøger og encyklopædier
I bibliografiske kataloger
 Polyformer
Typer af polyformer
Polyomino efter antal celler
Puslespil med polykuber
Stable opgave
  • Præcis dækningsproblem
  • Algoritme
  • links
Personligheder
relaterede emner
Andre puslespil og spil