Polyomino

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. július 10-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

Polyomino vagy polyomino ( angolul  polyomino ) - lapos geometriai formák, amelyeket több egysejtű négyzet összekapcsolásával alakítanak ki az oldalukon. Ezek olyan poliformok , amelyek szegmensei négyzetek [1] .

A poliomino-bábu egy végtelen sakktábla véges összefüggő részhalmazaként tekinthető, amely egy bástya által megkerülhető [1] [3] .

A poliominók nevei

A poliominókat ( n -minók) a négyzetek n számáról nevezték el , amelyekből állnak:

n Név n Név
egy monomino 6 hexamino
2 dominó 7 heptamino
3 tromino nyolc oktamino
négy tetramino 9 nonamino vagy enneomino
5 pentomino tíz decamino

Történelem

A poliominókat legalább 1907 óta használják a szórakoztató matematikában [4] [5] , és az ókor óta ismerték. Számos, 1–6 négyzetből álló ábrát tartalmazó eredmény először a Fairy Chess Review-ban jelent meg 1937 és 1957 között „ boncolási problémák” címmel .  A "polyomino" vagy "polyomino" ( eng. polyomino ) elnevezést Solomon Golomb [1] találta ki 1953-ban, majd Martin Gardner [6] [7] tette népszerűvé .  

1967 - ben a Science and Life magazin cikksorozatot jelentetett meg a pentominókkal kapcsolatban . Később évekig publikáltak a poliominókkal és más poliformokkal kapcsolatos problémákat [8] .

Poliominók általánosításai

Attól függően, hogy a figurák megfordítása vagy elforgatása megengedett-e, a következő három poliominótípust különböztetjük meg [1] [2] :

A szomszédos cellák kapcsolódási feltételeitől függően a következőket különböztetjük meg [1] [9] [10] :

A következő táblázat a poliomino-figurák számáról és annak általánosításairól gyűjt adatokat. A kvázi - n -minók száma 1, ha n  = 1, és ∞, ha n  > 1.

n poliominók pszeudopoliomino
kétoldalú egyoldalú rögzített kétoldalú egyoldalú rögzített
összes lyukakkal lyukak nélkül
A000105 A001419 A000104 A000988 A001168 A030222 A030233 A006770
egy egy 0 egy egy egy egy egy egy
2 egy 0 egy egy 2 2 2 négy
3 2 0 2 2 6 5 6 húsz
négy 5 0 5 7 19 22 34 110
5 12 0 12 tizennyolc 63 94 166 638
6 35 0 35 60 216 524 991 3832
7 108 egy 107 196 760 3031 5931 23 592
nyolc 369 6 363 704 2725 18 770 37 196 147 941
9 1285 37 1248 2500 9910 118 133 235 456 940 982
tíz 4655 195 4460 9189 36 446 758 381 1 514 618 6 053 180
tizenegy 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

Poliformok

A poliformák  a poliominók általánosítása, amelyek sejtjei bármilyen azonos sokszög vagy poliéder lehet. Más szóval a poliforma egy lapos alak vagy térbeli test, amely egy adott alapforma több összefüggő másolatából áll [11] .

A sík (kétdimenziós) poliformák közé tartoznak az egyenlő oldalú háromszögekből kialakított poliamondok ; szabályos hatszögekből kialakított polihexek ; polyabolo , amely egyenlő szárú derékszögű háromszögekből áll, és mások.

Példák térbeli (háromdimenziós) polialakokra: polikockák, háromdimenziós kockákból állnak; polironok ( eng.  polyrhons ), rombododekaéderekből állnak [12] .

A polialakokat a magasabb dimenziók esetére is általánosítják (például a hiperkockákból - polihiperkockákból képzettek).

Feladatok

Téglalapok fedése egybevágó poliominóval

A P poliomino sorrendje a P  egybevágó másolatainak minimális száma, amely elegendő egy téglalap összehajtásához. Azoknál a poliominóknál, amelyek másolataiból nem lehet téglalapot hozzáadni, a sorrend nincs meghatározva. A P poliomino sorrendje akkor és csak akkor egyenlő 1-gyel, ha P  téglalap [13] .

Ha van legalább egy téglalap, amelyet a P páratlan számú egybevágó másolata lefedhet, a P poliominót páratlan poliominónak nevezzük ; ha a téglalap csak páros számú P példányból hajtható össze, akkor P- t páros poliominónak nevezzük .

Ezt a terminológiát 1968-ban D. A. Klarner [1] [14] vezette be .

Van egy 2. rendű poliominókészlet; példa erre az úgynevezett L - poliominók [15] .

Megoldatlan matematikai problémák : Van olyan poliomino, amelynek a sorrendje páratlan?

A 3. rendű poliominók nem léteznek; ennek bizonyítékát 1992-ben publikálták [16] . Bármely poliomino, amelynek három másolata téglalapot alkothat, maga is téglalap, és 1-es a rendje. Nem ismert, hogy létezik-e olyan poliomino, amelynek a sorrendje 3-nál nagyobb páratlan szám [14] .

Vannak 4. , 10. , 18. , 24. , 28. , 50. , 76. , 92. , 312. rendű poliominók ; létezik egy konstrukció, amely lehetővé teszi, hogy bármilyen természetes s -re 4 s - os nagyságú poliominót kapjunk [14] .

