Pentomina

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Vseh 18 enostranskih pentomin, vključno z zrcalnimi šestimi
Običajno označevanje pentomin z latiničnimi črkami kaže zgornja slika. Včasih črko N nadomešča črka S.[1] Drugo označevanje je Conwayjevo.
94 prostih pentapletov

Pentomína (tudi pentamína) je poliomina, ki jo sestavlja pet skladnih neprekrivajočih se enotskih kvadratov ortogonalno povezanih po stranicah. Beseda pentomina izhaja iz starogrške besede πέντε: pénte - pet in domina.

Obstaja 12 različnih prostih pentomin, ki se običajno označujejo s črkami latinične abecede, katerim so delno podobne. Praviloma pentomina, ki izhaja iz zrcaljenja ali zasuka poljubne pentomine, ne šteje za drugačen lik. Celotni množici pentomin rečemo tudi pentomino, oziroma pentamino.[1] Naslednji liki:

Nonpolyomino 001.svg Nonpolyomino 002.svg Nonpolyomino 003.svg Nonpolyomino 004.svg Nonpolyomino 005.svg Nonpolyomino 006.svg Nonpolyomino 007.svg Nonpolyomino 008.svg Nonpolyomino 009.svg Nonpolyomino 010.svg Nonpolyomino 011.svg Nonpolyomino 012.svg Nonpolyomino 013.svg Nonpolyomino 014.svg Nonpolyomino 015.svg Nonpolyomino 016.svg Nonpolyomino 017.svg Nonpolyomino 018.svg Nonpolyomino 019.svg Nonpolyomino 020.svg Nonpolyomino 021.svg Nonpolyomino 022.svg Nonpolyomino 023.svg Nonpolyomino 024.svg Nonpolyomino 025.svg Nonpolyomino 026.svg Nonpolyomino 027.svg Nonpolyomino 028.svg Nonpolyomino 029.svg Nonpolyomino 030.svg Nonpolyomino 031.svg Nonpolyomino 032.svg Nonpolyomino 033.svg Nonpolyomino 034.svg Nonpolyomino 035.svg Nonpolyomino 036.svg Nonpolyomino 037.svg Nonpolyomino 038.svg Nonpolyomino 039.svg Nonpolyomino 040.svg Nonpolyomino 041.svg Nonpolyomino 042.svg Nonpolyomino 043.svg Nonpolyomino 044.svg Nonpolyomino 045.svg Nonpolyomino 046.svg Nonpolyomino 047.svg Nonpolyomino 048.svg Nonpolyomino 049.svg Nonpolyomino 050.svg Nonpolyomino 051.svg Nonpolyomino 052.svg Nonpolyomino 053.svg Nonpolyomino 054.svg Nonpolyomino 055.svg Nonpolyomino 056.svg Nonpolyomino 057.svg Nonpolyomino 058.svg Nonpolyomino 059.svg Nonpolyomino 060.svg Nonpolyomino 061.svg Nonpolyomino 062.svg Nonpolyomino 063.svg Nonpolyomino 064.svg Nonpolyomino 065.svg Nonpolyomino 066.svg Nonpolyomino 067.svg Nonpolyomino 068.svg Nonpolyomino 069.svg Nonpolyomino 070.svg Nonpolyomino 071.svg Nonpolyomino 072.svg Nonpolyomino 073.svg Nonpolyomino 074.svg Nonpolyomino 075.svg Nonpolyomino 076.svg Nonpolyomino 077.svg Nonpolyomino 078.svg Nonpolyomino 079.svg Nonpolyomino 080.svg Nonpolyomino 081.svg Nonpolyomino 082.svg

niso pentomine, saj so vsaj enkrat povezani le z ogliščema.[2] Takšni liki, imenovani nepentomine, skupaj s prostimi pentominami tvorijo množico likov, imenovanih (prosti) pentapleti. Pentapleti se pojavljajo v Conwayjevi igri življenja.

