i i “vencelj-abrakadabra” — 2010/6/16 — 12:48 — 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 148–152 Marija Vencelj: ABRAKADABRA ALI ŠTETJE NAJKRAJŠIH POTI V MREŽI Ključne besede: matematika, kombinatorika, graf, binomski koefici- enti, Pascalov trikotnik. Elektronska verzija: http://www.presek.si/17/982-Vencelj-abrakadabra.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. 148 ABRAKADABRA ali štetje najkrajših poti v mreži Dandanes besedo ABRAKADABRA največkrat uporabljamo kot sinonim za "zapleten nesmisel". V davnih časih pa je bila to čarobna beseda, ki so jo imeli navado v skrivnostnih oblikah vrezovati vamulete, ki naj bi lastnika obvarovali pred boleznijo in drugimi nesrečami. Primer takega čarobnega zapisa je na sliki 1. Nekaj je gotovo: pred radove- dnostjo ne zavaruje! Nasprotno! Ob pogledu nanj se kar samo ponuja vprašanje, na koliko načinov lahko v njem preberemo besedo ABRAKADABRA. Poglej- mo! Pri tem se domenimo, da veljajo le "povezane" besede. To pomeni, da bomo začeli brati pr i črki A v zgornjem (severnem) vogalu in na posameznem koraku nadaljevali s sosednjo spodnjo črko (jugovzhodno ali jugozahodno), do - kler ne bomo dosegli zadnjega A na spodnjem (južnem) vogalu. A 8 8 R R R A A A A K K K K K A A A A A A D D D D D A A A A 8 8 8 Slika 1 R R A Ste poskušali besede prešteti? ln obupali? Poglejmo, kako lahko nalogo posplošimo in hkrati dobimo za reševanje idejo, boljšo od štetja. Problem spominja na hojo ali vožnjo po mestu, v kate- rem so ulice razvrščene kot na sliki 2. V mreži ulic lahko izbiramo različne poti, ki vodijo od A na severu do A na jugu. Poti so različnih dolžin; na sliki označena je dolga deset blokov. Očitno ni nobene poti, ki bi bila od nje krajša , je pa več takih, ki so dolge deset blokov. Prav te najkrajše poti ustrezajo branju čarobne besede na sliki 1. Besedo ABRAKADABRA torej lahko preberemo na 149 toliko načinov, kolikor je različnih najkrajših povezav med skrajno severno in skrajno južno točko cestne mreže s slike 2. Slika 2 Ob tem si lahko postavimo tudi vprašanje, koliko je različnih najkrajših povezav severne točke A s poljubno točko mreže . Za točke blizu A poti ni težko prešteti. Nekaj rezultatov je vpisanih na sliki 3. Slika 3 2 3 3 4 6 4 5 10 10 5 6 15 20 15 6 21 35 35 21 56 70 56 126 126 252 Slika 4 150 Naj bo sedaj Z poljubno križišče mreže. križiščeX njegov severozahodni in Y njegov severovzhodni sosed kot na sliki 3 . Najk rajša pot. ki vodi od A do Z. mora iti ali skozi X ali skozi Y . Če gremo skozi X. je nadaljevanje od X do Z eno samo. Isto velja za vsako pot. ki vodi skozi Y . Od tod sledi: Število vseh najkrajših poti od A do Z je enako vsoti števila vseh najkrajših poti od A do X in števila vseh najkrajših poti od A do Y. Na osnovi te ugotovitve ni težko sestaviti tabele za število najkrajših poti od zgornje točke A do dane točke (slika 4) . Iz nje razberemo. da poteka od točke A na severu do točke A na jugu 252 najkrajših poti oziroma. da je na slik i 1 čarobna beseda ABRAKADABRA zapisana na 252 različn ih načinov . Nekateri ste števila s tabele 4 že prepoznali. Prav imate - to so binomski koeficienti. Njihovo trikotno razporeditev, katere začetek je na zgornjem delu slike 3. običajno imenujemo Pascalov trikotnik. Načeloma lahko Pascalov tri- kotn ik nadaljujemo v nedogled. Prvo in zadnje število v posamezni vodoravni vrsti sta enaki ena , ostala števila so zaporedne vsote po dveh sosednjih števil iz prejšnje vrste. Tabela na sliki 4 ni nič drugega kot iz večjega Pascalovega tri- kotnika izrezan kvadraten kos. Že v 17. stoletju je francoski matemat ik in filozof Blaise Pascal našel in tudi dokazal eksplicitno formulo za računanje binomskih koeficientov le iz njihove lege v Pascalovem trikotniku (ki ga je sam imenoval aritmetični tri- kotnik). brez računanja števil v prejšnjih vrsticah. Lego števila lahko opišemo • tako. da npr . navedemo. v kateri vodoravni vrsti in na katerem mestu z leve v tej vrsti se nahaja. Drugi podatek nam pove, v kateri poševni vrsti smeri JZ-SV se število nahaja. Pri tem vrste in mesta numeriramo od nič da lje. Če z [n ] r označimo število v n-ti vodoravni vrsti na r-tem mestu. je Pascalov t rikotnik takle Zveza , ki velja za števila iz notranjo- st i sheme. se v teh oznakah zapiše: Očitno je še. da sta med seboj ena ki števili, ki ležita v ist i vrsti simetrično na navpičnico skozi vrh sheme. saj je število naj krajših poti od vrha sheme do simetrično ležečih točk enako. To zapišemo: [8] n] u] [ ~J nj nj [ ~J nJ nj m [ri] [ij [i l [jJ [:] V~ 1J [~J r': 1 ]r [n+ 1 J= [ n J+ [n J -r ,- 1 r za r - 1.2 , ... . n (1) (2) 151 Pascal je dokazal, da je [n ] = ..!Ill1..:=..!l.0_-.2L.:l'2...-=!-7"_l) r 1.2.3... r in dodatno [~ ] = 1 (3) (4) V našem primeru je n = 10 in r = 5, torej je število besed ABRAKADABRA enako kar smo prej izračunali na rekurziven način . Pascal nam v svojih delih ne zaupa, kako je prišel do eksplicitne formule - morda jo je enostavno uganil. Zato bomo tudi mi pustili to vprašanje ob strani in si ogledali le dokaz formule. Vemo, da so števila ob robovih sheme enaka 1, torej [~ ] = [~ ] = 1 (5) kar se ujema s (3) za r = n in s (4). Formulo (3) moramo torej dokazati le še za notranjost sheme, to je za O< r