Polyomino

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. heinäkuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Polyomino tai polyomino ( englanniksi  polyomino ) - litteät geometriset muodot, jotka on muodostettu yhdistämällä useita yksisoluisia neliöitä niiden sivuilla. Nämä ovat polyformeja , joiden segmentit ovat neliöitä [1] .

Polyominonappula voidaan nähdä äärettömän shakkilaudan äärellisenä yhdistettynä osajoukona, joka voidaan ohittaa tornilla [1] [3] .

Polyominojen nimet

Polyominot ( n -minot) on nimetty niiden neliöiden lukumäärän n mukaan, joista ne koostuvat:

n Nimi n Nimi
yksi monomino 6 heksaamino
2 domino 7 heptamino
3 tromino kahdeksan oktamino
neljä tetramino 9 nonamino tai enneomino
5 pentomino kymmenen dekamino

Historia

Polyominoja on käytetty viihdyttävässä matematiikassa ainakin vuodesta 1907 [4] [5] ja ne ovat olleet tunnettuja antiikista lähtien. Monet tulokset, joissa oli 1-6 ruutua sisältäviä lukuja, julkaistiin ensimmäisen kerran Fairy Chess Review -lehdessä vuosina 1937-1957 otsikolla " dissektioongelmat " .  Nimen "polyomino" tai "polyomino" ( eng. polyomino ) loi Solomon Golomb [1] vuonna 1953, ja sen teki sitten suosituksi Martin Gardner [6] [7] .  

Vuonna 1967 Science and Life - aikakauslehti julkaisi sarjan artikkeleita pentominoista . Myöhemmin polyominoihin ja muihin polyformeihin liittyviä ongelmia julkaistiin useiden vuosien ajan [8] .

Polyominojen yleistykset

Sen mukaan, sallitaanko kuvien kääntäminen vai kiertäminen, erotetaan seuraavat kolme polyominotyyppiä [1] [2] :

Naapurisolujen yhteysolosuhteista riippuen erotetaan seuraavat [1] [9] [10] :

Seuraavaan taulukkoon on koottu tiedot polyominohahmojen lukumäärästä ja sen yleistyksistä. Kvasi - n -minojen lukumäärä on 1, kun n  = 1 ja ∞, kun n  > 1.

n polyominot pseudopolyomino
kahdenvälinen yksipuolinen korjattu kahdenvälinen yksipuolinen korjattu
kaikki reikien kanssa ilman reikiä
A000105 A001419 A000104 A000988 A001168 A030222 A030233 A006770
yksi yksi 0 yksi yksi yksi yksi yksi yksi
2 yksi 0 yksi yksi 2 2 2 neljä
3 2 0 2 2 6 5 6 kaksikymmentä
neljä 5 0 5 7 19 22 34 110
5 12 0 12 kahdeksantoista 63 94 166 638
6 35 0 35 60 216 524 991 3832
7 108 yksi 107 196 760 3031 5931 23 592
kahdeksan 369 6 363 704 2725 18 770 37 196 147 941
9 1285 37 1248 2500 9910 118 133 235 456 940 982
kymmenen 4655 195 4460 9189 36 446 758 381 1 514 618 6 053 180
yksitoista 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

Polyforms

Polyformit  ovat yleistys polyominoista, joiden solut voivat olla mitä tahansa identtisiä polygoneja tai polyhedraja. Toisin sanoen polyform on litteä figuuri tai tilakappale, joka koostuu tietyn perusmuodon useista yhdistetyistä kopioista [11] .

Tasomaisia ​​(kaksiulotteisia) polyformeja ovat tasasivuisista kolmioista muodostetut polyamonds ; polyheksit , muodostettu säännöllisistä kuusikulmioista; polyabolo , joka koostuu tasakylkistä suorakulmaisista kolmioista ja muista.

Esimerkkejä spatiaalisista (kolmiulotteisista) polyformeista: polycubes, jotka koostuvat kolmiulotteisista kuutioista; polyronit ( eng.  polyrhons ), jotka koostuvat rombododekaedreista [12] .

Polyformit yleistetään myös suurempien ulottuvuuksiin (esimerkiksi hyperkuutioista muodostetut - polyhyperkuutiot).

Tehtävät

Suorakulmioiden päällysteet kongruenteilla polyominoilla

Polyomino P : n järjestys on P  :n yhteensopivien kopioiden vähimmäismäärä, joka riittää taittamaan jonkin suorakulmion. Polyominoille, joiden kopioista ei voi lisätä suorakulmiota, järjestystä ei ole määritelty. Polyominon P kertaluku on 1, jos ja vain jos P  on suorakulmio [13] .

Jos on vähintään yksi suorakulmio, joka voidaan peittää parittomalla määrällä P:n yhteneviä kopioita , polyomino P :tä kutsutaan parittomaksi polyominoksi ; jos suorakulmio voidaan taittaa vain parillisesta kopiomäärästä P , kutsutaan P : tä parilliseksi polyominoksi .

Tämän terminologian esitteli vuonna 1968 D. A. Klarner [1] [14] .

On joukko luokan 2 polyominoja; esimerkkinä ovat ns. L - polyominot [15] .

Ratkaisemattomat matematiikan ongelmat : Onko olemassa polyominoa, jonka järjestys on pariton luku?

Kolmannen asteen polyominoja ei ole olemassa; todiste tästä julkaistiin vuonna 1992 [16] . Mikä tahansa polyomino, jonka kolme kopiota voivat muodostaa suorakulmion, on itse suorakulmio ja sen järjestys on 1. Ei tiedetä, onko olemassa polyominoa, jonka järjestys on pariton luku, joka on suurempi kuin 3 [14] .