Megoldatlan problémák a matematikában : Mekkora a lehető legkisebb páratlan többszöröse egy téglalap nem téglalap alakú poliominóval való lefedésének?

Klarnernek sikerült találnia egy 2-es rendű, nem téglalap alakú poliominót, amelynek 11 példánya alkothat téglalapot [1] [14] [17] , és ennek a poliominónak nem kisebb páratlan számú példánya fedi le a téglalapot. 2015 októberében nem ismert, hogy létezik-e nem téglalap alakú poliominó, amelynek 9, 7 vagy 5 másolata téglalapot képezhet; nem ismerünk más példát olyan poliominókra, amelyek minimális páratlan többszöröse 11-es borítással rendelkezik (kivéve a Klarner által talált példát).

Minimális területek

Minimális régió ( eng. minimal region , minimal common superform ) egy adott poliominóhalmazhoz - a lehető legkisebb területű poliominók, amelyek az adott halmaz minden egyes poliominóját tartalmazzák [1] [14] [18] . A tizenkét pentominóból álló halmaz minimális területének megtalálásának problémáját először T. R. Dawson vetette fel a Fairy Chess Review című könyvében 1942-ben [18] .

Egy 12 pentominóból álló halmazhoz két minimális kilenccellás régió tartozik, amelyek az 1285 nemnominóból 2-t képviselnek [1] [14] [18] :

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

Lásd még

Jegyzetek

  1. ↑ 1 2 3 4 5 6 7 8 9 10 Golomb S. V. Polimino, 1975
  2. ↑ 1 2 Weisstein, Eric W. Polyomino  (angol) a Wolfram MathWorld webhelyén .
  3. ↑ 1 2 A sakkbástyát használó poliominók népszerű definíciója nem szigorú: a négyzetparkettának vannak szétválasztott részhalmazai, amelyeket egy bástya megkerülhet (például egy sakktábla négy négyzetből álló csoportja a1, a8, h1, h8 nem egy tetramino , bár egy bástya ezen mezők egyikén áll, három mozdulattal megkerülhet három másik mezőt). A poliominók pontosabb meghatározása a Tamerlane sakkjában használt "vezír" figura segítségével lenne : a vezír csak egy cellát mozgat vízszintesen vagy függőlegesen.
  4. ↑ Henry E. Dudeney. Canterbury Puzzles, 1975, 111–113
  5. ↑ Alexandre Owen Muñiz. Néhány szép pentomino színezési probléma . Letöltve: 2015. október 24. Az eredetiből archiválva : 2016. március 4..
  6. ↑ Gardner M. Matematikai rejtvények és szórakoztatás, 1971. - 12. fejezet. Polyomino. - 111-124. o
  7. ↑ Gardner M. Matematikai regények, 1974. - 7. fejezet. Pentominók és poliominók: öt játék és egy sor feladat. - 81-95
  8. ↑ Tudomány és Élet 2-12. (1967), 1., 6., 9., 11. (1968) stb.
  9. ↑ Poliformák . Letöltve: 2013. augusztus 22. Az eredetiből archiválva : 2015. szeptember 11..
  10. ↑ Weisstein, Eric W. Polyplet  a Wolfram MathWorld webhelyen .
  11. ↑ Weisstein, Eric W. Polyform  a Wolfram MathWorld webhelyen .
  12. ↑ ezredes Sicherman kezdőlapja. Polyform Curiosities archiválva 2014. december 14-én a Wayback Machine -nél . A Polyrhons katalógusa archiválva : 2015. szeptember 11. a Wayback Machine -nál
  13. ↑ Karl Dahlke. Téglalapok burkolása poliominóval . Letöltve: 2013. augusztus 25. Az eredetiből archiválva : 2020. február 15.
  14. ↑ 1 2 3 4 5 6 Golomb, S. V. Polyominoes : Rejtvények, minták, problémák és csomagolások  . - 2. kiadás - Princeton University Press, 1994. - ISBN 0-691-08573-0 .
  15. ↑ Weisstein, Eric W. L-Polyomino  a Wolfram MathWorld webhelyén .
  16. ↑ IN Stewart, A. Wormstein. A 3. rendű poliominók nem léteznek  //  Journal of Combinatorial Theory, Series A  : folyóirat. - 1992. - szeptember ( 61. évf. , 1. sz.). - 130-136 . o .
  17. ↑ Michael Reid. A P hexomino prímjai . Letöltve: 2015. október 24. Az eredetiből archiválva : 2016. március 22.
  18. ↑ 1 2 3 Alexandre Owen Muñiz. Polyomino Common Superforms . Letöltve: 2015. október 24. Az eredetiből archiválva : 2017. május 21..

Irodalom

Linkek


  Ugrás a Wikidata elemre  Szótárak és enciklopédiák
Bibliográfiai katalógusokban
 Poliformok
A poliformok fajtái
Polyomino a sejtek száma szerint
Rejtvények polikockákkal
Halmozási feladat
  • Pontos lefedettség probléma
  • algoritmus
  • linkek
Személyiségek
Kapcsolódó témák
Egyéb rejtvények és játékok