i
i
“1023-Domajnko-2” — 2010/7/1 — 10:00 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 18 (1990/1991)
Številka 1
Strani 36–38
Vilko Domajnko:
Z GRAFI GRE LAŽJE
Ključne besede: razvedrilo, Presekova nadloga, naloge.
Elektronska verzija:
http://www.presek.si/18/1023-Domajnko-nadloga.pdf
c© 1990 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.
36
Z GRAFI GRE LAžJE PRESEKOVA NADLOGA
Niz letošnjih Presekovih nadlog bomo začeli z zbirko rekreacijskih nalog. ki
v teoriji grafov pogosto služijo kot slikovito dopolnilo .
Poglejmo torej!
1. Prva je iz zbirke znamenitega ameriškega sestavljalea ugank Sama
Loyda (1841 - 1911).
V začetku tega stoletja je planet Mars seveda še zmogel na vse pretege
buriti domišljijo Zemljanov. In tako je zviti Loyd narisal zemljevid Marsa z
nekaterimi "tedaj pravkar odkritimi" mesti in z vodnimi kanali. ki povezujejo
ta mesta . Od reševalcev uganke je zahteval. da poiščejo pot. ki vodi skozi
vsako izmed označenih mest natanko po enkrat. Toda pri tem je treba začeti
in končati v mestu. ki leži ob južnem polu planeta in je označeno s črko S
(glej sliko 1) . Pot. ki jo bo predlagal reševalec . pa mora nositi v sebi še nek
dodatni pomen. ki ga še nočemo izdati. Močno se namreč nadejamo. da ga
bo odkril kar reševalec sam.
Še tole zanimivost je vred no omeniti pri tej uganki. Loyd jo je objavil
kar dvakrat. In to kljub temu. da je že po prvi objavi uganke dobil pravcato
goro pisem. v katerih so mu reševalci sporočali : "Saj sploh ni takšne poti."
Res je bil nabrit. ta Loyd. ni kaj!
Slika 1 Slika 2
2. Na sliki 2 je načrt neobičajne zgradbe z mnogo vrati. Povejte. ali se
je mogoče sprehoditi skozi to zgradbo tako. da gre spreh ajalee skozi sleherna
vrata natanko enkrat.
37
3. Z labirinti in z zamotano hojo po njih ste se v lanskem letniku Preseka
že spopadli (glej Presek 3). Tokrat je pred vami primer . ob katerem boste
lahko uporabili pridobljeno znanje.
V kraju Hampton Court v Angliji imajo znamenit labirint. Domnevam .
da vas takle labirintek ne bo spravil v prehudo zadrego in da vam torej ne
bo pretežko poiskati kakšne izmed odrešilnih poti. ki vodijo ven iz sredine
labirinta (od točke A do točke Ž). Nekoliko težje pa je najbrž poiskati vse
take različne poti. In glej. prav to zahteva ta naloga! Pravzaprav - dovolj bo .
če poveste le. koliko teh poti je.
Pri tem iskanju ne štejte tistih . pri katerih je treba iti po kakšnem delu
več kakor le enkrat.
ž
Sli ka 3 Sli ka 4
4. Slika 4 nam predstavlja načrt mestnega parka. Njegovi skrb niki so se
odločili. da bo v zabavo vseh meščanov po poteh parka vozil majhen otroški
vlakec. Skozi park bi naj vozil po krožni poti. ki bi naj bila speljana tako. da
bi skozi vsako izmed kri ži š č parka peljala natanko enkrat. Pri tem ni nujno.
da bi vlak vozil po vseh poteh parka . Obenem pa načrtovalci takšne krožne
vožnje tudi ne želijo. da bi šel vlak po kakšni izmed poti večkrat.
Toda . glej. nesreča res nikoli ne počiva - krožne vožnje. ki bi ustrezala
vsem opisanim zahtevam . sploh ni mogoče speljati.
Ali znate pojasniti. zakaj ne?
5. Šest dobrih prijateljev živi v šestih razli čnih mestih . Ker nočejo . da
bi njihovo prijateljstvo in poznanstvo sčasoma usahnilo . so se domenili. da se
bodo vsak teden v sredo poklicali po telefonu in si med seboj pripovedovali
vsaj šale . če že ne kaj drugega .
38
Trdijo. da so uspeli svoje sredine telefonske pogovore sčasoma že tako
izmojstriti. da jim sedaj zadošča že vsega skupaj samo osem pogovorov. da
vsak izmed njih izve vse šale preostalih petih prijateljev.
Vendar se mi zdi. da je osem presneto nizko število pogovorov in tako
res ne vem. če naj jim verjamem.
Pomagajte!
6. Mož in žena iz družine Bel čev] sta priredila hišno zabavo in nanjo
povabila še dvoje zakonskih parov - Modrinjakova in Rumenjakova dva. Vsi
stari znanci so se ob snidenju. kakor se seveda spodobi. najprej rokovali.
Vendar pa je bilo med tedaj zbranimi tudi nekaj takšnih . ki se še niso poznali.
Ti se niso med seboj rokovali.
" : :" :'.:., .,.-
Ko so bili že vsi zbrani. je Belec kot prireditelj zabave povprašal vsakega
izmed prisotnih . kolikokrat se je rokoval. Pri tem je za čud a dobil od njih
same različne odgovore.
Povej. kolikokrat se je rokovala Belčeva žena. Pri tem upošteva], da
- se mož in žena z enakim priimkom med seboj nista rokovala :
• se nihče ni rokoval s samim seboj:
- se nihče ni z nikomer rokoval več kakor enkrat .
Vilko Domajnko