i
i
“4-2-Repovs-Skratek” — 2010/5/10 — 12:28 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 4 (1976/1977)
Številka 2
Strani 75–77
Dušan Repovš:
ŠKRATEK IN PAJEK
Ključne besede: matematično razvedrilo, matematika, rekreacijska
matematika, kombinatorika.
Elektronska verzija: http://www.presek.si/4/4-2-Repovs-skratek.pdf
c© 1976 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.
MATEMATiČNO
RAZVEDRILO
šKRATEKIN PAJEK
Ogledali s i bomo zan imiva (matematična) problemčka, ki sta
med s e boj tesno povezan a, saj j e drugi s amo razšir itev prvega.
Pa začnimo!
Problem 1. : Škratek stoji v ~evem spodnjem ko t u po ~jubno ve~i­
ke iahovske deske . torej na "koti " (O.O) . (V s p ~ o in em naj po me-
ni koordinata (m. n) kvadratek. k i se nahaja na pre sečiiču m- t e-
ga s t o ~p c a i n n -te vrst i c e . ) Na ko ~ i k o načinov (pri n ajmanjiem
itevi~u korakov) ~ahko pride iz kvadratka (O.O ) na izbr an i kva-
dratek (x .y)? Pri tem pa od ikratka zahteva jmo. da se gib~je
vedno ~e vodoravno aLi navpično.
Reš itev: Oz načimo s sp r em en l j i vko Ux ,y število možnih (naj -
kr a jš i h) prehodov iz kle tk e ( 0 , 0 ) v kl e tk o (x, y). Očitno je za
poljuben par števil x i n y r e s :
ux ,o = 1 in u o• Y = 1
Pr av tako je res , da lah ko šk r a t ek pr i de v kletko ( x , y ) le
iz kletk (x-l ,Y) a li pa (x, y -l) , do kater ih pa lahk o pr ide s e -
ved a na natanko ux-1 y ozi ro ma Ux , y - l n a č i n o v . Odtod dobi mo re-
kurziv no* relac ij a z~ f unkci j o Ux ,y:
Ux ,y = Ux - 1 ,y + Ux, y-l
(Tor e j j e Ux ,y = f (x ,y ) funk-
c ij a dveh cel i h nenegativnih
sprem enljivk .)
Sed a j se lo t imo vpisovanja
štev il ux,y v posamezne stolp-
ce . Postope k vidimo iz slike:
(Ali st e prepoznal i Pascalov
tr i kot ni k binomskih koe f ici-
entov ? Zanimivo , mar ne?)
75
Poiš čimo r eš ite v naš e r e kur z i vne form ule: oči tno potrebuje
škr a t ek za pr eh od kvadratka (0,0 ) na kvadra te k (m, n ) s amo m+n
korak ov, m vodor avn i h in n na vpič n ih . Oči tno i mamo za iz bor m
mest n~ r az pol ago kvečj emu c:+n = (m + n ) !/ (m !n ! )**mo ž no s t i . To
pa je obenem odgov or na naš e vpr aša nje :
ux, y
(x + y ) !
x!y !
Pro blem 2.: Pajek si je spZeteZ v kotu s obe nekakino "kub i a-
no" mre žo . DobZjene prostorske kockice imenujemo kZetke s koor -
di natami (x ,y,z) . (Pomen x , y i n z Zahko ugane te iz prejlnje re -
litve) . Na koZiko naainov Zahko pride pajek iz kota sobe , t .j .
iz kZetke (0 ,0,0) v dano kZetko (k , Z,m)? Pri tem mora vedno u-
brat i na j kra jlo pot , kakor popre j I kr a t e k .
Reš i t ev : Tako kot poprej t ud i tu p o i š čem o podobne zakoni to s ti
v gibanju pajka. Oči tno je t okrat re kur zivn a fo r mul a:
Ux ,y , z = ux - l , y , z + Ux , y - l , z + Ux ,y,z -l
o čitno pa velja j o t ud i na s l ed nje tri ena č be:
u ( x+ y)!I (x!y!)x, y,O
ux , O, z ( x + z ) !/ (x !z ! )
UO,y ,z ( y + z ) !/ (y !z ! )
ke r smo to ugot ovi l i že pri š kr a t ku .
Da pr i demo do kl etk e ( k, Z, m) , nam t okrat zadostuje na tanko
k + Z + m kor a kov . Te lah ko izberemo n a j~ r e j na
( k + Z + m) !I (k! (Z + ml ! ) n a č i n o v za pot po osi x , nato nam o-
sta ne Z + m mest, izmed katerih l ahko spet i zbir amo pot po os i
y na ( Z + m) !/ (Z !m! ) n ačinov . Tor e j je ce lotno štev i lo možno-
st i izb ora št evi l k in Z (število m pa je že s t em en ol ično do-
ločeno ) en a ko i z ra zu :
( k+ Z+ m) ! (Z +m ) !
k i (Z + ml ! Z!m!
I n od t od do b imo r e zu lt a t , k i smo
= ( k + Z + m) !
k !Z !m!
ga p ričakova l i:
'd'Št ev i lo n! imenuj emo "n fakul t et a" a l i "n f aktorsko" , pomeni pa produkt
vse h zapo redn i h naravnih š tev i l od 1 do n:
n ! = 1. 2. 3 .4 . . . ..
Naj dodamo, da postan e j o štev i la n ! že za relati vno maj hne n- j e st ra hov i to
vel ik a , npr . l O! = 3628800 , 20! = 24329 0200817664 0000, i t d .
76
, (a + # + # I !  
Bl~,gf,s s l y l x l  i 
Seveda se d &  naloga p o s p l t j i i t i  na poljubno dimenzionalno 
"ajkauan mreto I n  rezult.dE j e  spet analogan - v n-dfmenzijah 
dobimo 
Za kenee pa poskuslts resi tole nalego: I ~ I A D  m eS$8t~ZZB18- 
w v  d5h k h k o  ~ ~ a p Q Z ~ d d t @  s meanJ 8e MaIra@@ @eta laa$mrrth a&$*&