Brýrnar í Köningsberg

Brýrnar í borginni Königsberg í Prússlandi, nú Kaliningrad sem tilheyrir Rússlandi, þó að hún sé víðs fjarri því, náðu heimsfrægð. Gegnum borgina liggur áin Pregel sem skiptir borginni í fjóra hluta, A, B, C og D eins og sést á myndinni. Sjö brýr tengja þá saman eins og myndin sýnir.

Íbúar í Königsberg skemmtu sér við það á sunnudögum að fara yfir allar brýrnar, en aðeins einu sinni yfir hverja. Lesendur gætu haft gaman af því að reyna að leysa þrautina áður en lengra er haldið.Brýrnar í Köningsberg

 

 

Hvernig sem þeir reyndu, þá tókst engum það. Menn drógu þá niðurstöðu af því að það væri ekki hægt, en hvernig á að sanna það?

Hinn þekkti stærðfræðingur Euler fann lausn sem byggir á graffræði. Mér hefur alltaf fundist lausn hans flókin og hugsaði þetta á einfaldan hátt (þó að grunnurinn sé auðvitað sá sami). Ég leysi þetta svona:

Einhvers staðar verður að byrja. Gerum ráð fyrir því að við byrjum ekki á efsta svæðinu C. Þá þurfum við að fara inn á svæðið (til dæmis um brú c eins og myndin sýnir) förum svo út aftur (segjum um brú d) og komum svo inn í annað sinn um brú g. Sem sé tvisvar inn og einu sinni út.

Brýrnar í Köningsberg C

Það er að segja. Ef við byrjum utan svæðis C, þá hljótum við að enda inni á svæðinu, vegna þess að við megum aldrei fara oftar en einu sinni yfir neina brú. Samkvæmt þessu er sama hvort við byrjum á A, B eða D; við hljótum að enda á svæði C.

Við gerum það sama fyrir öll hin svæðin.

Næst skulum við gera ráð fyrir því að við byrjum ekki á neðsta svæðinu B. Þá þurfum við að fara inn á svæðið (til dæmis um brú a eins og myndin sýnir) förum svo út aftur (segjum um brú b) og komum svo inn í annað sinn um brú f. Aftur tvisvar inn, einu sinni út.

Brýrnar í Köningsberg B

Það er að segja. Ef við byrjum utan svæðis C, þá hljótum við að enda inni á svæðinu, vegna þess að við megum aldrei fara oftar en einu sinni yfir neina brú. Samkvæmt þessu er sama hvort við byrjum á A, C eða D; við hljótum að enda á svæði B.

Ég læt nægja að birta myndina af A. Þó að brýrnar þar séu fimm, þá er röksemdafærslan hliðstæð. Ef við byrjum utan A, þá hljótum við að enda inni á því (förum inn þrisvar og út tvisvar). Samkvæmt þessu er sama hvort við byrjum á B, C eða D; við hljótum að enda á svæði A.

Brýrnar í Köningsberg A

Loks sjáum við að alveg á sama hátt er niðurstaðan sú ef við byrjum utan D, hljótum við að enda þar. Samkvæmt þessu er sama hvort við byrjum á A, B eða C; við hljótum að enda á svæði D.

Brýrnar í Köningsberg D

Þetta er augljóslega ómögulegt. Ef við byrjum á A hljótum við að enda á B. En við munum líka enda á C og loks munum við líka enda á D, það er að segja við endum á þremur mismunandi stöðum. Það sama gildir ef við byrjum á einhverjum hinna staðanna. Niðurstaðan er því sú að þetta leiðir til þversagnar. Þar af leiðandi er ómögulegt að fara yfir allar brýrnar.

Þessa aðferð er hægt að nota til þess að leysa eftirfarandi þraut:

Þraut fyrir grein um Köningsberg

Markmiðið er að teikna óbrotna línu, sem sker sjálfa sig ekki, og fer gegnum hvert strik í kassanum á myndinni nákvæmlega einu sinni. Þetta hefur gert marga gráhærða, rétt eins og brýrnar í Köningsberg.

Um lausn Eulers á brúavandanum má lesa hér.

 

 

Færðu inn athugasemd

Skráðu umbeðnar upplýsingar að neðan eða smelltu á smámynd til að skrá þig inn:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Breyta )

Google photo

You are commenting using your Google account. Log Out /  Breyta )

Twitter picture

You are commenting using your Twitter account. Log Out /  Breyta )

Facebook photo

You are commenting using your Facebook account. Log Out /  Breyta )

Tengist við %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.