Pentomina
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. Celotna množica pentomin se imenuje tudi pentomino, oziroma pentamino. Naslednji liki:

                                                                                 

niso pentomine, saj so vsaj enkrat povezani le z ogliščema. 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 kiralne v 2 razsežnostih. Če se doda njihove zrcalne podobe (F', J, N', Q, Y', S), se dobi 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-ih pentomin se lahko pokrije ravnino. Vsaka kiralna pentomina lahko pokrije ravnino brez zrcaljenj.

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 se lahko zapomni le zadnji del abecede (TUVWXYZ) in besedo FiLiPiNo. Velikokrat velja prepričanje, da je 5 tetromin premalo, 35 heksomin pa preveč, tako da je 12 pentomin ravno prav.

Simetrija 

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

 pentomine F, L, N, P in Y nimajo simetrije. Lahko se jih obrne 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 se lahko obrne 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 se lahko obrne 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 se lahko obrne 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 se lahko obrne na 2 načina z zasukom. Ima dve osi zrcalne sismetrije, obe poravnani z mrežnimi črtami. Njena 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 se lahko obrne le na en način. Ima štiri osi zrcalne simetrije, poravnane z mrežnimi črtami in diagonalami, ter rotacijsko simetrijo reda 4. Njena simetrijska grupa, diedrska grupa reda 4, ima osem elementov.

Če se ločuje zrcaljenja pentomin, kot pri enostranskih pentominah, sta prva in četrta kategorija dvakrat večji, kjer se dobi dodatnih 6 pentomin od skupnih 18. Če se ločuje tudi zasuke, potem je treba 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 se dobi 5 · 8 + 5 · 4 + 2 + 1 = 63 negibnih pentomin.

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

  

Za dvorazsežne like sta v splošnem še dve kategoriji:
 lahko se jih obrne 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 se jih obrne 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 

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-ih 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. Obstaja točno 2339 rešitev, brez trivialnih različic, ki se jih dobi z zasukom ali zrcaljenjem celega pravokotnika, in z upoštevanjem zasuka in zrcaljenja podmnožice pentomin (kar včasih da dodatno rešitev na preprost način). Te rešitve se lahko razdelijo v 911 ekvivalenčnih razredov glede na tri podobnostne transformacije.

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 se lahko dobi, če se zasuče 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. 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:

                  

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 se v kot postavi pentomini T ali U, kjer nastane nova luknja. 

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

Pentomine v književnosti 

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, da bodo predstavljene tudi v filmu 2001: Vesoljska odiseja, vendar je prevladal šah.

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 

 Lonpos

Sklici

Viri

Zunanje povezave 

 
 Gerard's Pentomino Page 

Matematične igre
Poliforme
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 . Obstajarazlič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 . Celotna množica pentomin se imenuje tudi pentomino , oziroma pentamino . Naslednji liki : niso pentomine , saj so vsaj enkrat povezani le z ogliščema . 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 kiralne vrazsežnostih . Če se doda njihove zrcalne podobe ( F' , J , N' , Q , Y' , S ) , se dobienostranskih 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 odih pentomin se lahko pokrije ravnino . Vsaka kiralna pentomina lahko pokrije ravnino brez zrcaljenj . 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 uporabljazaporednih č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 se lahko zapomni le zadnji del abecede ( TUVWXYZ ) in besedo FiLiPiNo . Velikokrat velja prepričanje , da jetetromin premalo ,heksomin pa preveč , tako da jepentomin ravno prav . Simetrija Če se upošteva zasuke mnogokratnikov le pod kotom , obstajajo naslednje simetrijske kategorije : pentomine F , L , N , P in Y nimajo simetrije . Lahko se jih obrne nanačinov :z zasukom in šez zrcalnimi podobami . Njihovo simetrijsko grupo sestavlja le identična preslikava . pentomini T in U se lahko obrne nanač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 se lahko obrne nanačine z zasukom . Njuna os zrcalne simetrije leži pod kotom glede na mrežne črte . Njuna simetrijska grupa ima dva elementa : identiteto in diagonalno zrcaljenje . pentomino Z se lahko obrne nanačine :z zasukom in šez njegovima zrcalnima podobama . Ima točkovno simetrijo , znano tudi kot rotacijska simetrija reda Njegova simetrijska grupa ima dva elementa : identiteto in zasuk pod kotom . pentomino I se lahko obrne nanačina z zasukom . Ima dve osi zrcalne sismetrije , obe poravnani z mrežnimi črtami . Njena simetrijska grupa ima štiri elemente : identiteto , dve zrcaljenji in zasuk pod kotom . To je diedrska grupa reda znana tudi kot Kleinova štirikratna grupa . pentomino X se lahko obrne le na en način . Ima štiri osi zrcalne simetrije , poravnane z mrežnimi črtami in diagonalami , ter rotacijsko simetrijo reda Njena simetrijska grupa , diedrska grupa reda ima osem elementov . Če se ločuje zrcaljenja pentomin , kot pri enostranskih pentominah , sta prva in četrta kategorija dvakrat večji , kjer se dobi dodatnihpentomin od skupnih Če se ločuje tudi zasuke , potem je treba 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 se dobi · + · ++ =negibnih pentomin . Naslednje slike prikazujejo osem različnih obrnitev pentomin F , L , N , P in Y : Za dvorazsežne like sta v splošnem še dve kategoriji : lahko se jih obrne nanačina z zasukom pod kotom , z dvema osema zrcalne simetrije , obema poravnanima z diagonalami . Takšna vrsta simetrije zahteva vsaj heptomino . lahko se jih obrne nanačina , kot sami sebi zrcalni podobi , na primer svastika . To je rotacijska simetrija reda Ta vrsta simetrije zahteva vsaj oktomino . Pokrivanje pravokotnikov in kvadratov 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 odih pentomin ima površinoenot , tako da mora imeti pravokotnik površinoenot . Možne velikosti so× × ×in× 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×sta prva rešila letaColin in Jenifer Haselgrove . Obstaja točnorešitev , brez trivialnih različic , ki se jih dobi z zasukom ali zrcaljenjem celega pravokotnika , in z upoštevanjem zasuka in zrcaljenja podmnožice pentomin ( kar včasih da dodatno rešitev na preprost način ) . Te rešitve se lahko razdelijo vekvivalenčnih razredov glede na tri podobnostne transformacije . Primer×imarešitev , ×imarešitev , ×pa lerešitvi ( ena je prikazana na sliki , drugo se lahko dobi , če se zasuče cel blok , ki vsebuje pentomine L , N , F , T , W , Y in Z ) . Malo lažjo ( bolj simetrično ) uganko , pokritje kvadrata×z luknjo×v sredini , je rešil Scott leta Obstajarešitev . Scottov algoritem je eden prvih uporab programa z vračanjem . Zgled vseh devetnajstih pokritij kvadrata × kjer je pentomina X na mestu : 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 se v kot postavi pentomini T ali U , kjer nastane nova luknja . Za reševanje takšnih problemov so opisali učinkovite algoritme , na primer Knuth . Če se jih požene na sodobni računalniški opremi , se lahko te pentominske uganke reši v nekaj sekundah . Pentomine v književnosti Pentomine , še posebej rešitev pravokotnika× ( [ UXPI ] [ LNFTWYZ ] V ) , je v svojem znanstvenofantastičnem romanu Imperial Earth , objavljenem leta predstavil Clarke . Upal je , da bodo predstavljene tudi v filmu Vesoljska odiseja , vendar je prevladal šah . V svojem otroškem romanu Chasing Vermeer iz leta ki ga je ilustriral Helquist , jih je predstavila tudi Balliettijeva . Prav tako v nadaljevanjih romana , The Wrightin The Calder Game . Glej tudi Lonpos Sklici Viri Zunanje povezave Gerard's Pentomino Page Matematične igre Poliforme