i
i
“Razpet-kralj” — 2010/6/16 — 12:36 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 17 (1989/1990)
Številka 3
Strani 134–137
Marko Razpet:
ŠE O ŠAHOVSKEM KRALJU
Ključne besede: matematika, kombinatorika, pot, povezava, binomski
koeficienti, rekurzivna formula.
Elektronska verzija: http://www.presek.si/17/982-Razpet.pdf
c© 1989 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.
134
SE O SAHOVSKEM KRALJU
o šahovskem kralju , ki pa se sme sprehajati po polovični šahovnici le v treh
predpisanih smereh, smo v Preseku že precej izvedeli. Odgovorili smo na vpra-
šanje, na koliko različnih načinov lahko pride na poljubno polje z začetnega
polja. Ta števila so nam pričarala lepe vzorce, če smo polja barvali z barvami,
ki so jih narekovali ostanki pri deljenju z danim številom p. Tudi tokrat bomo
prehodili pr ibližno tako pot, le da kralju šahovnice ne bomo odvzemali.
Mislimo si torej šahovskega kralja na poljubno veliki šahovnici. Polja zazna-
mujmo tako kot doslej z O, 1, 2, oo. v vodoravni in navpični smeri. Pozicijo na
šahovnici bomo seveda podajali z urejenim parom (x, yI nenegativnih celih
števil. Kralju pa dovolimo le poteze
(x, yI ~ (x+ 1, v). (x, yI ~ (x, y + 11, (x, yI ~ (x + 1, y + 1I
Začetno polje, s katerega gre kralj po šahovnici, bo vselej polje (O, Ol. Označi­
mo z Mlx, y, kI število poti, po katerih lahko pride kralj iz izhodišča na polje
(x, yI po k korakih . Pri tem je k tudi nenegativno celo število. Zaradi lažjega
računanja bomo definirali: M(x, y, kI = O, če je vsaj eno od števil x, y manjše
kot O in M(O, O, Ol = 1. Vse tabele in slike so urejene tako, kot smo označili
šahovnico: od leve proti desni in od spodaj navzgor. Števila M(x, y, kI imajo
očitno lastnost simetričnosti za x in y: M(x, y, kI = M(y, x, kI za vsa nenega-
tiv na cela števila x, y, k. Oglejmo si vse tiste poti, po katerih prispe kralj s polja
(O,Ol na polje (3,21 po treh potezah. Te so:
Prirejena tabela števil M(x, y, 31 je
y=2 takale:
y=l 1 3 3 1
O 3 6 3
y=o O O 3 3
x=Ox= 1x=2 x=3 O O O 1
Slika 1
Izven te kvadratne tabele števil so same ničle, ki pa jih ni smiselno pisati in z
njimi tratiti prostora. Bralec sam bo po naslednjem premisleku zlahka sestavil
take tabele tudi za drugačno število korakov k. Obstaja namreč zelo preprosta
povezava med števili M(x, y, kI. Po k korakih pride kra lj na polje (x, yI tako,
da pride po k - 1 korakih na polja (x - 1, yI ali (x, y - 1) ali (x - 1, y - 1),
s teh pa na končno polje po enem samcatem koraku. Z enačbami to takole
zapišemo:
135
M(x, y, kI = M(x-l, y, k-lI + M(x, y-l, k-lI +M(x-l, y-l, k-lI (lI
Ni težko videti, da je M(x, O, kI = 1, če je x =k in O sicer. Na polje (x, Ol lahko
pride kralj le vodoravno, torej na en sam način, toda le, če je x = k, sicer pa
tega polja ne doseže. Če je polje (x, yI predaleč, ga po premajhnem številu
korakov k kralj spet ne doseže. Če je število k preveliko, pa na polja, ki so pre-
blizu ne more. Zato so v naši tabeli nekatera števila, ki tvorijo zase trikotno
shemo tik ob izhodišču, enaka nič. Hitro lahko ugotovimo naslednje:
M(x, y, kI =O, če je x > k ali y > k ali x + y < k.
V nadaljevanju bomo označevali z mlx, yI manjšega, z M(x, yI pa večjega
od števil x, y. Potemtakem velja:
M(x, yI ~ k ~ x + Y ~ M(x, y, kI '* O (21
Na prvi pogled ugotovimo, da ležijo na diagonali in dveh stranicah prejšnje
tabele ravno binomski koeficienti (tI. Ponovimo:
ni(nI = , (n I = ( n I
k kUn-kI! k n-k
(Pascalova identitetal
o binomskih koeficientih je bilo v Preseku že veliko napisanega, zato o njih tu
ne bi razpravljali.
Z relacijo (1I so števila M(x, y, k) natanko določena. Dokažimo:
M(x, y, k) = (~ )( k~) = (~)( k~Y)
Na prvi pogled izraz za M(x, y, kI ni simetričen v števil ih x in y. Toda
(3)
kly! kI
---------------=-------------=
yi (k-y) I(k-x)! (y-k+xl! (k-x)! (k-y)! (x+y-k)!
klx! k x
--------------- = ()( I
xUk-x)l(k-yl!(x-k+y)! x k-V
S Pascalovo identiteto pa se prepričamo, da zadoščajo števila M(x, y, k) relaciji
(1 I :
M(x, y, k) -M(x-l , y, k-l) - M(x, y-l, k-lI -M(x-l, y-l, k-l) =
(k)( Y ) _ (k-1)( Y ) _ (k- 1)( y-1 I _ (k- 1j(Y-1 ) =
Y k-x y k-x y-1 k-1-x y-1 k-x
136
= ( y )(k-1)_(k-l)( Y)=O
k-x y-1 y-l k-x
Bralec, ki je že bolj vešč kombinatorike, bo morda preveril (3) s preprostim
sklepanjem.
Za x = O dobimo iz (3): M(O, y, k) = (~)(~). Če je k < y, potem je prvi
faktor nič, če pa je k > y pa drugi. Če je k = y, dobimo M(O, k, k) = 1. Torej
MlO, y, k) = 1, če je k = y, in O sicer.
Za k =x ali za k = y dobimo čiste binomske koeficiente:
M(x, y, x) = (;) in M(x, y, y) = (~)
Tudi za k = x + y dobimo lep rezultat:
M(x, y, x + y) = (x x+ y) = (X; y)
Sedaj ni več težko prešteti število vseh poti, ki kralja pri dovoljenih potezah
pripeljejo v dano točko (x, y). To število označimo z ,(x, y) . Očitno velja
zaradi omejitve (2) :
in odtod zaradi (3):
x+y
,(x: y) = ~ M(x, y, k)
k=M(x,y)
(5)
(6)
x+y
,(x,y) = ~ (k)l v )
k=Mlx,y.l y k-x
Števil rlx, y) nam ni treba računati po tej komplicirani formuli, kot nam ni
treba računati binomskih koeficientov s fakultetami, saj imamo na razpolago
Pascalov trikotnik, kjer shajamo samo s seštevanjem. S podobnim razmislekom
kot smo dobili zvezo (1). dobimo relacijo
,(x, y) =rlx - 1, y) + ,(x, Y - 1) + ,(x - 1, y - 1) (7)
Ker je ,(x, y) = ,(V, xl in ,(x, O) =rlO, y) = 1 za x, y ~ O, lahko dobimo polju-
. bno veliko tabelo števil ,(x, y):
..... ...... .......
7 25 63 129
5 13 25 41
3 5 7 9
1 1 1 1
137
Tabelo začnemo izpolnjevati levo spodaj. vsako naslednje število je vsota treh,
recimo 41 = 25 + 7 + 9, števila 41 , 25 , 7, 9 tvorijo v tabeli kvadrat števil. Pre-
den preidemo na morda najzanimivejši del tega razglabljanja, še neobvezna
naloga za bra lce: dokaži, da velja za poljubni nenegativni celi števili x, y iden-
titeta
m(x.y) + x+y
r(x,yl= L (xw y-kl= L (kI( x I
k=O k x k=M(x.y) x x+y-k
Števila r(x, yI z rastočima x in y hitro naraščajo in vsa so liha. Izberimo si
naravno število p večje od 2 in opazuj mo tabelo ostankov štev il r(x, yI pri
deljenju s številom p . Učeno rečeno, študirajmo števila r(x,yl po modulu p,
označimo jih z r(x, y)(mod pI. Z~ p = 3 dobimo tako tabelo, sestavljeno iz
številO, 1,2 za O .;;;; x, y .;;;; 15 (glej tabelol
~-Q-o---o-' -c-<>--
O X
Tabelo dobimo po formuli (71, pri
čemer računamo po modulu p = 3,
se pravi, čim vsota na desni prekorač i
število p, odštejemo od nje tolikokrat
p , da dobimo število med O in p-l
vključno. V tabeli so zanimive ničle .
Te tvorijo pravilno razporejene kva-
drate, katerih stranice štejejo 1, 3 ,
9, ... ničel. Z računalnikom lahko
sestavimo zelo obsežne tabele na opi-
sani način. Za p = 5 dobimo tako
sliko:
Marko Razpet
1112221110000000
1210002120000000
1020002010000000
1110002220000000
1211211210000000
1022011021022011
1112221111112221
1021021020000000
1111111110000000
1212121212121212
1210002121210002
1020002011020002
1110002221110002
1211211211211211
1021021021021021
1111111111111111
Točka (x, yI je pobarva na temno, če
je število r(x, yI deljivo s številom p .
Opazimo mali križec v večjem, ta je
kasneje zopet v večjem itd. Zapo-
redje stranic temnih kvadratov raste
po zaporedju 1, 5, 25, ...
Slika 2.p =5
o o
o o o
o o o o
o u o o , ,'
(3,6) ,
o ? o // v>X,
o .0 p '
./ /
~' / J'
. '
o
o
o
o
y