i
i
“629-Pisanski-naslov” — 2009/6/10 — 8:58 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 10 (1982/1983)
Številka 4
Strani 163–168
Tomaž Pisanski:
PETNAJST IN PODOBNE IGRE
Ključne besede: matematika.
Elektronska verzija: http://www.presek.si/10/629-Pisanski.pdf
c© 1983 Društvo matematikov, fizikov in astronomov Slovenije
c© 2009 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.
PETNAJST IN PODOBNE IGRE
I gr a "Petnaj st" je dobro po-
znan a s t a r e jš i m bralcem . Ker
pa je morda le vs i ne poznate,
jo bom op isa l . Na kvadratu 4x4
lež i 15 ploščic ve likos ti l xl,
en kvadratek pa je pra zen .
P loščice so o štev i lčene s
števi 1kami od 1 do 15 . Na l o qa :
s premik anjem ploščic dobi ti
"urejen" polož aj, ki ga prik a -
zu je s l i ka 1. '
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 ,.
Sl ika 1
če igre nimaš doma, Sl JO la-
hko sam napraviš . Iz papir j a
izreži majhne kvadratke in jih
oš tevi lči. P loščo si nar iši na
drugem kosu papirja . (slika 2 )
MATEMATIKA
00~ ....~\---+----+------+---l
C:J8 1----+---+- +_-1
Sl ika 2
Re cimo, da je začetni položaj
t ak, ko t ga kaže s l i ka 3 :
1 2 3 4
5 6 7 8
9 10 11 12
14 15 13 ,.
Slika 3
Kako b i pr i šli do končnega,
urejenega položaja? Prvih dveh
vrst ic ne bo mo spreminj ali,
zat o jih na sl iki ne bomo niti
pokaza li . Eno možno rešite v
kaže s l i ka 4 :
163
Slika 4
Poglejmo še enkrat rešitev na slik i 4. Iz začetnega položaja na
s liki 3 smo po nekaj potezah prešli v končni položaj (k i ga ka-
že slika 1) . Poteze moremo uganiti iz sosednjih "položaje v. V
prvi potezi smo kvadratek 12 premaknil i na vzdol. V naslednji
potezi smo kvadratek 11 premaknili na desno. Potezo lahko nata-
nčno pop išemo že s kvadratkom, ki ga premikamo . Tako je tretja
poteza do ločena že s tem, da povemo, da bomo premaknili kvadra-
tek 13 . Mesto, na katero ga bomo premakn ili, je namreč popolno-
ma določeno - premakniti ga moramo na mesto preznega kvadratka .
Premikamo lahko le ploščice na kvadratkih, ki so sosednji praz-
nemu mestu. V vsakem trenutku imamo torej največ 4 možne poteze
(če je prazni kvadratek v sredini p lošče). če je prazni kvadra-
tek na robu, imamo le 3 možne pote ze in če je v vogalu le dve
možni potezi . V našem začetnem položaju na sliki 3 imamo le dve
možni potezi : 12 in 13 . Rešitev, ki jo kaže slika 4, lahko zdaj
na kratko popišemo z začetnim položajem (slika 3) in z zapored -
jem potez :
12-11-13 -15 -14 -9-10 -13-11-12 - 15-14 -13 -10-9 -1 3-14 -15.
Za reši tev smo potreboval i 18 potez. Zdaj pa
si lahko zas tavimo dve zan imivi vprašanji:
ALi j e mogo če i z v sakega začetnega poLo žaja
doseči končni poLoža j?
ALi z namo na jti praviLo , ki nam bo povedaLo ,
kako i z danega začetnega poLožaja doseči
končni poLožaj?
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 '"
164 Slika 5
Odgovor na prvo vprašanje je ne! Iz položaja na sliki 5 ni
mogoče doceči končnega položaja. Se več! Vsi možni položaji ra -
zp~dejo na dve množici, označimo ju z O i n S. Iz vsakega po lo -
žejev množice O je mogoče doseči vsak drug položaj iz množice
O, med drugim tudi končni položaj na sliki 1 . Iz vsakega polo -
žaja množice S je mogoče doseči vsakega drugega iz S in obratno.
To trditev bi lahko dokazali s permutacijami, vendar ji bomo mi
kar verjel i. Kdor pa le ne verjame, naj pogleda v knj i go J. I.
Pereljmana: Zanimiva matematika . Z odgovorom na prvo vprašanje
si pri igranju žal ne moremo kaj dosti pomaqa t i . Kako pa naj
vemo, kateri začetni položaj leži v množici O?
Morda pa bo odgovor na drugo vprašanje bolj konstruktiven . Pre-
den se lotimo raziskave tega vprašanja, si oglejmo celo družino
sorodnih iger. Igro pe tnajst lahko namreč posp lošimo . Namesto
da jo igramo na tabl i 4x4, lahko podobno nalogo zastavimo na ta -
bli 6x6 ali 4x5 oziroma v splošnem na tabli mxn . Pri tem sta m
in n poljubni vnaprej izbrani števili. En kvadratek imamo pra -
zen, ostalih mn - 1 kvadratkov pa oštevi lč imo s štev ili 1,2,
3, ... , mn - 1. Končni položaj ima v splošnem obliko:
n +
(m-2)n +
(m -1)n +
2
n + 2
(m -2)n + n-1
(m -1)n + n-1
Slika 6
n
2n
(m-2)n + n
*
Zaradi simetrije lahko obravnavamo le primere,ko je število
stolpcev večje ali enako številu vrstic. Primer m = 1 najprej.
če je tudi n = 1, igra ni zanimiva; imamo en sam kvadratek, pa
še ta je prazen. Ce je n d 2, sta oba položaja v množici o.
Pri n = 3 je igra bolj zanimiva, imamo namreč 6 možnih položa-
jev:
165
Prv i tr i je so v O, dr ug i trij e pa v S . če je n več kot 3 , pr i de
do sit uac i j e , ki je dos lej še ni s mo i me li. Dobim o v e č ko t sa mo
dve mn oži ci. Pr i vsa ke m m dobim o (m - 1) ! = (m - 1)(m -2) . .. 3 ·2· 1
mn oži c po lo žajev . V vsak i je po m po ložaje v .
i n vse možne položaje , v kate re la hko iz njega
Zdaj pa si og lejmo i gr e , pri kater i h je
mo 4! = 4 ·3 ·2·1 = 24 položajev. Oglej mo
n = 2 . Pr i m = 2
si po lo žaj : IJTIJ
[I[!J
pridem o.
i ma -
ITI2J[IE]IJTIJC!TIJUEJ[ffi]f2T3lr;r3][lli][]]JJ[]]JJ@TI
[I[!JQII] 0]]ITIIJ[]]]JDEJ[ill] (I[JJ[ITjJ[I[!J[!IIJDTIJ
po loža jev, v ka te re l ah ko pr i de-
prid emo v ka terega ko l i i zme d
Skra t ka, dobi mo ravno dvanajs t
mo . I z pol oža j a ~1 pa l ah ko
3 •
preosta l i h dvanajs položa j e v . Spet imamo l e dve množic i O in S .
Pr av got ovo je mogoče pr i vsaki igri mxn pre i t i i z končnega v
začetn i po ložaj , če j e mogoč e preit i iz za č e tne g a v končni, l e
zapore dje pot ez mo ramo obr n i t i. Ta ko nas zapo r e dje
15-1 4- 13- 9-10-1 3-14-1 5-1 2-11-1 3-10-9-14-1 5- 13-11 -1 2
prip e lj e iz po l ož aja na s l i ki 1 v po ložaj na sl ik i 3 .
Č as je, da si og l e da mo nasl ed nj o i gr o 2x3 . Re cim o, da j e z ač e t-
ni po ložaj t a kl e :
na svoje
QDJDJD . Najpre j bomo poskusi l i s p r avi t i 1
8IOJ
mesto . Ke r enice ne moremo premakni ti, bomo najprej *
e nico , vendar t a ko,
Zdaj l ah ko enic e pre-QDJDJDQDJDJD
l!l.ffiJ l1EIJJ
Spe t pripeljemo * p r ed
pr ip e l ja l i kenic i:
maknemo : QDJDJD .
rn:II!J
da en i ce pr i tem ne premik amo : QDJDJD~[lli]]] CBII]] illIII]
[ffil!J illlIlJ illillJ [I]J]1J [ill]]]
16 6
Pr e makn emo e ni co : [l]"±I]]
DEIIl
Zdaj bomo sp razni mi mes t o na d e ni co: I1II[[] [l"[!]]] C!III]]
DEIIl !JIillJ !JIillJ
še e na pot e za i n enica je na s voj e m mestu : CCCDJD
C!IillJ
Na sled nj a na l oga je prip el j at i š ter ico na s voj e mesto. V na šem
pri me r u n i tež ka. f1T2J]J . Pr vi ~ to lpec j e že dobe r . Ostal nam
rn:TITI
je š e kvad ra t 2x2 , ki ga užen emo podobno kot smo to že prej de -
lali . Iz []]]] že li mo dobiti [l"I1] . če s e š e s pomni mo našeg a
[ill] [[El
r a zmiš lj anj a ob nalog i 2x2 , vemo, da j e v 12 pr ime r ih na l oga
r eš l jiv a , v pre os t al ih 12 primer ih pa ni. ža l j e naš primer med
ner e š ljivim i . Zdaj pa že lahk o povemo, kako se da re šiti vsako
nal ogo na des ki 2xn . če je n = 2 , j o re šimo t ako, kot smo že
pov eda l i. č e je n več ko t dv a, pa na jprej post avimo prvi stol -
pe c v pravi lni pol ož a j in na t o r eš imo nal ogo s preos ta l imi pl oš-
č i cam i na des ki 2x( n- l) . To pomeni , da s pr e vimo drugi s t ol pe c v
pra vilni pol ožaj, za t em tretji in tako naprej, dokler nam ne
ost an e na lo ga na des ki 2x2. Tak o l ahko užen emo vs ako nal ogo ob-
l ike 2x n . Kaj pa nal oge ob) ike 3xn? Tu.gre č is to pod obno .Naj -
prej postav imo kva dr a t ke 1 , 2, 3 , . . . , n V pra viln em vr stnem
redu v pr vo vrs tic o , za tem pa v dru gih dveh vrsticah rešimo
nal oge 2xn . t a ko kot smo že poveda l i. še majhen korak in zna l i
bomo re šiti vs ak o na l ogo obl i ke mXn . Takole napra vimo :
Ur edi mo naj p re j pr vo vrs t ico
( pos tav imo 1, 2 , . . . , n na pr a-
va me sta) , za t em pa re šim o na-
l ogo (m-1) xn . Nas led nja sl ik a
kaže, v kak šnem zaporedju pri-
pelje mo po t em pr a vi l u kva dr at -
ke na s voj e prava me sta pr i
i gr i pet naj st.
Pr i tem, ko " pel j emo kvadratek
na sv oje mesto", ne smemo v e č Sl i ka 8
167
p r e mi kati kva d ratkov , k i smo
j i h že "pr ipeljali na svoje
mesto ".
Ogleda l i smo s i družino iger
o z i ro ma na log , k i so podobne
i gr i petnajs t (mi j o reje i me-
n uj e mo i g r a 4x4). Do ka z al i n i -
smo t u ni česar . Spoz na l i pa s mo
pravi lo al i , kot bi t e mu r ekli
ma t e matik i, a l g o r i t em,
k i reš i vsak o i gr o ~ xn ( m i n n
ve č ja kot 1 ) tak o, d a jo v kon -
čn i fazi prevede na i g r o 2x 2 .
če i ma mo s rečo i n je i g r a 2 x2
reš lj iva , reš imo s tem tud i
prvo tno na logo . Da lobi s e do -
ka z a t i, dav pr i meru, ko ne mo -
r emo reš i ti i g r e 2x2 , tudi
prv otna na loga n ima re š it ve.
2
S l i ka 1a
16 8
I g ro petn aj st l ahk o pos pl oš i mo
š e na d ru g ačne nač i n e . Kva d r a t -
ke sp r eme ni mo rec imo v p r av ok ot-
n ik e a l i pa v like ra zl ičn ih
obl ik . Premisli in r eši t ol e
na logo : Na tabl i 5 x4 je 10 l i -
kov r az vr š č eni h t a ko, ko t ka ž e
s l i ka 9 .
1 2 3
5
4
718 6
9 10
S l i ka 9
Ali j e mogoč e s premi -
ka nj i prestaviti kvadratek š te -
v i lka 2 na me sto, k i ga kaže
sl ika lO ? Položa j ostalih p loš -
č i c pr i tem ni pomembe n !
Tomaž Pisan s k i