I Računalništvo Nadaljevanje s str. 155 . Profesor Manindra Agraval (skrajno desno) in njegova podiplomska študenta Nitin Saksena in Niradž Kaja!. Računski postopek treh indijskih znanstvenikov bomo morda opisali kdaj drugič. Za zdaj povejmo le, da čas, ki ga novi postopek v najslabšem primeru potrebuje za preskus praštevilskosti števila n, zanesljivo ni večji od CIn12 n , kjer je C neka konstanta. Avtorji domnevajo, da potrebni čas v resnici ni večji od C In6 n. Za ilustracijo vzemimo, da njihova domneva drži in da je vrednost kon- stante C enaka času, ki ga naš računalnik potrebuje za eno deljenje. Potem bo za preskus praštevilskosti števila n = 10100 + 267 porabil približno 149 sekund oziroma dve minuti in pol. No , toliko bomo pa že počakali! . Novi postopek ima velik teoretičen pomen. V praksi pa se bodo za reševanje problema praštevil še vedno uporabljali verjetnostni algoritmi, ki so neprimerno hitrejši, kar dosežejo z žrtvovanjem absolutne pravilnosti odgovora. Verjetnostni algoritmi se namreč lahko včasih zmotijo in kakšno število razglasijo za praštevilo, čeprav je v resnici sestavljeno. Ker pa je verjetnost napake izredno majhna (veliko manjša od verjetnosti glavnega dobitka na loteriji) , so ti algoritmi za potrebe kriptografije zaenkrat povsem ustrezni. Marko Petkovšek I PRESEK list za mlade matematike, fizike , astronome in računalnikarje 30. letnik, leto 2002/03, številka 3, strani 129-192 VSEBINA MATEMATIKA FIZIKA ASTRONOMIJA RAČUNALNIŠTVO NOVE KNJIGE ZANIMIVOSTI, RAZVEDRILO NOVICE NALOGE REŠITVE NALOG TEKMOVANJA NA OVITKU Koti v pravilnem petkotn iku (Marko Raz pe t) 142-147 O Arhimed ovi kroni (Jane z Strnad) 134-137 Kot a ino t renje (Andrej Likar) 152-154 Bine ugot avlja radioak ti vn ost (Jože P ah or) 164-168 Druga naj svetlejša zvez da (Marijan P rosen) 148-150 Dvojni planet (Marijan Prosen ) 169-170 Številski labirint (Mart in Juvan) 138-141 Rešit ev problema praštevil (Marko Pet kovšek ) . . . . . . . . . . . 155, III Marijan in St ana Prosen: Zvezd ni m iti in legende (Marija Vencelj ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 151 Križanka "Matematik i 19 . stoletj a" - reš . na str. 170 (Marko Bokalič) . . . . .. . .. . .. . . .. . .. . ... . .. . .. . . .. . 160-161 Did on a , volovska koža in razglednica (Marija Ven celj) 162-16 3 Astronomski tabor na Blokah (Petra Ven celj) . . . . . . . . . . . . . . . . 133 33 . mednarodna fizikalna olimpiada (Ciril Dominko) . . .. . 156-157 Sloven ija gre naprej a li ka ko smo bili na j bolj ši na olimpiad i (To ne Grad išek) . . . . . . . . . . . . . . . . .. . . . . . . . . . 157-159 Mednarodni kongres matematikov , Peking 2002 (D ušan Repovš) 171- 172 Na d rugi st rani Zemlje - Nagrad na naloga (Pe te r Petek ) 130 Hr an a , ran a , Ana , na - Nagrad na naloga (Marija Vencelj ) 131 Tri posode - reš . st r. 168 (Marij a Vencelj ) 141 R aziskovalna naloga o Kano pu in Sirij u - reš . st r. 159 (Marijan Prosen ) 150 Dva kamna - Reši tev nagr adne naloge iz 1. številke (Marija Vencelj ) .. . .. . . . . . .. . . .. . . . . .. . . .. . . . . . .. . . .. 131-132 Naloga o Fibonac cijevem za poredj u - Rešitev s str. 4 (V iktor Velkavrh in Roman Drnovšek) 154 Urn ik tekmovanj v letu 2003 (Darjo Feld a ) 173-175 22 . področno t ekmovanje iz fizike za osnovnošo lce - reš . na str. 180 (Zlatko Bradač, M irko Cvahte) 176-179 Naloge z regijskega fizikalnega tekmovanja sred nješolcev Slovenije v šolskem letu 2001 /02 (C ir il Dominko) .... . 183-186 Iz birn a t esta za med narod no matematično olipmiado - reš . na str. 188 (Matj až Željko) 187 Večerno nebo nad Bloško plano to (foto Pe tra Ven celj) . G lej t udi zapis na str. 133 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Sloven ski olimpijski ekipi na 33. fizikalni in 43. matematični olimpiadi. Poročili sta na st rane h 156 in 157 II Zlata krona iz preddverj a gro ba Fi lip a II , Makedonskega, v ob liki vej ice iz listov in cvetov , zvit e v ven ec , iz 4. stoletj a pred našim štetjem . Več o t em najdejo bralci na sp let ne m naslovu "http:/ / 111111 . mcs. drexe l .edu/ " cr or r es/Archimedes/Cro\ffi/Crollnlntro .html". IV P eter P etek "No, danes je pred nami naloga iz zemlj episa," je rekla teta Ama- lija, takoj ko so njeni trije nečaki Jožica, Tomaž in Polonca, stopili skozi vrata. Na mizi je imela globus. "Kateri kraj na Zemlji leži najdlje od Ljubljane?" "Hm, ravno na nasprotni stra- ni planeta, za cel premer Zemlje daleč," je premišljeval Tomaž. "J a, ampak Zemlja ni čisto okrogla, malo sploščena je ," je imela pomisleke Polonca. Amalija je menila: "Seveda ne bomo tako grozno natančni, privzemimo, da je Zemlj a krogla. ali ono stran bomo pogledali , da Nagradna naloga I NA DRUGI STRANI ZEMLJE - Nagradna naloga In tudi kakšnih sto kilometrov na to najdemo kakšen večji naseljeni kraj ." "Iščemo torej Ljubljani antipodno mesto ," je rekla Jožica in zasukala globus. "Tule nekj e v Tihem oce anu mora biti ." "Saj tu je sama voda. Antipodna točka Ljubljane je sredi oceana," so razočarano ugotovili vsi skupaj . Zemljepisna širina Ljubljane je (zao- kroženo na cele stopinje) 46° severno in dolžina 15° vzhodno, torej leži antipodna točka 46° južno in 180 0 - 15° = 165° zahodno, tam pa je daleč naokoli samo morje. To pravz aprav ni nič posebnega, saj morje pokriva 71 odstotkov Zemlje in kopno le 29 odstotkov. Zato pa nagradna naloga za vas, dragi bralci. Poiščite par večjih mest, ki sta si vsaj približno antipodni (do 150 km natančno). Im eni mest - z zemljepisno širino in dolžino - pošljite najkasneje do 15. januarja 2003 na naš naslov: Presek, Jadranska 19, 1001 Ljubljana, p.p. 2964. Preverili bomo rezultate in izžr ebali reševalca, ki bo prejel knjižno nagrado. I Nagmdna naloga - Rešitve nalog HRANA , RANA, ANA, NA - Nagradna naloga Iščemo čim daljšo slovensko besedo , iz katere lahko z zaporednim izpu- ščanjem natanko ene črke dobimo zaporedje samih slovenskih besed , do vklj učno zadnje , ki ima dve črki. P rimer je pri kazan v naslovu naloge. Črko lahko izpu st imo na kateremkoli mestu , ne nujno na prvem (npr. križ , riž , rž ali križ , kri, ki ), ne smemo pa spreminjati vrstnega reda črk. Sklanj anje, spreganje, st opnj evanje, dvojina, množina , kr at ice so a ) prepovedane op eracije; b) dovo ljene operacije. Za najdaljšo besedo po d a) in po d b) razpisujemo knji žni nagradi. Če bo takih več , bo o nagradi odločil žreb . Besede pošljite najkasneje do 15. januarja 2003 na n aš na- slov: Presek, Jadranska 19, 1001 Ljubljana, p .p. 2964. Marija Vencelj DVA KAMNA - R ešitev nagradne naloge iz 1. številke V let ošnj i 1. št evilki smo vam zastavili vprašanje, kd aj se srečata ka- mna, od katerih prvega sp ustimo z višine h, dru gega pa hkrati sprožimo navpično s tal s hit rost jo vo. Nalogo je bilo treba rešiti za po datke: a) h = 20 m , Vo = 20 mis, b) h = 30 m, Vo = 10 mi s. P ravilna odgovora st a: a) Srečata se čez 1 sekundo. b) Srečata se čez 2,45 s na t leh , kamor čez 2 sekundi najprej prispe drugi kamen in 0,45 sekunde za njim še prvi. (Vzeli smo g = = 10 ms- 2 .) Na nalogo smo prej eli dvanaj st pravilnih odgovorov. Poslali so jih Denis Brojan iz Domžal, Juvančič J anez z Mute in devet učenk ter en učenec z Osnovne šole Davorina Jenka v Cerkljah na Gorenjs kem: Tina Gašpirc , Mina Grčar , Mart a J agodic, Anit a Krt , Nataša Luskovec, Maj da Pavlin , Damjana Praprotnik, Po lona Trobevšek , Eva Žlebir in Boj an Zupin. Vsak svojo in vsak po svo je drugačno. Njihovemu učitelju fizike gredo naše čestitke za delo pri do datnem po uku. Za pravilne smo šteli t ud i t iste rešitve, ki so bile fizikalno prav zast avljene in računsko pravilno rešene, po manjklj iv pa je bil odgovor na zastavljeno vp rašanje. Žreb je sledil največji verje t nosti. Kn jižno nagrado je prisodil osmo- šolki izpod Krvavca. Prejme jo Marta J agodic. Rešitve nalog I Rešitev naloge Vse prisp ele rešitve so povsem računske . Skupaj rešimo nalogo nekoliko drugače . Kamn a se srečata, ko sta ob ist em času na isti višini od t al. Če štejemo čas t od trenutka, ko kamna sp ustimo oziroma sprožimo , in ozna- čimo z dl( t) višino prvega kamna ter z d2(t ) višino drugega kamna nad tl em i, velja dl (t)={~ _ ~t2 , d2(t ) = { ~ot - ~ t2 , če je h - ~t2 ;::: O sicer če je vot - ~ t2 ;::: O sicer Iskani čas srečanja to je najmanjši pozitivni čas, za katerega je dl (to) = = d2 (to). Poiskali ga bomo grafično . Za g bo mo vzeli 10 ms- 2 . d[m] 20 dl , , , "" , d2, , / , -, / , / , a) Slika 1. Grafa funkcij dl(t ) = 10 / , I , I , = 20 - 5t2 in d2(t ) = 20t - 5t2 I ,I , se sekata p ri to = 1 s, kamna se I ,I to \ srečata čez 1 s v zraku na višini I \, I 15 m . ol 2 3 4 t [sl d[m] 30 dl 20 b) Slika 2. Grafa funkcij dl( t ) = 10 = 30 - 5t2 in d2(t ) = l Ot - 5t2 se d2 prvič zd ružita pri to = 2,45 s , t o --- --- ,, , je čas srečanja ob eh kamnov na / / , ' 1 t leh . ol 2 to 3 4 t rs] Marija Vence lj INovice ASTRONOMSKI TABOR NA BLOKAH Na radiu Ognjišče poteka že od februarja 2001 vsako dru go soboto v mesec u od daja Zanimivosti nočnega neba, ko jo pr ipravlja profesor Boris Kham. V nje nem okviru je bil od 11. do 13. julija 2002 na Blokah po- sku sno organiziran tridnevni astronomski tabor z naslovom Potovanje m ed galaksijami. Namen tabora je bil seznanit i ud eležence z osnovami astronomije in opazovanje steleskopom. P rišli smo z vseh koncev Slovenije, ob večerih pa so nas obiskali še domačini z okolice Blok. Podnevi smo spoznavali zvezdne kar te in ozvezdja, opa- zovali Sonce in Sončeve pege, ko pa na m je opazovanje pre- prečila oblačnost , smo izvedli nekaj preprostih fizikalnih po- skusov in vaj (merjenje gravi- t acijskega posp eška z nitnim nihalom , računanje mase Ze- mlje s pomočjo Newtonovega gravitacijskega zakona, to plo- tni to k s Sonca). Zvečer smo se podali na lov za galaksi- jami , kopicami in planet arnimi meglicami . Naš cilj so bili Messierjevi obj ekti (M4, M13, M16 , M18, M20, M26 , M27, M29 , M39, M51, M53, M56, M80, M92 , M I01, M108). Po skusni tab or je uspel. Zanimivi program je bil brez- hibno izpeljan , motivirani Delo v "d nevni izme ni" . smo bili pr av vsi udeleženci. Spot oma so se razvile tudi zanimive debate, usp elo nam je na pravit i pr enekatero lepo fotografijo (glej naslovnico). Petra Vencelj Fizika 1 o ARHIMEDOVI KRONI Če ni res, je lepo povedano. Italijanski rek Zgodb o najdemo celo v nekaterih učbenikih fizike, zato jo pozn a pr ecej učencev . Sirakuški vladar Hieron II . je pr i zlatarju naročil kron o in mu dal v ta namen kos čistega zlata. Krona, ki jo je zlatar izročil Hieronu, je imela enako maso kot kos zlat a. A Hieron je pomislil , da ga je morda zlatar ogoljufal t ako, da je nekaj zlata nad omestil z manj dr agocenenim srebrom. Sum je zaupal Ar him edu, ki mu je že večkrat svetoval in je bil njegov dober znanec , kot t udi zna nec njegovega sina Gelona, celo njun sorodnik. Slika 1. Arhimeda, ki je bil roj en let a 289 , je ubil vojak let a 212, ko so Rimljani zased li Sirakuze. Hieron (306 do 215) je od let a 275 vlad al sam in od let a 240 skupaj s sinom Ge lonam. Tako bi zgo dbo bilo najbrž treb a postaviti pred let o 240 . Vse let nice zade vajo čas pred našim štet je m. I Fizika Arhimed je moral ugo toviti, ali je zlatu v kroni primešano srebro, ne da bi krono , ki jo je Hieron že posvetil bogovom, kakorkoli poškodoval. Arhimed je, tako pripoveduje zgodba, najprej prišel do odkritja, kako izmeriti prostornino krone. Ko je legel v banjo do vrha polno vode, je ugotovil , da je prostornina vod e, ki se prelije iz banje, enaka njegovi prostornini in da je prostornina vode v banji za toliko manjša, ko stopi iz nje. Od veselj a nad odkritjem je gol stekel po mes tu in vpil: "He ureka , heureka!" (Odkril sem , odkril sem!) . Nekateri v isti sapi omenjajo še zakon o vzgonu, ki ga je Arhimed tudi odkril. Po tem zakonu se teža potopljenega telesa navidez zmanjša za težo izpodrinjene vod e. B tem spoznanjem Arhimedu ni bilo t ežko rešiti naloge s krono. Izmeri ti je bilo t reba prostornino kosa zlata z maso krone in jo primerj ati s prostornino krone. Če bi bila prostornina krone večja kot prostornina kosa zlata , bi krona izpodrinila več vode kot kos zlata; to naj bi pomenilo , da je zlatu v kroni primešano srebro. Arhimedov poskus naj bi to zares pokazal in tako razkril zlatarjevo goljufijo. O zgodbi je prvi poročal rimski inženir Vi truvij v 1. stoletju našega štetja . Toda premi slek porodi sum , da so si zgodbo izmislili pozneje. Opi- sani postopek ne kaže domiselnosti , značilne za Arhimeda, in ne izkoristi zakona o vzvodu (glej Aristotel in Arhimed o vzvodu , Presek 24 (1996/97) 70.) in zakona o vzgonu . Še pomembnejši je praktični pomislek , da bi se po opis anem poskusu tedaj bilo težko odločiti, ali je zlatar ogoljufal vladarja ali ne. To razkrije kratek račun. Šlo naj bi za razmeroma lahko krono v obliki vejice z listi, zvite v venec. Take krone iz 4. stoletja pred našim štetjem so našli v Leti, Amfipoliju in Vergini v Grški Makedoniji ter v Dardanelah. Verginska krona , ki ji sicer manjka nekaj listov, ima prem er 18,5 cm in maso 714 g. Vzemimo, da masa krone meri 1000 g in premer posode z vodo, v katero jo potopimo, 20 cm . Ploš čina nj ene osnovne ploskve doseže 314 cm'' . V tablicah poiščemo gostoto zlata in srebra. Podatki segajo od 18,88 g/cm3 , za vakuumsko destilirano, do 19,3 g/cm3 , za lit o , in 19,4 g/ cm 3 , za monokristalno zlato , ter od 10,49 g/ cm 3 , za mononokristalno , do 10,492 g/cm3 , za vakuumsko destilirano srebro. V Arhimedovih časih niso vakuumsko destilirali kovin in ne vzgajali lepih velikih monokristalov, pa tudi tako čistih kovin kot danes niso mogli dobiti . Ker pač podatke potrebujemo, se odločimo za 19,3 g]cm" , za gostoto zlata , in 10,5 g/ cm 3 , za gostoto srebra, z zavestjo, da sta zadnji mesti lahko negotovi. 136 Fizika I Nas lednje vprašanje je prostorni na zlitin. V nekaterih pr imerih se ta razlikuje od vsote prostornin prvega in drugega element a, ki ju zli- jemo . Tudi v najobsežnejših tablicah snovnih konstant pa ni podatka o prostornini zlit ine zlata in srebra . Najbrž v tem primeru podatek ni potre- ben. Atoma imat a zelo podobno kemijsko zgradbo (po lmer obeh je enak 0,144 nm) in enako kr istalno zgradbo (ploskovno centrirano kubično mrežo z robom osnovne celice 0,407 nm v kristalu zlata in 0,408 nm v kristalu srebra). Zato lahko privzamemo , da se masi obeh atomov razlikujeta samo zaradi mas jeder in da v zlit ini le atomi srebra zasedejo mesta atomov zlata . Zlato na 79. mestu periodne pr eglednice ima relativno atomsko maso 196,97, srebro pa na 47. mestu relativno atomsko maso 107,87. T i masi sta v razmerj u 1,867; le-to se le malo razlikuj e od razmerja gostot 1,826. Zato privzam emo , da je prostornina krone kar vsot a prostornine zlata in pr ostornine srebra, ki ju sestavljata. Vzemimo, da je zlatar 300 g zlata zamenjal za 300 g srebra. Čisto zlato ima značilno rumeno barvo, medtem ko ima srebro "kovinsko barvo" (nekateri pravijo , da je br ezbarvno). To je povezano z valovno dolžino svet lobe, ki jo absorbira kristal. Odbita svetloba, v kater i ni t e sestavine, kaže značilno barvo. Že pr i 300 g srebra je zlit ina utegni la biti opazno bolj "bela" od čistega zlata. Morda je prav to zbud ilo Hiero nov sum? Večj i delež srebra bi bil še bolj tvegan. Barva se manj spremeni, če zlato zlijemo z bakrom. Toda baker ima gostoto 8,9 g/cm3 , torej je pr ecej manjša od gostot e srebra . Zato bi bilo primes bakra pri Ar him edovem poskusu laže odkriti. Pri navedeni izbiri je prostornina krone 700 g/19 ,3 gcm-3 + + 300 g/1O,5 gcm - 3 =64,8 ern". V izbrani posodi ji ustreza višin a vod e 64,8 cm3/314 cm 2 = 0,206 cm . Prostornina kosa zlat a z maso 1000 g je 1000 cm3/19,3 = 51,8 cm3 in ji v pos odi ustreza višin a vode 51,8 cm3 /312 cm2 = 0,165 cm . Razlika obeh višin dosež e komaj 0,041 cm = 0,41 mm. Tolikšno razliko gladin bi težko opazili s prostim očesom. Ustreza ji pro sto rn ina 0,041 cm . 314 cm 2 = 13 cm" vode, ki bi dodatno st ekla iz posode, če bi v zvrhano polno posodo najprej po topili kos zlata, ga vzeli iz vode in potem potopili kro no. Upoštevati je treba , da je gladina vode zaradi površinske napetost i ukrivljena ter da nekaj vode lah ko ostane na zlatu . Razlika višin in dodatna prostornina bi bili še manjš i, če bi bili masa kro ne in masa kosa zlata manjši, če bi zlat ar manjši del zlata nadomesti l s srebrom ali če bi imela posoda večj i pr emer. Fizika Z bolj domiselnim posku som pa bi Arhimed precej laže ugotovil , ali je zlat ar goljufal. Oprl bi se prav tako na zakon o vzvo du in zakon o vzgonu. Kr ono in kos zlata bi obes il na kr aj išči enakoročnega vzvoda, kakršnega uporab lja te htnica. Vzvod, ki bi bil na zraku v ravnovesju, bi se dvignil na strani krone, ko bi ga potopil v vod o. Krona z večjo prostornino bi izpodrinila več vod e z večj o maso od mase kosa zlata in bi bila za to navidez lažja. S pr ejšnjimi podatki ugotovimo , da se masa krone, ki ustreza njeni tež i, navidez zmanjša za 64,8 g, to je na 1000 g - - 64,8 g = 935,2 g, ker je gostot a vode 1 g/cm3 . Mas a , ki ustreza teži kosa zlata, pa se navidez zmanjša za 51,8 g na 1000 g - 51,8 g = 948,2 g. Razlike te h mas 948,2 g - 935,2 g = 13 g s potopljeno te ht nico t udi v Arhimedovih časih ne bi bilo težko ugotoviti . V tem primeru nap ake, ki smo jih omenili pri pr ejšnjem načinu merjenj a, ne bi motile. Poleg tega bi vzvod lahko uporabili t udi, če krona ne bi imela natančno enake mase kot kos zlata. Na zraku bi dosegli ravnovesje, če bi povečali ročico krone, v kolikor bi imela krona manjšo maso, ali če bi ročico zmanjšali, v kolikor bi imela krona večjo maso . Kaj se je dogaj alo v davnih časih , ne vemo in najbrž nikoli ne bomo vedeli. Ni pa dvoma , da so si veliko zanimivih zgodb izmislili kasneje z dobrim namenom , da bi pritegnili pozornost bralcev in poslušalcev. O eni od njih, v katero je bil pr av tako vpl eten Arhimed , je Presek že poročal. Trdni fizikalni razlogi govorijo za to, da rimskih ladij niso zažgali s sončno svet lobo, ki se je odbila na vdrtih ščitih (Arhimed in sežig ladij , Presek 21 (1993/94) 2). To ne pomeni, da bi bilo treba zanimive stare zgodbe pregnati iz šole. Prav pa je, če jih jemlj emo z zabav ne strani in v njih ne iščemo "na ravoslovne resnice". Pri računanju smo uporabili naslednje enačbe: a) za ploščino kroga, to je dna posode: p = 7fr2 , če je r polmer kroga, b) za prostornino valja: V = 7fr2 h , če je h njegova višina, c) zvezo med maso in prostornino: m = pV, če je p gostota, in d) zvezo med težo in maso: F = mg, če je g težni pospešek. Zaradi zadnje zveze smo lahko razpravljali o masi, ki ustreza teži , čeprav zakon o vzgonu pravi, da se teža potopljenega telesa navidez zmanjša za težo izpodrinjene tekočine. Janez St rn ad Računalništvo I ŠTEVILSKI LABIRINT P red časom sem nalet el na naslednjo različico iskanj a izho da iz labi- rinta. Namesto običajne slike labirint a dobimo pravokotno tabe lo na- ravnih števil, na primer tako, kot je prikazana na sliki 1. Na začetku se nahajamo na enem od polj tabe le, rec imo v levem zgornjem vogalu . Naš cilj je priti do nekega izbranega polj a t abele, ki predst avlja izhod iz lab irint a . Pri t abeli s slike 1 naj bo to desni spodnji vogal. Premikanje po lab irintu po teka takole: Če smo na polju, na katerem je napisano število k , potem se lahko prem aknem o za k mest v desno, za k mest v levo, za k mest navzgor ali za k mest navzdol. Seveda pa pri te m ne sme mo stopiti čez rob t abe le. 3 2 3 4 3 3 1 3 3 2 1 3 5 3 3 2 2 4 1 3 3 3 3 3 1 4 2 3 2 5 Slika 1. Štev ilski labir int . Za labirint s slike 1 je ena od možnih poti do izhoda prikazana na sliki 2. Seveda pa pri vseh številskih labirintih ni moč priti do izhoda. Tako na primer labirint s slike 1 nima rešitve, če mu izhod prest avimo v desni zgornj i vogal. ® CD ci) (!) 0 ® Slika 2. Pot skozi labirint s slike 1. Računalništvo In kako se lotiti iskanja izhod a iz št evilskega labirint a? Seved a se iskanja lahko lotimo s poskušanjem in se pri t em zanašamo na navdih ter zaupamo v srečo . Če pa želimo zanes lj ivo pot do rešit ve, je priporočljivo , da se reševanj a lotimo bolj urejeno in sistematično . Ena od možnih poti je naslednja : Polj a t abele bomo postopoma oštevilčili tako, da bo št evilka , prirejena pos ameznemu polju, povedala , koliko potez smo potrebovali , da smo z začetnega prišli do tega polja . Začetno polje označimo s številko O. Nato poljem , na katera lahko pri- demo s polj a številka O, do delimo številko 1. V naslednjem koraku še neoštevilčenim polj em , na katera lahko pridemo s po lj , ki imajo št evilko 1, dodelimo številko 2. Post opek ponavljamo, dokler številke ne dobi tudi polj e, na katerem je izhod iz labirint a. Številka , dodeljena izhodu, pove, koliko potez potrebujemo, da pridemo iz labirint a . Vendar pa se postop ek vedno ne izide. Lahko se namreč zgodi, da na nekem koraku ne moremo več priti na nobeno neoštevilčeno polje , do po lja, na katerem je izhod, pa še nism o prišli . V takem primeru poti iz labirint a ni . o 3 1 4 4 3 4 2 4 3 1 2 4 3 2 3 2 4 Slika 3. Iskanje po ti skozi labirint . Če opisa ni postop ek up orabimo na labirintu s slike 1, dobimo tabelo št evil s slike 3. Številka 4 v desnem spodnjem vogalu pove, da je iz labirinta moč priti v št ir ih potezah, torej potezo hitreje, kot to naredimo z rešit vijo s slike 2. In kako poiščemo poteze, ki jih moramo naredi ti , da pridem o iz labirint a? Verj etno je najlažje, da si jih beležimo kar spro ti . Vsakič , ko neko polj e oštevilčimo, si tudi zapomnimo, s katerega polj a (z za eno manjšo št evilko) smo nanj prišli. Včasih je t akih polj več. Takrat si zapo mnimo katerokoli od njih. Up oštevaj t e nasvet in poiščite št ir i poteze, ki nas pripeljejo do izhoda iz labirinta s slike 1. 140 Računalništvo I Ko se reševanj a s svinčnikom in papirjem naveličamo, lahko gornj i postopek zapiše mo t udi v obliki računalniškega programa. V nadaljeva nju je zap isana le fun kcija , ki opravi glavni del računanja , branje podatkov o labirintu in izpis ugotovitev pa boste morali dod ati sami. int resi (int lab [MAX] [MAX] , int m, int n, int pot [MAX] [MAX] [3] ) { i nt i, j, poteza, konec , t; for (i = O; i < m; i++) for (j = O; j < n; j++ ) pot [iJ ej] [O] = pot Ci] ej] [1] = pot Ci] [j] [2] -1 ; 1* začetni položaj in začetna poteza *1 poteza = pot [O] [O] [O] = O; do { konec = 1; for (i = O; i < m; i++) for (j = O; j < n ; j++) if (pot[i] ej] [O] == poteza) { 1* gremo na levo *1 ii ((t = j - lab Ci] [j]) >= O && pot Ci] et] [O] pot[i] et] [O] = poteza + 1; konec = O; pot[i] et] [1] = i; pot[i] et] [2] = j ; } 1* gremo na desno *1 ii ((t = j + lab[i] [j]) < n && po t j i.] et] [O] pot[i] et] [O] = poteza + 1; konec = O; pot[i] [t][l] = i ; pot[i] et] [2] = j; } 1* gremo na vzgor *1 ii ( (t = i - lab Ci] [jJ) >= O && pot et] ej] [O] pot[t] ej] [O] = poteza + 1; konec = O; pot et] [j] [1] = i ; pot et] [j] [2] = j; } 1* gremo na vzdol *1 ii ((t = i + Lab lL] [jJ) < m && pot Itl [j] [O] pot[t] ej] [O] = poteza + 1 ; konec = O; pot[t] [j] [1] = i; pot[t] ej] [2] = j; } -1) { -1 ) { -1) { - 1) { } } poteza++; } while (pot[m - 1] [n - 1] [O] return !konec; -1 && !konec); Računalništvo - Naloge Funkcija vrne vrednost 1, kadar obstaja pot do izhod a iz labirinta , sicer vrne vrednost O. Komponenti 1 in 2 v tabeli pot povest a , od kod smo pri šli na dano polj e, komponent a Opa, koliko pot ez smo potrebovali. Funkcija ni napisan a najbolj varčno . Z dodatno pomožno funkcij o bi njeno kodo lahko nekoliko skraj šali , še bolj moteča pa je potratnost izvedbe postopka. V vsaki ponovitvi zanke do namreč pregledamo celotno tabelo, čeprav je v njej morda le nekaj polj , iz katerih lahko naredimo nove poteze. Ta polj a bi si lahko na vsakem koraku zabe ležili v pomožno eno- razsežno t ab elo in se tako izognili vsakokratnemu pot ratnemu preverj anju vseh polj. T ist i, ki poznate osnove algoritmov, ste v gornjem postopku verj etno prepo znali eno od raz ličic pre gleda grafa v širin o. Končajmo z nalogo. Na sliki 4 vas čaka "še neraziskan" številski labirint . Začnete v levem zgornjem vogalu, izhod pa je v desnem spodnjem vogalu. Seveda iščete t ako pot do izhoda, ki zahteva čim manj potez. 6 1 2 1 4 1 2 1 2 1 1 4 4 2 2 2 1 4 4 6 2 1 4 1 4 1 4 2 4 1 1 6 1 2 1 4 1 4 1 2 6 8 6 1 2 2 4 6 4 4 1 2 1 2 1 6 1 6 1 4 6 1 2 4 2 4 4 4 5 1 Martin Juvan TRI POSODE Gostilničar je kupil 50 litrov vina, 2 litra odlil v štefan , ost alo pa nalil v t ri enake posod e, vendar v različnih količinah . Rad bi , da bi bile posode tudi enako polne, zato začne vino pretakati . Najprej iz ene posod e od lije polovico vina enakomerno v drugi dve posodi (to je, v vsako enako količino) . Nato odlije iz druge posod e polovico vsebine ena komern o v prvo in tretj o posod o in nazadnje polovico vsebine tretje posod e enakomerno v prvi dve posodi. Presrečen opazi, da je dosegel, kar je želel, da so gladine v vseh treh posodah enako visoko. Koliko je bilo vina na začetku v posam eznih posodah? Marija Vencelj Rešit ev je na strani 168. Matematika I KOTI V PRAVILNEM PETKOTNIKU Kot je razvidno na sliki, v pravilnem petkotniku ABCDE s središčem v točki S povsem naravno nastopajo koti 18°, 36° ,54° in 72° , ki so vsi večkratniki kota 18° . E A c Za kot e 30°,45° in 60° ni tež ko najti vrednost i kotnih funkcij , saj si pom agamo z enakostraničnim trikotnikom in kvadratom . Rezult atov si t udi ni težko zapo mnit i. Navadno pa najdemo v učbenikih za kotne funkcije kotov , ki jih srečamo v pravi lnem petkotniku, precej zaplete ne izpeljave. Za nekatere od njih je treba obvladat i celo kompleksna števila ter ena čbe t retje in četrte stopnje. Ogled ali si bom o, kako lahko enost av- neje do bimo izraza za sinus in kos inus kot a 54° . Rezult at nam omogoča izračun vrednosti kotnih funkcij t udi za ostale kote v pravilnem petkotniku in geomet rijs ko konstrukcijo pravilnega petkotnika, če pozn amo njegovo st ranico a. Najprej opazimo, da velja 2 . 54° = 270° - 3 . 54° . Nato se spomnimo znanih identit et sin 20: = 2 sin o:cos o: , cos 20: = 1 - 2 sin2 o: , sin( 270° - 0:) = - cos o: . IMat ematika Nekoliko manj znana je identitet a za kosinus t rojnega kot a , ki pa jo dobimo iz adi cijskega izreka in prejšnjih identitet (ali tudi iz Moivreove formule): cos So = cos(2a + a) = cos 2a cos a - sin 2a sin a = cos o fl - 4 sin2 o ) . Označimo x = sin 54° , y = cos 54° . Očitno je O< x < 1 in O< Y < 1. Ker velja dobimo od tod naj prej 2xy = -y(1 - 4x 2 ) , po kr aj šanju z y in po preuredi t vi pa je pred nami kvadratna enačba 4x 2 - 2x - 1 = O. Njeni rešitvi st a Ker je X2 negativno število, imamo nazadnj e sin 54° = ~(1 + VS). Število 1 ep = -(1 + VS) 2 smo že srečali v Preseku (Presek 27 (1999/2000) , 34). Imenuj emo ga število zlatega reza (zlato raz merje , označujemo ga t udi T), ker nastopa pri zlatem rezu, zlatem pr avokotniku , zlati spirali. Potence števila ep s celimi ekspo nent i se linearn o izražaj o s ep samim, koeficienti pa so F ibonaccijeva šte vila. Trditev te melji na tem , da število ep = 2X 1 zadošča enačbi ep 2 = = ep + 1, iz katere dob imo ep " , oziro ma enačbi ep -1 = ep - 1, ki nam da izraz e za ep - n, kjer je n naravno število. 144 Mat ematika I Nekateri menij o, da se oznaka 4> uporablja v čast starog rškemu ki- parju Fidiji , ki je zlati rez upor abljal pri svojih moj strovinah, drugi pa stavijo, da oznaka pride od Fibon accija. Kakorkoli že je, velja . 1 sm54° = "2 4> . P od obno idejo , ki nas prived e do kvadratne enačbe , lahko up orabimo t udi za sinus kota 18° . Začnemo z enakostjo 2·18° = 90° -3 ·18° in nadaljujem o podobno kot pri sinusu kota 54° . Lahko pa up orabimo do blje ni rez ultat in enakost 2 sin218° = 1 - cos36° = 1- sin 54° = ~ (2 - 4» . Tako dob imo najprej . 2 ° 1 ( ) 1 ( )2sin 18 = =1 2 - 4> = =1 4> - 1 , nato pa . ° 1 ( ) 1sm 18 = - 4> - 1 = - . 2 24> S številom 4> se izražajo t ud i 1 ~ . 1 ~ sin 36° = "2 V 3 - 4> , sin 72° = "2 V 2 + 4> . P rav tako lahko s št evilom 4> zapišemo tudi kosinuse, tangense in kotangense tistih večkratnikov kota 18° , ki ležijo med kotoma O° in 90° , kot kaže razprede lnica . ~ sin tg D 18° ~)2 - 4> iJ35 - 204> 72° 36° ~J3 - 4> ) 7 - 44> 54° 54° ~4> iJ15 + 204> 36° 72° ~J2 + 4> J3+ 44> 18° o cos ctg Br alec bo z lahkoto zapisa l vrednosti v zgornj i razpred eln ici v običajni ob liki, s kvadratnimi koreni , Čemu nam vse to lahko kori sti ? Matematika V učbenikih običajno najdemo geomet rijsko konstrukcijo pravilnega petkotnika, ki je včrtan dani krožnici. Po skusimo sedaj konstruirati pra- vilni petkotnik z dano stranico a. Njeni kraj išči označimo z A in B , ki bosta hkrati že dve oglišči iskanega lika . V A in B narišemo pravoko tnici na daljico AB in kons truiramo kvad ra t ABF G. Razpolovišče stranice AG označimo s H , potem pa načrtamo krožni lok s središčem v H skozi F. Kr ožni lok preseka pod aljšek stranice AG v točki I . Na tem podaljšku določimo še točko J , ki je od A oddaljena 2a. Ker je po Pi tagorovem izreku 1 IHII = IH FI = '2 aJ5, dobimo 1 1 IAI I = IAH I + IH I I = '2 a+ '2aJ5 = a4J . Skozi 1 načrtamo vzporednico stranici AB, ki jo krožni lok s središčem v A skozi J preseka v točki K . Takoj vidimo , da premica skozi A in K oklepa z dalj ico AB kot 54° . Velja namreč . IAII a4J 1 SlU n ali X n :::; m - (n - 1) < 1, saj je n 2': 5 > 3.) 190 Tekmovanja I Št evilo X l + X 2 + ...+ X n-2 = nm - X n - X n - l = (n - l)m - X n- l je deljivo z n - 2, zato je Xn - l == m(n - 1) == tri (mod (n - 2)) . Sedaj pa podobno kot zgor aj sklepamo, da mora biti X n - l = m, saj bi v nasprotnem imeli Xn- l 2 m + (n - 2) > n ali X n - l :::; m - (n - 2) < 1, saj je n 2 5. Ker smo dokazali, da mora biti X n = X n- l, števila X l , X2, . . . , X n ne tvorijo permutacije števil 1, 2, . . . , n , saj niso vsa različna. 11/2. Označimo središče kro žnice K z O, presečišče premic BF, CE In tangent skozi A in D pa z X . Če je B C II EF, je B C ..1 OX in EF ..1 OX. Ker je AD ..1 OX, so premi ce B C , E F in AD vzporedne. . .. . . . . . x ' p -- - -- --,- ... .. y Na j sedaj pr emi ci B C in EF ne bosta vzp oredni. Označimo presečiš­ če pr emic B C in EF z Y , dr ugo presečišče pr emice D Y s kro žnico K pa z A' . Dokazati moramo, da je A' = A. Označimo pr avokotno projekcijo točke X na premico DY z C , presečišče trikotniku B CX očrtane krožnice s premico XY pa s P . Tekmovanja S koti enostavno preverimo, da je št ir ikot nik Y PBF t etiven. (Lahko pa tudi op azimo, da je točka B pravzaprav Miquelova točka t r ikot nika Y X E t er izbranih točk P , C in F na nj egovih stranicah .) Po izreku o poten ci točke na kro žni co lahko zapišemo IX P! ·IXYI = IXBI ·IXFI = IXDI2 in IYPI·IYXI= IYBI·IYCI= IYA'I ·IYDI· Ko seštejemo gornj i enačbi, dobimo IXYI 2 = IXDI 2 + IYA'I . IYDI , kar lahko zapišemo v obliki IXYI2 - IXDI2 = IYA'I · IYDI. Ker je GX .L DY, lahko zapišemo IXYI2 = IGy/2+ IGXI 2 in IXDI 2 = IGDI2 +IGXI2 . Torej je IXYI2 -IXDI 2 = (IGYI+ IGDJ) (IGYI-IGDJ) = IYDI · (IGYI-IGDJ) . Ker paje IXYI 2 - IXDI2 = IYA'I·IYDI, iz gornjih enačb sledi IYA'I = = IGYI- IGDI in zato IGA'I = IGDI. Točka Gje t ako razpolovišče tetive DA' in je OG -l DA' . Torej so točke O , G in X kolinearne in sta si točki D in A' simetrični glede na premico OX. Ker st a si tange ntni točki A in D tudi simetrični glede na prem ico OX, je zato A' = A . 11/3. Dokažimo, da je ustrezen način en sam: v vsa polj a vpišemo 1. Trditev bomo dokazali s protislovjem. Naj bo n najmanjše število, za katerega obstaja ustrezna tabe la A = [aij] razsežnosti (2n -1) x (2n -1 ), v kateri smo zapisali vsaj eno število -1. Če i-ta vr sti ca tabele A ni simetrična glede na srednje polje, tvorimo novo tabelo B = [bij ], kjer je če je j = 2n - 1 če je j i= 2n - 1 . V tabeli B je sedaj i-ta vrstica simetrična glede na srednje polje. Ko postopek ponovimo za vse nesimetrične vrstice , dobimo po vrsticah si- metrično t abelo, ki ima še vedno lastnost , da je število v vsakem polju produkt št evil v sosednjih poljih. V vsaj eni vrsti im amo št evilo -1 , saj bi sicer bile vse vrstice že v t abeli A simetrične glede na srednje polje. Torej lahko privzamem o, da je tabe la simetrična po vrsticah. Podobno lahko privzamem o, da je tabe la simetrična t udi po stolpci h. 192 Tekmovanja I Naj bo torej A tabela razsežnost i (2n -1) x (2n -1), v kateri imamo vsaj eno število enako - 1, vsaka vrs ti ca in vsak stolpec t abele pa je simetričen na srednje po lje. Oglejmo si srednjo vrstico te tabele . Če je prvi element te vrstice enak 1, so vsi elementi v t ej vrstici enaki 1. Če pa je prvi element te vrstice enak - 1, mora biti vrstica oblike - 1, -1, 1, - 1, -1 , 1, . .. , 1, -1, -1. Torej je v vrstici 2 (mod 3) števil. Slednje pa ni možno, saj je 2n - 1 oj. 2 (mod 3) . Po dobno sklepamo, da so tudi v srednjem stolpcu vsa števila enaka 1. Ko iz tabele izrežemo srednjo vrstico samih enic in srednji stolpec samih enic, dobimo štiri manjše tabele razsežnosti (2n - 1 -1) x (2n - 1_1) . V vsaj eni izmed njih (recimo Al) je vsaj en eleme nt enak -1. Ker pa smo ob robu t abele Al imeli pas samih enic, je tudi v tabeli Al vsako število produkt števil v sosednjih po ljih . Torej bi lahko ti zmanjšali, kar pomeni, da je že na začetku bil ti = 2. V tem primeru pa imamo tabelo 3 x 3, pri kat eri sta srednja vrstica in srednji stolpec enaka 1,1,1. Torej so vsi elementi enaki 1. Skratka, pokazali smo, da nas privzetek, da imamo v tabeli vsaj eno število enako - 1, vodi v protislovje . Ma tjaž Željko PRESEK list za mlade matematike, fizike, astroname in računalnikarje 30. letnik, šolsko leto 2002/03, številka 3, strani 129-192 UREDNIŠKI ODBOR: Vladimir Batagelj, Tanja Bečan (jezikovni pregled) , Mirko Dobovišek (glavni urednik), Vilko Domajnko, Darjo Felda (tekmovanja), Bojan Golli, Marjan Hribar, Boštjan Jaklič (tehnični urednik), Martin Juvan (računal­ ništvo), Sandi Klavžar, Boris Lavrič, Andrej Likar (fizika), Matija Lokar, Franci Oblak, Peter Petek, Marijan Prosen (astronomija), Marija Vencelj (matematika, odgovorna urednica). Dopisi in naročnine: DMFA - založništvo, Presek, Jadranska ulica 19, 1001 Ljublja- na, p .p . 2964 , tel. (Ol) 4766-553 , telefaks (Ol) 2517-281. Naročnina za šolsko leto 2002/03 je za posamezne naročnike 3.300 SIT (posamezno naročilo velja do preklica) , za skupinska naročila šol 2.700 SIT, posamezna številka 825 SIT, tematska številka 1.650 SIT, stara številka 650 SIT, letna naročnina za tujino 25 EUR, devizna nakazila SKB banka d.d, Ljubljana, Ajdovščina 4, Ljubljana, SWIFT: SKBASI2X, transakcijski račun številka 03100-1000018787. List sofinancira MŠZŠ Za ložilo DMFA - založništvo Tisk: DELO Tiskarna, Ljubljana © 2002 Društvo matematikov, fizikov in astronomov Slovenije - 1519 Poštnina plačana pri pošti 1102 Ljubljana Slovenska olimpijska ekipa na 33. mednarodni fizikalni olimpiadi na Baliju v Indoneziji. Od leve proti desni: Jure Bajc, Gašper žerovnik (pohvala), Davorin Učakar, Matjaž Humar (pohvala) , Andraž Stožer (pohvala) , Matija Perne (zlata medalja), Ciril Dominko. Ekipa Slovenije na 43 . mednarodni matematični olimpiadi v Glasgowu. Od leve proti desni: Matjaž željko (vodja ekipe), Erik Štrumbelj (pohvala), Tine Porenta, Tone Gradišek , Aleksandra Franc , Janez Šter, Klemen Šivic (bronasta medalja) in Gregor Dolinar (član mednarodne tekmovalne komisije) . ,: