i
i
“Klavzar-permutacije” — 2010/6/14 — 10:05 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 16 (1988/1989)
Številka 3
Strani 159–163
Sandi Klavžar:
O IGRI PETNAJST IN PERMUTACIJAH
Ključne besede: matematika, kombinatorika, permutacije, rekreacija-
ska matematika.
Elektronska verzija: http://www.presek.si/16/930-Klavzar.pdf
c© 1988 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
o IGRI PETNAJST IN PERMUTACIJAH
Igra Petnajst je bila včasih zelo priljubljena. Okrog leta 1880 so jo igra li prav
vsi, ta ko kot pred časom razvpito Rubikovo kocko . Najbolj vnet i reševalci so
se lahko celo preizkušali na štev ilnih tekmovanjih. Med vrhuncema popular-
nosti igre Pet najst in Rubikove kocke je poteklo pribl ižno 100 let in če bi zlo-
rab ili matematično indukcijo , b i lahko zak lj uč il i, da se bo naslednja igra, ki bo
prep lavila svet, spet pojavila čez približno 100 let. Če danes pogledamo, kako
je z obema igrama , ugotovimo, da ju skoraj ne srečamo več. Le tu in tam se še
pojavita. Ravno pred kratk im sem v trafiki videl igro "Enaintr ideset", ki je igra
Petnajst z nekaj več ploščicami.
O igri Petnajst je Presek že pisal (Tomaž Pisanski : Petnajst in podobne igre,
Presek 1982-83, št . 4). Najprej se spom nimo , za katero igro gre. Na kvadratu
4 x 4 so razporejene ploščice, ki so označene s števili od 1 do 15, eno mesto pa
je prazno . Z zapored nim premikanjem poskušamo ploščice spraviti v urejen po-
ložaj. V vsakem koraku lahko premaknemo le eno izmed ploščic, ki so po stra-
nici sosednje praznemu prostorčku. Na slik i 1a je primer začetne razporeditve,
ki jo moramo spraviti v končno razporeditev na sliki 1b. Znak * na sliki ozna-
čuj e prazno mesto. V prvem ko raku lahko premaknemo le ploščico 3 ali pa 9.
Če premaknemo ploščico 3, lahko v naslednjem kora ku premaknemo ploščico
5 , 15 a li pa 3 . Tako premikamo ploščice, dokler ne pridemo do končne razpo-
redit ve ali dok ler ne obupamo .
7 14 1 11
12 2 6 8
13 4 15 9
10 5 3 "
Slika 1a
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 •
Slika 1b
Končna razpored itev je vedno taka, kot je prikazano na sliki 1b. Ker lahko
vsako razporeditev ploščic preprosto prevedemo v obliko, kjer je prazno mesto
v spodnjem desnem kotu, privzemimo, da je tudi v začetni razporeditv i prazno
mesto v spodnjem desnem kotu . V omenjenem članku Tomaža Pisanskega je
opisan algoritem, kako iz poljubne začetne razporeditve poskušamo priti do
končne razporeditve. Včasih postopek uspe, drugič pa ne. V resnici algoritem
pripel je do končne razporeditve v natanko polovici primerov in to so vsi prime-
ri, ko je igra rešljiva. Algor item je naslednji : Najprej uredimo ploščice 1,2,3,4,
5 , 6, 7 in 8. Teh ploščic ne bomo več premikali . Nato uredimo še ploščici 9 in
13, nato še 10 in 14 . Tudi teh ploščic ne premikamo več. Za urejanje nam pre-
159
ostanejo samo še p loš č i ce 11,12 in 15 . V polovici primerov jih lahko uredimo,
v ostalih pa ne.
Vprašajmo se, kako bi lahko iz začetne razporeditve ugotovili, al i je igra
rešlj iva ali ne. Z nekaj znanja o permutacijah bo od govor pre prost. To pa je tud i
zadosten raz log, da si naj prej ogledamo nekaj osnovnih dejstev o perm ut acijah,
ki so eden najpomembnejših pojmov v kombinatorik i.
o permutacijah
Imejmo n elementov, ki so urejen i v do lo čenem vrstnem redu. Ime na Ana,
Krist ina , Peter, Simon in Ž iga so na pri mer urejena po abeced i. Če ta imana
premešamo , na pri mer Simon, Žiga, Peter, Kristina , Ana , potem smo napravili
permutacijo teh imen. Odslej bomo identificiral i elemente, k i jih permut iramo ,
kar s prvimi nnaravn imi števili. Če permutacija elemente 1,2 , 3, 4, 5, 6, 7 raz -
poredi v vrstni red 3,5,7, 1, 2,4,6 bo mo to kraj še zap isal i:
(
1 234567)
3571246
V zapisu permutacije torej v zgornjo vrst ico zapišemo št evila od 1 do n, v
spodnjo pa nj ihovo razpo red it ev. Permutacijo, kjer so elementi tudi v spodnji
vrstici razporejeni od 1 do n , imenujemo identična permutacija.
Koliko je vseh permutacij f1 elementov? Takole razmislimo . Na prvem
mestu lahko stoji katerokol i izmed n števil. Ko na prvem mestu stoji neko šte-
vilo, je na d rugem mestu lahko katerokoli izmed preostalih n - 1 števil. Ko
postopek nadaljujemo, imamo na predzadnjem mestu na izbi ro še dve števili,
na zadnjem pa le še eno samo . Vseh mo žnih permutacij je torej
n . (n -- 1) . (n - 2 ) ' oo 2 .1. Dobljeno število označimo z n! (izgovarjamo n-fa-
ku/teta).
Za vajo izp iši vse permutacije t re h in štirih elementov!
Če v permutacij i med seboj zamenjamo dva elementa, potem pravimo, da
smo napravili transpozicijo. Z zaporedjem transpozicij lahko vsako permutacijo
prevedemo na identično permutacijo. Če drugače ne, potem najprej zamenja-
mo element, ki je na prvem mestu , z enico; nato element, ki je na drugem
mestu, z dvojko in tako do konca , dokler niso vsi elementi v spodnji vrstici na
pravem mestu . Na sliki 2 je primer zaporedja transpozicij. ki permutacijo
( 1 2 3 4 S ) ed id . • oo3412 S prev eVI entr čno perrnutacqo. .
/1
/'
(
12345)
34125
160
(
12345) (12345) (12345) (12345)
--+ 31425 --+ 32415 --+ 12435 --+ 12345
V našem primeru smo začetno permutacijo privedli do identične s štirimi
transpozicijami. Seveda bi lahko to naredili tudi drugače. Najmanj transpozicij
bi naredili, če bi najprej zamenjali 1 in 3, nato pa še 2 in 4. Poskušaj sedaj še
nekaj drugih zapored ij in preštej. koliko transpozicij si napravil! Gotovo si opa-
zil, da si vedno potreboval sodo število transpozicij. To ni nič presenetljivega.
Dokažemo namreč lahko , da če dano permutacijo pretvorimo v identično per-
mutacijo s sodim številom transpozicij. potem je na noben način ne moremo z
lihim in obratno . Tega ne bomo dokazovali. Dokaz lahko najdemo v knjigi
Ivana Vidava Algebra, Ljubljana 1980, na strani 63. Zaradi te lastnosti pravimo
permutacijam, ki jih spravimo do identične s sodim številom transpozicij. sode
permutscije, ostalim pa tihe perrnutecije. Sodih permutacij je ravno toliko, kot
je lihih.
Vprašajmo se, kako učinkovito določimo parnost permutacije, t.j. ali je
permutacija soda ali liha . Ugotavljanje parnosti po zgornji definiciji gotovo ni
najprimernejše; če je permutacija nekoliko daljša, moramo prepisovat i vrstice
kot nori, pa še zmotimo se lahko (če se sodokrat ni nič hudega) . Vzemimo
I d . " (123456789) P . led' k "ed" Inas e njo parrnutaci]o: 796314582 . o vrsti zas ujrno, am gr o ee-
menti permutacije: 1 gre v 7, 7 v 5 in 5 v 1. Krog je sklenjen. Naprej: 2 gre v 9
in 9 v 2. 3 gre v 6, 6 v 4 in 4 v 3. Element 8 pa gre kar sam vase. Račun zapiše-
mo takole:
(
1 2 3 .. 5 6 7 89)
7 9 6 3 1 .. 5 8 2 = (175)(29)(364)(8).
Pravimo, da smo permutacijo zapisali s tujimi cikli. Cikle imenujemo tuje, ker
vsak element permutacije nastopa v natanko enem ciklu. Vsak cikel zase je tudi
permutacija. Cikel (1 7 5) moramo razumeti takole: 1 gre v 7, 7 v 5,5 v 1, vsi
ostali elementi: 2, 3,4,6,8 in 9 pa se preslikajo vase. Skoraj očitno je, da se da
vsaka permutacija zapisati s tujimi cikli, zato tega ne bomo dokazovali.
Kako ugotovimo parnost cikla? Število elementov, ki nastopajo v zapisu
cikla, imenujemo dolžine cikla. Dokaži, ali pa vsaj na primerih preizkusi, da
velja: če je dolžina cikla sodo število, potem je cikel Iiha permutacija, sicer pa
je soda. V našem primeru so vsi cikli sodi, izjema je le cikel ( 29 ). Za vsak po-
samezen cikel znamo določiti njegovo parnost. Kako pa iz dolžin tujih ciklov
perrnutacijs ugotovimo parnost permutacije? Ko urejamo elemente v nekem
ciklu, so elementi ostalih ciklov nedotaknjeni, saj so cikli tuji! Torej ured imo
prvi cikel, drugi cikel in tako do konca . Število vseh napravljen ih transpozicij
je enako vsoti števil transpozicij po posameznih tujih ciklih .
Izpeljali smo naslednji recept za ugotavljanje parnosti. Najprej permutacijo
161
zapišemo s tujimi cikli in vsakemu ciklu pr iredimo njegovo do lžino zmanjšano
za 1. Nato števila seštejemo in če je vsota sodo število, je permutacija soda,
sicer pa liha. Na prvi pogled mo rda nekoliko zapleteno, ko pa napravite nekaj
primerov, postane postopek zelo enostaven. V gornjem prime ru imamo ra čun:
2 + 1 + 2 + O = 5, torej je permutacija liha. Še en primer: permutacijo s slike 2
zapišemo s cikl i (1 3)(2 4)(5). otrej računamo 1 + 1 + 0= 2, zato je permuta-
cija soda.
Nazaj k igri Petnajst
Sedaj že dovolj vemo o permutacijah, da uženemo igro Petnajst . Najprej začetn i
razporeditvi ploščic pri redimo permutacijo. To napravimo tako, da po vrsticah
preberemo števila na kvadratu. Začetni razporeditvi s slike 1 pripada perrnuta-
cija
(~
234
14 1 11
5 6 7 8
12 2 6 8
9
13
10 11
4 15
12
9
13 14 15
10 5 3 :)
Če koga moti * kot element permutacije, lahko * mirno zamenja s šte-
vilom 16 . Kaj se zgodi s to permutacijo, ko napravimo en premik ploščice?
Natanko ena transpozicija, kje r se zamenjata element * in neka ploščica. In
kako pridemo od začetne razporeditve do končne? Z zaporedjem t ranspozicij,
ki pa seveda niso poljubne, saj vedno premaknemo *. Če smo prišli do
končne razporeditve, potem trdimo, da smo napravili sodo število premikov
prazne ploščice. Res! Prazna ploščica je na koncu na istem mestu kot na za-
četku. Zato se je morala pomakniti navzgor tolikokrat kot navzdol in levo toli-
kokrat kot desno. Torej zaključimo. Če je permutacija, ki pripada začetni
razporeditvi (z * v spodnjem desnem kotu) , tiha, potem igra Petnajst nima
rešitve.
Permutacijo k začetni razporeditvi s slike 1 zapišemo s tujimi cikli:
(17621451291310411153)(8)(*)
Račun 13 + O + O = 13 nam pove, da je permutacija liha, torej naloga s slike 1
nima rešitve.
Igro Petnajst tako povsem obvladamo . Algoritem reševanja je na'slednji:
1. Če * ni v spod njem desnem kotu, razpored itev popravi v tako obliko.
2. Začetni oz. dobljeni razporeditvi priredi permutacijo.
3. Ugotovi parnost permutacije .
4 . Če je permutacija liha, igra nima rešitve, sicer pa z algoritmom z za-
četka članka reši nalogo .
162