i
i
“Razpet-sahovski-kralj” — 2010/6/1 — 11:08 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 15 (1987/1988)
Številka 6
Strani 358–361
Marko Razpet:
ŠAHOVSKI KRALJ Z OMEJENO SVOBODO GIBA-
NJA
Ključne besede: matematika, kombinatorika, rekurzivna formula, po-
teza, pot, binomski koeficient, število poti.
Elektronska verzija: http://www.presek.si/15/915-Razpet-kralj.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.
ŠAHOVSKI KRALJ Z OMEJENO SVOBODO GIBANJA
Zam islimo si šahovskega kr alja (barva ni pomembna), ki se lahko sprehaja samo
po 36 po lj ih šahovske deske, kot pr ikazuje slika 1. Na druga po lja ne sme, zato
jih tud i nismo narisali . Položaj kralja bomo označeva li nekol iko drugače , kot
je navada v šahovskem svetu, in sicer z urejenim parom celih števil (x, y), pri
čemer je O~ x ~ 7 in O~ y ~ x. Zadn ja relacija predstavlja "omejeno suvere-
nost" kralja.
y
7
6
5
4
3
2
1
O
O 2 3 4 5 6 7 x
Slika 1
Ubogemu kral ju, k i mu je na tak način okrnjeno kraljestvo, ni dovol jeno,
da bi se premikal v vseh smereh, kakor to lahko po čnejo običajni kralji na obi-
čajn ih šahovnicah . Naš se lahko premika samo tako, da napreduje za eno po lje
proti desni ali za eno polje navzgor ali pa oboje hkrati. Dovoljene so torej
poteze:
(x, y) """* (x + 1, v). (x, y) """* (x, y + 1) in (x , y) """* (x + 1, Y + 1)
Skušali bomo odgovoriti na vprašanje: Koli ko različnih poti ima kralj na izbiro,
da pride s polja (O, O) na polje (x , y)?
Označimo število vseh teh razl ičnih pot i s q( x , y) .
Primer 1. Za manjše x in y lahko qix, y) določ imo s tem, da vse možne poti na-
rišemo . Določimo na pr imer q(2, 2). Dovoljene poti so naslednje:
358
Slika 2
Torej je q(2, 2) = 6. Samo ena pot pripelje kralja z začetnega polja (O, O) na
polje (1, O), zato je q( 1, O) = 1. Prav tako lahko pride na polja (2, O), (3, O) , ...,
(7, O) na en sam način. To pomeni, da je qix , O) = 1 zax= 1,2, .._, 7. Zaradi
popolnosti bomo vzeli še q(O, O) = 1.
Nobenega razloga ni, da ne bi vzeli trikotne šahovske deske drugačnih raz-
sežnosti, recimo take, ki ima na osnovnici n polj. Pri tem je lahko n poljubno
naravno število. V vsakem primeru velja:
q(x,O)=l zax;;;'O (1)
Primer 2. S preštevanjem določimo q(2, 1) in q(3, 1). V prvem primeru so do-
voljene naslednje poti :
Slika 3
Imamo torej 4 raz lične poti: q(2, 1) = 4. V drugem primeru pa so možne take
poti :
Slika 4
Torej je q(3, 1) = 6. Polje (3,2) je dosegljivo s polj (2,2), (3, 1) in (2, 1). Kralj
lahko pride na prvo od teh treh po q(2, 2) = 6 različnih poteh, na drugo po
q(3, 1) = 6 različnih poteh in na tretje po q(2, 1) = 4 različnih poteh, vsakokrat
začne na polju (O, O). Do polja (3, 2) ima samo še korak. Od tod sklepamo, da s
polja (O, O) kralj s svojo omejeno svobodo gibanja prej ali slej zavzame polje
(3, 2) po q(2, 2) + q(3, 1) + q(2, 1) = 6 + 6 + 4 = 16 različnih potez . Z enakim
premislekom ugotovimo:
359
qix, y} = q(x-1, y) + qix, y-1) + q(x-1, y-1) za 1 ~ x in 1 ~ y ~ x (2)
To je rekurzivna formula za izračun števil qix, y} . Upoštevajmo še relacijo (1),
pa že lahko sestavimo preglednico:
1,;\ O 1 2 3 4 5 6 7-
7 8558
6 1806 6752
5 394 1412 3534
4 90 304 714 1408
3 22 68 146 264 430
2 6 16 30 48 70 96
1 2 4 6 8 10 12 14
O 1 1 1 1 1 1 1 1
V vrstico z oznako y in stolpcu z oznako x stoji število q(x, V). V spodnji vrst i-
ci smo upoštevali, da je q(x, O} = 1. Ostale vrstice izpolnimo samo s seštevanjem
največ treh števil v skladu s formulo (2). Pri tem vzamemo , da je qix, y) = O, če
je x < y . Hitro se vidi, da so nad vrsto iz enic sama soda števila, to je
I
q(x, 1) = 2 x za x ~ 1 (3)
Števila q(x, 2} je že nekoliko teže razpoznati. Opazimo pa naslednjo zako-
nitost: števila -t q(x, 2) so po vrsti 3,8, 15, ...r to pa so kvadrati števil 2,3, 4,..t
zmanjšani za 1. Velja torej:
q(x,2}=2(x2-1} za x~2 (4)
Uganiti števila qix , 3} ni več mačji kašelj, napišimo samo rezultat :
q(x,3)=~(x-2}(2x2+4x+3} za x~3 (5)
Pojavi se seveda vprašanje, kako se glasi formula za qix, y} v splošnem . Najbolj
zadovoljni najbrž ne moremo biti z njo , ker je videti takale:
( . ) x-I/+1q x, y =---'---
y
y-l
~ (x) ( y ) 2k+ 1 za y > O
k=O k k + 1
(6)
Do nje pridemo z metodami tako imenovanega simboličnega ali umbralnega ra-
čuna (Roman, [1]). Kot poseben primer dobimo iz (6) tudi (3), (4) in (5) .
Preverimo, če je res q(3, 2) = 16: q(3, 2} = (~}(~) 2 + (~)(~) 22 = 4 + 12 = 16.
Naloga za bralce: Vsak ponedeljek obiskujem tržnico. Branjevka, pri kateri ku-
pujem, je prejšnji ponedeljek prodajala paradižnik po 400 din za kilogram . Da-
360