MATEMATIKA
Problem kitajskih prstanov
Tanja Gologranc Zgodovina problema
Problem kitajskih prstanov je ena najbolj znanih matematičnih ugank. Prvotni problem sestavlja palica z devetimi povezanimi prstani, pri čemer lahko devet nadomestimo s poljubnim številom prstanov (glej sliko 1). Te prstane moramo s palice odstraniti. Nihče ne ve natančno, kdo je avtor sestavljanke in kdaj se je prvič pojavila; obstajajo le pripovedke. Ena izmed najbolj znanih govori o tem, da naj bi palico z devetimi povezanimi prstani za svojo ženo izumil kitajski strateg Zhuge Liang (181-234), in sicer z namenom, da bi si krajšala cas, ko je bil sam na vojnih pohodih. Drugi, prav tako nezanesljivi viri trdijo, da uganka izhaja iz dinastije Song (960-1129). Prvi zapis uganke tega tipa sega v 14. stoletje, njegov avtor pa je italijanski matematik Luca Pacioli (1445-1517).
Opis problema
Imamo palico in prstane, pri cemer se prstani ne prepletajo le med sabo ampak prepletajo tudi palico. Te prstane moramo s palice odstraniti. Tako kot za vecino znamenitih ugank tudi za problem kitajskih prstanov velja, da ga rešujemo z upoštevanjem pravil.
SLIKA1.
Kitajski prstani
Kljub temu, da so pravila enostavna, reševanje zahteva veliko razmisleka in predvsem potrpežljivosti.
Ves cas bomo obravnavali splošen primer, torej problem n kitajskih prstanov, pri cemer je n poljubno število iz množice {0,1,...}. Iz tehnicnih razlogov, ki bodo omenjeni pozneje, je vkljucen tudi primer z 0 prstani. Za lažji opis rešitve problema bomo prstane oznacili. Prstane oštevilcimo narašca-joce, z oznakami od 1 do n tako, da prvi prstan na palici, torej prstan, ki je od držala palice najbolj oddaljen, dobi oznako 1.
Opis pravil za reševanje problema
Zacetno stanje je stanje, ko so vsi prstani na palici. Iz tega stanja lahko pridemo v katerokoli drugo stanje, in sicer z zaporedno uporabo le dveh potez. Premaknemo lahko:
prstan z oznako 1 (poteza tipa 0); ■ prstan z oznako i + 1, ce je prstan z oznako i na palici, prstanov z oznakami 1,...,i -1 pa na palici ni (poteza tipa 1).
Pri tem premik prstana pomeni, da mu zamenjamo položaj iz je na palici v ni na palici oziroma obratno.
Problem kitajskih prstanov porodi najprej vprašanje, ali rešitev sploh obstaja. Obstoj rešitve porodi nadaljna vprašanja; eno od teh je vprašanje o najmanjšem številu potez, potrebnih za rešitev problema.
Predpostavimo, da problem kitajskih prstanov zacnemo reševati v zacetnem stanju in da bomo problem rešili s kar najmanj potezami. Potem imamo za prvo potezo dve možnosti; bodisi iz palice odstranimo prstan z oznako 1 (poteza tipa 0) bodisi odstranimo prstan z oznako 2 (poteza tipa 1). Ker je naša rešitev najkrajša, ne bomo v nobeno stanje prišli vec kot enkrat. Torej imamo za vse nadaljnje poteze samo še eno možnost, saj bi nas dve zaporedni potezi istega tipa pripeljali v že obiskano stanje. Zato bo naše zaporedje alternirajoce zaporedje potez tipa 0 in 1. Na sliki 2 je zaporedje potez, ki rešijo problem treh kitajskih prstanov.
4
PRESEK 43 (2015/2016) 1	4
MATEMATIKA
SLIKA 2.
Postopek reševanja problema treh kitajskih prstanov
Rešitev problema z grafi
Za vsak prstan obstajata dve možnosti, in sicer, ali je prstan na palici ali pa ga ni. Ce je na palici, potem mu priredimo vrednost 1, sicer mu priredimo vrednost 0. Potemtakem lahko vsako stanje problema n g N0 kitajskih prstanov predstavimo kot 5 = sn... s1, pri cemer si = 1(0) pomeni, da prstan z oznako i je(ni) na palici. Tukaj opozorimo še, da za n = 0 s predstavlja prazen niz. Glede na zgoraj omenjeni pravili, lahko bit si+1 spremenimo, ce je bodisi i = 0 (poteza tipa 0) bodisi je st = 1 in sj = 0 za vsak j g {1,...,i - 1} (poteza tipa 1). Za vsak i g {1,...,n} definirajmo s i = 1 - si. Potem lahko dovoljene premike opišemo tudi takole. Iz stanja sn...s2s1 lahko z eno potezo pridemo v stanje sn...s2s 1, iz stanja
sn...si 10...0 pa lahko prav tako z eno potezo pridemo v stanje sn.. .si 10... 0.
Iz zgoraj opisanega postopka, kako iz danega stanja z eno potezo pridemo v drugo stanje, bomo konstruirali graf Rn. Vsako stanje problema predstavlja eno vozlišče grafa, dve vozlišči (stanji) sta povezani s povezavo natanko takrat, ko lahko iz enega stanja z eno potezo pridemo v drugo stanje. Zdaj lahko problem zapišemo z uporabo grafov: poišci (najkrajšo) pot med 1n = .K^L in 0n = (h^.
nn
Graf Rn vsebuje natanko dve vozlišci, ki imata natanko enega soseda. To sta vozlišci, ki predstavljata stanji 0n in 10n-1 = 1 0... 0, kjer je mogoca le po-
n-1
R2
00
o—
01
—o—
11
—o—
10
—o
R3
000 001 011 010
o-o-o-o-
110 111 101 100
—o-o-o-o
SLIKA 3.
Konstrukcija grafa r3 iz grafa r2
PRESEK 43 (2015/2016)1
5
MATEMATIKA

00... 0
01... 0
11... 1
0n-1 107^
11... 0
SLIKA 4.
Graf Rn
teza tipa 0. Vsa druga vozlišča imajo natanko dva soseda, saj za vsako tako stanje obstajata obe rela-ventni potezi (tipa 0 in tipa 1). Iz omenjenih lastnosti grafa Rn zlahka dokažemo, da je Rn pot na 2n vozliščih, s krajiščema 0n in 10n-1, ki vsebuje stanje 1n. Dokaz najenostavneje opravimo z indukcijo. Ce vsakemu stanju poti Rn-1 na levo stran pripnemo 0, dobimo pot od 0n do 010n-2. Ta vsebuje vsa stanja grafa Rn, ki se začnejo z 0. Enako velja, če vsakemu stanju poti Rn-1 na levo stran pripnemo 1 in tako dobimo pot od 10n-1 do 110n-2. Ta vsebuje vsa stanja grafa Rn, ki se začnejo z 1. Ker sta 010n-2 in 110n-2 edini stanji z različnima prvima bitoma, ki ju povezuje poteza tipa 1, sta vozlišči 010n-2 in 1 dobimo, da je pn - pn-2
potrebnih potez za rešitev n kitajskih prstanov. Z pn označimo najmanjše število potez, potrebnih, da spraznimo paličo z n prstani, to je, da pridemo iz stanja 1n do stanja 0n. Ker je Rn pot, je pn ravno razdalja v grafu Rn med vozliščema 1n in 0n. Iz kon-strukčije grafa Rn sledi, pn-1 = (2n - 1) - pn (glej sliko 4). Na ta način dobimo rekurzivni zapis pn + pn-1 = 2n - 1, z začetnim pogojem p0 = 0, s čimer lahko za poljubno število prstanov n pridemo do rešitve v končnem številu korakov. Iz rekurzije lahko s preprostim izračunom pridemo do ekspličitne formule za fin.
Iz enačb ßn + ßn-1 = 2n - 1 in ßn-1 + ßn-2
= 2n-1 -
= 2
n- 1
110n-2 sosednji v Rn, kar pomeni, daje Rn pot. Opazimo lahko, da graf Rn sestavljata dve disjunktni kopiji grafa Rn-1, pri čemer v prvi kopiji vsakemu vozlišču 5 = sn-1.. .51 dodamo sn = 0 in dobimo vozlišče 0sn-1... s1. V drugi kopiji vsakemu vozlišču s = sn-1.. .s1 dodamo sn = 1, niz s pa obrnemo in dobimo 1s1... sn-1 (glej sliko 3).
Ker je Rn pot na 2n vozliščih s krajiščema 0n in 10n-1, ki vsebuje stanje 1n, za vsak n obstaja rešitev problema n kitajskih prstanov. Ker lahko od 0n do 10n-1 pridemo v 2n - 1 potezah in ker 1n leži na poti med 0n in 10n-1, za rešitev problema n kitajskih prstanov zadošča manj kot 2n - 1 potez.
Iz rešitve problema treh prstanov je razvidno, da je v najkrajši rešitvi treba začeti s potezo tipa 0, sičer nas alternirajoče zaporedje potez v R3 vodi od 111 proti 100, s čimer se oddaljujemo od stanja 000. Ker je vsako najkrajše zaporedje potez za rešitev problema kitajskih prstanov alternirajoče zaporedje potez tipa 0 in 1, je za vsak lihi n prva poteza v najkrajši rešitvi poteza tipa 0. Za sode n velja ravno nasprotno, in sičer je v najkrajši rešitvi prva poteza vedno poteza tipa 1.
V nadaljevanju bomo iz zgoraj opisane konstruk-čije grafa Rn izpeljali rekurzijo za najmanjše število
Ce zaporedoma
manjšamo indekse, za sodi n dobimo:
ßn = ßn-2 + 2
n- 1
ß
= lPn-4
5) +2n-1
+ 2n-3) + 2n-
n-1
= ß2 + 23 + 25 + ■ ■ ■ + 2 = 2 + 23 + ■ ■ ■ + 2n-1 = 2 (1 + 4 + 42 + ■ ■ ■ + 4n-L)
=2
n
42 - 1 4 - 1
•>n+1
-2
Podobno za lihe n dobimo, da je ßn = 2n+31-1.
S tem smo dobili formulo, z uporabo katere lahko, za poljubno naravno število n, izračunamo najmanjše število potrebnih potez, ki rešijo problem n kitajskih prstanov.
Literatura
[1] A. M. Hinz, S. Klavžar, U. Milutinovic in C. Petr, The Tower of Hanoi-Myths and Maths, Birkhäuser 2013.
_ XXX
n- 1
1
ß
n- 1
3
6
PRESEK 43 (2015/2016) 1	6