Poliòmino
Un poliòmino és un objecte geomètric obtingut en unir diversos quadrats o cel·les de la mateixa mida de manera que cada parell de cel·les veïnes comparteixin un costat. Els poliòminos són, per tant, un cas especial de poliformes.
El terme poliòmino (en anglès: polyomino) s'originà en una conferència de Solomon W. Golomb per al Harvard Mathematics Club el 1953, la qual va ser publicada posteriorment a l'American Mathematical Monthly i en l'exemplar de maig de 1957 de Scientific American.[1] Els poliòminos són una generalització de la forma d'un dòmino, consistent en dos quadrats units per un costat (sense fer atenció al seu contingut).
Classificació
[modifica].gif)
Monòmino
[modifica]El monòmino correspon a un únic quadrat, així que només hi ha una configuració possible. Tot i que tècnicament no és considerat un poliòmino, s'inclou igualment a la llista al definir els grups de -òminos on és qualsevol enter positiu.
Dòmino
[modifica]El dòmino conté dos quadrats, i només una configuració possible.[1] Com que té simetria de reflexió, també és l'únic dòmino unilateral (amb reflexos considerats diferents). Quan les rotacions també es consideren diferents, hi ha dues figures: la segona es pot crear girant la primera 90°.[2][3]
Els dòminos poden recobrir un pla en un nombre comptablement infinit de maneres. El nombre de recobriments d'un rectangle 2×n amb dòminos és , el n-èssim nombre corresponent a la successió de Fibonacci.[4]
Els tessel·lats mitjançant dòminos apareixen en diversos problemes famosos, incloent el problema del diamant asteca en què les grans regions en forma de diamant tenen un nombre de dòminos igual a una potència de dos,[5] amb la majoria de mosaics que apareixen a l'atzar dins d'una regió circular central i que tenen una estructura més regular fora d'aquest "cercle polar àrtic", i el problema de l'escaquer mutilat, en què treure dues cantonades oposades d'un tauler d'escacs fa impossible enrajolar-la amb dòminos.[6]
Triòmino
[modifica]Els triòminos contenen tres quadrats. Quan les rotacions i els reflexos no es consideren formes diferents, només hi ha dos triòminos lliures diferents: "I" i "L" (la forma "L" també s'anomena "V"), i tots dos tenen simetria de reflexió.[7]
Tots dos tipus de triòmino poden ser disseccionats geomètricament en triòminos més petits del mateix tipus, per qualsevol enter .[8] Aplicant aquesta dissecció de manera recursiva s'obté un recobriment del pla, que en molts casos és un tissel·lat aperiòdic.[9]
Motivat pel problema de l'escaquer mutilat, Golomb va utilitzar aquest mosaic com a base per al que es coneix com teorema del triòmino de Golomb: si qualsevol quadrat és eliminat d'un tauler de 2n × 2n, el tauler resultant pot ser completament recobert amb L-triòminos. Per demostrar això mitjançant inducció matemàtica, es parteix el tauler en quadrants de mida 2n−1 × 2n−1 que contenen el quadrat eliminat, i un triòmino més gran format per els altres tres quadrants. El triòmino pot ser disseccionat recursivament a triòminos fins a la unitat, i la dissecció del quadrant amb el quadrat eliminat segueix la hipòtesi per inducció. Contràriament, quan un escaquer d'aquesta mida té un quadrat eliminat, no sempre és possible recobrir-lo amb I-triòminos.[10]
Tetròmino
[modifica]Els tetròminos contenen quatre quadrats, i sense comptar rotacions ni reflexions n'hi ha 5 de diferents. El joc Tetris es basa en aquests 5 tipus de tetròminos.[11]
Pentòmino
[modifica]Els pentòminos contenen cinc quadrats, i sense comptar rotacions ni reflexions n'hi ha 12 de diferents. Cadascun dels 12 pentòminos satisfà el criteri de Conway, és a dir, és capaç d'omplir el pla.[12] De fet, cada pentòmino pot omplir el pla sense ser reflectit.[13]
Hexòmino
[modifica]Els hexòminos contenen sis quadrats, i sense comptar rotacions ni reflexions n'hi ha 35 de diferents. Igual que en el cas dels pentòminos, cadascun dels 35 pentòminos satisfà el criteri de Conway.[12] Ara bé, a diferència de amb els pentòminos, tot i que un conjunt complet dels 35 hexòminos té un total de 210 quadrats, no és possible empaquetar-los en un rectangle. Això és demostrable emprant un argument de paritat. Si els hexòminos es col·loquen sobre un patró de quadres, llavors 11 dels hexòminos cobriran un nombre parell de quadrats negres (2 blancs i 4 negres o viceversa) i els altres 24 hexòminos cobriran un nombre senar de quadrats negres (3 blancs) i 3 negres). En general, es cobrirà un nombre parell de caselles negres en qualsevol cas. No obstant això, qualsevol rectangle de 210 quadrats tindrà 105 quadrats negres i 105 quadrats blancs i, per tant, no pot estar cobert pels 35 hexòminos.
Si es fa un desenvolupament pla d'un cub, s'obté forçosament un hexòmino.
Poliòminos de mida superior
[modifica]Segons s'incrementa s'obtenen heptòminos, octòminos, nonòminos, decòminos, undecòminos, dodecòminos, i així successivament. A partir dels heptòminos no totes les combinacions satisfan el criteri de Conway.[14] A més, a partir dels heptòminos poden aparèixer combinacions amb forats.
Referències
[modifica]- ↑ 1,0 1,1 Golomb, Solomon W. Polyominoes (en anglès). Nova York: Charles Scribner's Sons, 1965, p. 13. LOC 64-24805. OCLC 982644 [Consulta: 28 juny 2010].
- ↑ Weisstein, Eric W. «Domino». From MathWorld – A Wolfram Web Resource. [Consulta: 5 desembre 2009].
- ↑ Redelmeier, D. Hugh «Counting polyominoes: yet another attack». Discrete Mathematics, vol. 36, 1981, pàg. 191–203. DOI: 10.1016/0012-365X(81)90237-5.
- ↑ Concrete Mathematics Arxivat 2020-11-06 a Wayback Machine. by Graham, Knuth and Patashnik, Addison-Wesley, 1994, p. 320, ISBN 0-201-55802-5
- ↑ Elkies, Noam; Kuperberg, Greg & Larsen, Michael et al. (1992), "Alternating-sign matrices and domino tilings. I", Journal of Algebraic Combinatorics 1 (2): 111–132, DOI 10.1023/A:1022420103267
- ↑ Mendelsohn, N. S. (2004), "Tiling with dominoes", The College Mathematics Journal (Mathematical Association of America) 35 (2): 115–120, DOI 10.2307/4146865.
- ↑ Weisstein, Eric W., «Triomino» a MathWorld (en anglès).
- ↑ Nițică, Viorel (2003), "Rep-tiles revisited", MASS selecta, Providence, RI: American Mathematical Society, pàg. 205–217.
- ↑ Robinson, E. Arthur, Jr. «On the table and the chair». Indagationes Mathematicae, vol. 10, 4, 1999, pàg. 581–599. DOI: 10.1016/S0019-3577(00)87911-2..
- ↑ Golomb, S. W. «Checker boards and polyominoes». American Mathematical Monthly, vol. 61, 1954, pàg. 675–682. DOI: 10.2307/2307321..
- ↑ "About Tetris", Tetris.com. Retrieved 2014-04-19.
- ↑ 12,0 12,1 Rhoads, Glenn C. Planar Tilings and the Search for an Aperiodic Prototile. PhD dissertation, Rutgers University, 2003.
- ↑ Gardner, Martin «More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes». Scientific American, vol. 233, 2, 8-1975, pàg. 112–115.
- ↑ Rhoads, Glenn C. «Planar tilings by polyominoes, polyhexes, and polyiamonds». Journal of Computational and Applied Mathematics, vol. 174, 2, 2005, pàg. 329–353. DOI: 10.1016/j.cam.2004.05.002.