Pentomine F, L, N, P, Y in Z so hiralne v 2 razsežnostih. Če dodamo njihove zrcalne podobe (F', J, N', Q, Y', S), dobimo 18 enostranskih pentomin. Druge, označene z I, T, U, V, W in X, so enakovredne njihovim zavrtenim zrcalnim likom. To je pomembno v nekaterih računalniških igrah, kjer premiki zrcalnih podob niso dovoljeni, na primer v klonih Tetrisa in arkadni igri Rampart. Pentomine se poleg tetromin in drugih manjših likov pojavljajo v računalniški igri Pentix.

Z vsako od 12-tih pentomin se lahko pokrije ravnino. Vsaka hiralna pentomina lahko pokrije ravnino brez zrcaljenj.[3]

Conway je pentomine označeval drugače. Namesto I je pisal O, Q namesto L, R namesto F in S namesto N. Podobnost črkam je še bolj nenaravna (še posebej, ker je »O« raven lik, in ni podoben dejanski črki O). Prednost njegovega označevanja je v tem, da uporablja 12 zaporednih črk abecede. Ta shema se uporablja v povezavi z igro življenja, in tako govori o pentomini R namesto pentomine F.

Pri običajnem označevanju si lahko zapomnimo le zadnji del abecede (TUVWXYZ) in besedo FiLiPiNo.[4] Velikokrat velja prepričanje, da je 5 tetromin premalo, 35 heksomin pa preveč, tako, da je 12 pentomin ravno prav.[5]

Simetrija[uredi | uredi kodo]

12 prostih pentomin, pobarvanih glede na njihovo simetrijo

Če upoštevamo zasuke mnogokratnikov le pod kotom 90°, obstajajo naslednje simetrijske kategorije:

  • pentomine F, L, N, P in Y nimajo simetrije. Lahko jih obrnemo na 8 načinov: 4 z zasukom in še 4 z zrcalnimi podobami. Njihovo simetrijsko grupo sestavlja le identična preslikava.
  • pentomini T in U lahko obrnemo na 4 načine z zasukom. Njuna os zrcalne simetrije je poravnana z mrežnimi črtami. Njuna simetrijska grupa ima dva elementa, identiteto in zrcaljenje vzdolž črte vzporedne daljicam kvadratov.
  • tudi pentomini V in W lahko obrnemo na 4 načine z zasukom. Njuna os zrcalne simetrije leži pod kotom 45° glede na mrežne črte. Njuna simetrijska grupa ima dva elementa: identiteto in diagonalno zrcaljenje.
  • pentomino Z lahko obrnemo na 4 načine: 2 z zasukom in še 2 z njegovima zrcalnima podobama. Ima točkovno simetrijo, znano tudi kot rotacijska simetrija reda 2. Njegova simetrijska grupa ima dva elementa: identiteto in zasuk pod kotom 180°.
  • pentomino I lahko obrnemo na 2 načina z zasukom. Ima dve osi zrcalne sismetrije, obe poravnani z mrežnimi črtami. Njegova simetrijska grupa ima štiri elemente: identiteto, dve zrcaljenji in zasuk pod kotom 180°. To je diedrska grupa reda 2, znana tudi kot Kleinova štirikratna grupa.
  • pentomino X lahko obrnemo le na en način. Ima štiri osi zrcalne simetrije, poravnane z mrežnimi črtami in diagonalami, ter rotacijsko simetrijo reda 4. Njegova simetrijska grupa, diedrska grupa reda 4, ima osem elementov.

Če ločujemo zrcaljenja pentomin, kot pri enostranskih pentominah, sta prva in četrta kategorija dvakrat večji, kjer dobimo dodatnih 6 pentomin od skupnih 18. Če ločujemo tudi zasuke, potem moramo pentomine v prvi kategoriji šteti osemkrat, pentomine v naslednjih treh kategorijah (T, U, V, W, Z) štirikrat, pentomino I dvakrat in X le enkrat. Tako dobimo 5 · 8 + 5 · 4 + 2 + 1 = 63 negibnih pentomin.

Naslednje slike prikazujejo osem različnih obrnitev pentomin F, L, N, P in Y:

F-pentomino Symmetry.svgL-pentomino Symmetry.svg  N-pentomino Symmetry.svgP-pentomino Symmetry.svgY-pentomino Symmetry.svg

Za dvorazsežne like sta v splošnem še dve kategoriji:

  • lahko jih obrnemo na 2 načina z zasukom pod kotom 90°, z dvema osema zrcalne simetrije, obema poravnanima z diagonalami. Takšna vrsta simetrije zahteva vsaj heptomino.
  • lahko jih obrnemo na 2 načina, kot sami sebi zrcalni podobi, na primer svastika. To je rotacijska simetrija reda 4. Ta vrsta simetrije zahteva vsaj oktomino.

Pokrivanje pravokotnikov in kvadratov[uredi | uredi kodo]

Zgledi pokrivanj

S pentominami je povezanih veliko ugank in problemov. Standardna pentominska uganka je pokrivanje pravokotnika s pentominom, tako da se pentomine ne prekrivajo med seboj in da v pravokotniku ni praznih mest. Vsaka od 12-tih pentomin ima površino 5 enot, tako da mora imeti pravokotnik površino 60 enot. Možne velikosti so 6 × 10, 5 × 12, 4 × 15 in 3 × 20. Spretni reševalci lahko verjetno rešijo te probleme na roko v nekaj urah. Bolj zapletena naloga, ki običajno zahteva računalniško iskanje, pa je štetje skupnega števila rešitev za vsak primer.

Primer 6 × 10 sta prva rešila leta 1960 Colin in Jenifer Haselgrove.[6] Obstaja točno 2339 rešitev, brez trivialnih različic, ki jih dobimo z zasukom ali zrcaljenjem celega pravokotnika, in z upoštevanjem zasuka in zrcaljenja podmnožice pentomin (kar nam včasih da dodatno rešitev na preprost način).

Primer 5 × 12 ima 1010 rešitev, 4 × 15 ima 368 rešitev, 3 × 20 pa le 2 rešitvi (ena je prikazana na sliki, drugo lahko dobimo, če zasučemo cel blok, ki vsebuje pentomine L, N, F, T, W, Y in Z).

Malo lažjo (bolj simetrično) uganko, pokritje kvadrata 8 × 8 z luknjo 2 × 2 v sredini, je rešil Scott leta 1958.[7] Obstaja 65 rešitev. Scottov algoritem je eden prvih uporab programa z vračanjem. Zgled vseh devetnajstih pokritij kvadrata 8 × 8, kjer je pentomina X na mestu:

Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8 Pokritje kvadrata 8 × 8

V različicah te uganke se lahko luknje postavijo poljubno. Veliko takšnih vzorcev je rešljivih, z izjemo, da se vsak par lukenj ne sme postaviti blizu kota kvadrata, tako da lahko kot zasede le pentomina P, ali da v kot postavimo pentomini T ali U, kjer nastane nova luknja. Zgled nerešljive pentominske uganke

Za reševanje takšnih problemov so opisali učinkovite algoritme, na primer Knuth.[8] Če jih poženemo na sodobni računalniški opremi, lahko te pentominske uganke rešimo v nekaj sekundah.

Pentominos par pol square 11x11 001.svg Pentominos par pol square 11x11 002.svg
Zgled dveh pokritij kvadrata 11 × 11 s štirimi luknjami 2 × 2 z »vzporedno polarizirano« množico 21-ih pentomin

Pentomine v književnosti[uredi | uredi kodo]

Pentomine, še posebej rešitev pravokotnika 3 × 20 ([UXPI][LNFTWYZ]V), je v svojem znanstvenofantastičnem romanu Imperial Earth, objavljenem leta 1975, predstavil Clarke. Upal je tudi, da bodo predstavljene tudi v filmu 2001: Vesoljska odiseja, vendar je prevladal šah.[9] V svojem otroškem romanu Chasing Vermeer iz leta 2003, ki ga je ilustriral Helquist, jih je predstavila tudi Balliettijeva. Prav tako v nadaljevanjih romana, The Wright 3 in The Calder Game.

Glej tudi[uredi | uredi kodo]

Opombe in sklici[uredi | uredi kodo]

  1. ^ 1,0 1,1 Batagelj (1974).
  2. ^ Potočnik (2002).
  3. ^ Gardner (1975).
  4. ^ Golomb (1996).
  5. ^ Martin (1991).
  6. ^ Haselgrove (1960).
  7. ^ Scott (1958).
  8. ^ Knuth, Donald. "Dancing links" (v angleščini).  (Postscript, 1,6 MB). Vsebuje povzetek Scottovega in Fletcherjevega članka.
  9. ^ "More about Polyominoes and Polycubes". Kadon Enterprises, Inc. (v angleščini). Pridobljeno dne 2011-08-05. 

Viri[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]