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ð.

 

 

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.

Þ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.

Þ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.

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.

Þ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:

Markmiðið er að teikna óslitinn feril (hann má vera með sveigjum), 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.