Polyominoja on luokkaa 4 , 10 , 18 , 24 , 28 , 50 , 76 , 92 , 312 ; on olemassa rakenne, joka mahdollistaa 4 s :n polyominon saamisen mille tahansa luonnolliselle s :lle [14] .

Ratkaisemattomat matematiikan ongelmat : Mikä on pienin mahdollinen pariton monikerroin suorakulmion peittämisessä ei-suorakulmaisella polyominolla?

Klarner onnistui löytämään luokkaa 2 olevan ei-suorakulmaisen polyominon, josta 11 kopiota voi muodostaa suorakulmion [1] [14] [17] , eikä pienempi pariton määrä tämän polyominon kopioita voi peittää suorakulmion. Lokakuussa 2015 ei tiedetä, onko olemassa ei-suorakulmaista polyominoa, jonka 9, 7 tai 5 kopiota voi muodostaa suorakulmion; muita esimerkkejä polyominoista, joilla on vähintään pariton peittokerroin 11, ei tunneta (paitsi Klarnerin löytämä).

Vähimmäisalueet

Minimialue (eng. minimal region , minimaalinen yleinen superform ) tietylle polyominojen joukolle - pienimmän mahdollisen alueen polyominoja, jotka sisältävät jokaisen polyominon annetusta joukosta [1] [14] [18] . T. R. Dawson esitti ensimmäisen kerran Fairy Chess Review -julkaisussa vuonna 1942 [18] -ongelman kahdentoista pentominon sarjan vähimmäispinta-alan löytämisestä .

12 pentominon sarjassa on kaksi vähimmäisyhdeksänsoluista aluetta, jotka edustavat kahta 1285 nonominoosta [1] [14] [18] :

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

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 4 5 6 7 8 9 10 Golomb S. V. Polimino, 1975
  2. ↑ 1 2 Weisstein, Eric W. Polyomino  (englanniksi) Wolfram MathWorld -verkkosivustolla .
  3. ↑ 1 2 Suosittu shakkitornia käyttävien polyominojen määritelmä ei ole tiukka: neliöparketissa on erillisiä osajoukkoja, jotka torni voi ohittaa (esim. shakkilaudan neljän ruudun ryhmä a1, a8, h1, h8 ei ole tetramino , vaikka torni seisoo yhdellä näistä kentistä, voi ohittaa kolme muuta kenttää kolmella siirrolla). Polyominojen tiukempi määritelmä olisi Tamerlanen shakissa käytetyn "visiiri" -hahmon avulla : visiiri liikuttaa vain yhtä solua vaaka- tai pystysuunnassa.
  4. ↑ Henry E. Dudeney. Canterbury Puzzles, 1975, s. 111–113
  5. ↑ Alexandre Owen Muñiz. Hienoja Pentominon väritysongelmia . Haettu 24. lokakuuta 2015. Arkistoitu alkuperäisestä 4. maaliskuuta 2016.
  6. ↑ Gardner M. Matemaattisia pulmia ja viihdettä, 1971. - Luku 12. Polyomino. - s. 111-124
  7. ↑ Gardner M. Mathematical novels, 1974. - Luku 7. Pentominot ja polyominot: viisi peliä ja sarja tehtäviä. - s.81-95
  8. ↑ Tiede ja elämä nro 2-12 (1967), 1, 6, 9, 11 (1968) jne.
  9. ↑ Polyformit . Haettu 22. elokuuta 2013. Arkistoitu alkuperäisestä 11. syyskuuta 2015.
  10. ↑ Weisstein , Eric W. Polyplet  Wolfram MathWorld -verkkosivustolla .
  11. ↑ Weisstein, Eric W. Polyform  Wolfram MathWorld -verkkosivustolla .
  12. ↑ Kol. Sichermanin kotisivu. Polyform Curiosities Arkistoitu 14. joulukuuta 2014 Wayback Machinessa . Catalog of Polyrhons Arkistoitu 11. syyskuuta 2015 Wayback Machinessa
  13. ↑ Karl Dahlke. Laatoitus suorakulmiot polyominoilla . Haettu 25. elokuuta 2013. Arkistoitu alkuperäisestä 15. helmikuuta 2020.
  14. ↑ 1 2 3 4 5 6 Golomb, S. V. Polyominoes : palapelit, kuviot, ongelmat ja pakkaukset  . - 2. painos - Princeton University Press, 1994. - ISBN 0-691-08573-0 .
  15. ↑ Weisstein, Eric W. L - Polyomino  Wolfram MathWorld -verkkosivustolla .
  16. ↑ IN Stewart, A. Wormstein. Järjestyksen 3 polyominoja ei ole olemassa  //  Journal of Combinatorial Theory, Series A  : Journal. - 1992. - syyskuu ( osa 61 , nro 1 ) . - s. 130-136 .
  17. ↑ Michael Reid. P-heksominon alkuluvut . Haettu 24. lokakuuta 2015. Arkistoitu alkuperäisestä 22. maaliskuuta 2016.
  18. ↑ 1 2 3 Alexandre Owen Muñiz. Polyomino Common Superforms . Haettu 24. lokakuuta 2015. Arkistoitu alkuperäisestä 21. toukokuuta 2017.

Kirjallisuus

Linkit


  Siirry Wikidata-kohteeseen  Sanakirjat ja tietosanakirjat
Bibliografisissa luetteloissa
 Polyformit
Polyformien tyypit
Polyomino solujen lukumäärän mukaan
Palapelit polycubeilla
Pinoamistehtävä
  • Tarkka kattavuusongelma
  • Algoritmi
  • linkkejä
Persoonallisuudet
liittyvät aiheet
Muita pulmia ja pelejä