Sólin Sólin Rís 10:52 • sest 15:43 í Reykjavík
Tunglið Tunglið Rís 00:00 • Sest 00:00 í Reykjavík
Flóð Flóð Árdegis: 07:25 • Síðdegis: 19:43 í Reykjavík
Fjaran Fjara Árdegis: 01:09 • Síðdegis: 13:45 í Reykjavík
Sólin Sólin Rís 10:52 • sest 15:43 í Reykjavík
Tunglið Tunglið Rís 00:00 • Sest 00:00 í Reykjavík
Flóð Flóð Árdegis: 07:25 • Síðdegis: 19:43 í Reykjavík
Fjaran Fjara Árdegis: 01:09 • Síðdegis: 13:45 í Reykjavík
LeiðbeiningarTil baka

Sendu inn spurningu

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=
Forsíða Vísindavefur Gátur og heilabrot Er hægt að leysa þessa þraut sem ég og vinnufélagarnir höfum glímt við í meira en eitt ár?

Flokkun:

4.7.2008
Vísindavefur Gátur og heilabrot
Náttúruvísindi og verkfræði Stærðfræði

Er hægt að leysa þessa þraut sem ég og vinnufélagarnir höfum glímt við í meira en eitt ár?

Gunnar Þór Magnússon

Þrautin sem um ræðir sést á mynd 1 hér fyrir neðan. 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.



Mynd 1 - Þrautin

Ein tilraun að lausn sést á mynd 2. Þar höfum við þó lent í sjálfheldu, því enn vantar að fara gegnum strikið sem er merkt með rauðu, og við komumst ekki til þess án þess að fara aftur gegnum eitthvað annað strik.



Mynd 2 - Tilraun að lausn

Lesendur eru hvattir til að spreyta sig á þrautinni áður en þeir lesa áfram.

Til þess að svara spurningunni er þægilegt að grípa til svokallaðrar netafræði. Það er grein innan stærðfræði sem hefur verið þróuð til að leysa þrautir sem þessar og önnur svipuð vandamál, þar sem tengingar og sambönd milli hluta skipta máli, frekar en fjarlægðir og stærðir. Til dæmis er netafræði beitt í öllum tækjum sem gefa upp bestu leiðina til að keyra á milli tveggja staða, því þá skiptir frekar máli að vegir liggi á milli staðanna en að upphafs- og lokapunktur séu nálægt hvor öðrum.

Til þess að geta talað um netafræði þurfum við nokkur hugtök hennar. Þau eru einföld og auðskiljanleg. Eins og nafnið gefur til kynna snýst netafræði um net. Sérhvert net samanstendur af hnútum, sem við getum teiknað sem punkta í plani, og leggjum, sem við teiknum sem strik á milli punktanna. Þannig er mynd 3 hér á eftir af einföldu neti, sem hefur hnútana a, b, c og d, og nokkra leggi á milli þeirra.



Mynd 3 - Dæmi um net

Athugið að við getum haft fleiri en einn legg milli tveggja hnúta. Til dæmis eru tveir leggir á milli hnútanna c og d á myndinni. Ef við hugsum um hnútana sem mismunandi staði á Íslandi og leggina sem vegi á milli, þá svarar þetta til þess að tveir mismunandi vegir liggi á milli staðanna.

Nú skulum við breyta þrautinn okkar í net. Við lítum á hvern lítinn kassa sem hnút, og bætum svo við einum hnúti sem táknar allt sem er fyrir utan kassann. Þessa hnúta merkjum við með bókstöfunum frá a upp í f



Mynd 4 - Hnútarnir í þrautinni

Næst tengjum við á milli hnútanna ef við getum komist frá einum kassa í annann. Á mynd 5 fyrir neðan hefur þetta verið gert fyrir hnútinn a. Við tengjum sitt hvorn legginn frá a í hnúta b og d, og tengjum svo tvo leggi frá a í hnút f, vegna þess að úr kassa a komumst við út úr stóra kassanum gegnum tvö mismunandi strik.



Mynd 5 - Leggir lagðir út frá hnúti a

Þetta endurtökum við fyrir hina hnútana, og fáum að lokum netið á mynd 6. Spurningin í þrautinni snýst nú um hvort við getum byrjað í einhverjum hnút, og fundið veg sem fer nákvæmlega einu sinni um hvern legg í netinu.



Mynd 6 - Þrautin gerð að neti

Verkefni af þessu tagi eru algeng í netafræði og vegir eins og sá sem er spurt um kallast Euler-vegir eftir svissneska stærðfræðingnum Leonard Euler (1707 - 1783). Hann lagði grunninn að netafræði til að leysa svipað vandamál og við erum að glíma við. Það var vandamálið um brýrnar í Königsberg, sem snerist um hvort hægt væri að ganga nákvæmlega einu sinni um brýrnar sjö sem tengja borgina Königsberg saman.

Euler leysti vandamálið á sama hátt og við erum að gera; hann breytti vandamálinu í net, og fann svo einfalda leið til að komast að því hvort vegir eins og við erum að leita að séu til fyrir hvaða net sem er. Leiðin hans er að úthluta hverjum hnúti tölu sem við köllum stig, en stig hnútar er einfaldlega fjöldi leggja sem tengjast í hann. Hjá okkur er til dæmis stig b jafnt 5, stig d er einnig jafnt 5, og stig f er jafnt 9.

Það sem Euler sannaði var að vegir eins og þeir sem við viljum finna eru til nákvæmlega þegar fjöldi hnúta með oddatölustig er 0 eða 2. Í stuttu máli er ástæðan fyrir því að ef til er hnútur með oddatölustig, þá þarf vegurinn okkar annað hvort að enda í honum, eða fara út úr honum og koma aldrei í hann aftur. Einhversstaðar þarf vegurinn að byrja eða enda, svo ljóst er að það þarf annan hnút með oddatölustig til móts við þann sem fyrir er. Þá sést líka ef að til er einn eða fleiri hnútar með oddatölustig í viðbót við þessa tvo, þá er vegurinn sem við leitum að ekki til.

Í netinu okkar eru fjórir hnútar með oddatölustig: b, d, e og f, svo að Euler-vegurinn sem við leitum að er ekki til. Þrautin hefur því enga lausn.

Í raun höfum við svarað erfiðari spurningu en beðið var um, því í netinu okkar höfum við hvergi tekið tillit til þess að línan sem óskað var eftir megi ekki skera sjálfa sig. Við höfum sýnt að ekki er til lína sem uppfyllir skilyrðin, og því er sér í lagi ekki til lína sem sker sjálfa sig aldrei og uppfyllir skilyrðin.

Heimildir, lesefni og myndir:

Upprunalega hljóðaði spurningin svona:

Vinnufélagar mínir og ég hafa glímt við gátu í yfir ár. Hún snýst um að geta teiknað óbrotna línu í gegnum hverja hlið á ferhyrningi, sem fyrst er skipt til helminga með láréttri línu, og síðan er efri helmingnum skipt í 3 jafna hluta með 2 lóðréttum línum en neðri skipt í tvo hluta með einni lóðréttri línu fyrir miðju. Markmiðið er að teikna óbrotna línu í gegnum hverja hlið á kassanum og bannað er að fara tvisvar í gegnum sömu hlið eða brjóta línuna. Þúsundir möguleika hafa verið prófaðir en enginn hefur getað leyst þrautina og hefur þeirri hugmynd verið kastað fram að þetta sé í raun ómögulegt á stærðfræðilegum grundvelli. Spurningin er einfaldlega: Er hægt að leysa þrautina? P.S. Ég sendi mynd af þrautinni og ýmsum tilraunum til ritstjórnar, vona að einhver geti sannað hvort þetta sé hægt eða ekki.

Höfundur

Gunnar Þór Magnússon

Gunnar Þór Magnússon

stærðfræðingur

Útgáfudagur

4.7.2008

Spyrjandi

Pétur Örn Pálmarsson

Efnisorð

Tilvísun

Gunnar Þór Magnússon. „Er hægt að leysa þessa þraut sem ég og vinnufélagarnir höfum glímt við í meira en eitt ár?“ Vísindavefurinn, 4. júlí 2008, sótt 3. desember 2024, https://visindavefur.is/svar.php?id=48029.

Gunnar Þór Magnússon. (2008, 4. júlí). Er hægt að leysa þessa þraut sem ég og vinnufélagarnir höfum glímt við í meira en eitt ár? Vísindavefurinn. https://visindavefur.is/svar.php?id=48029

Gunnar Þór Magnússon. „Er hægt að leysa þessa þraut sem ég og vinnufélagarnir höfum glímt við í meira en eitt ár?“ Vísindavefurinn. 4. júl. 2008. Vefsíða. 3. des. 2024. <https://visindavefur.is/svar.php?id=48029>.

Chicago | APA | MLA

Þessi síða notar vafrakökur Nánari upplýsingar

Ég samþykki

Senda grein til vinar

=

Er hægt að leysa þessa þraut sem ég og vinnufélagarnir höfum glímt við í meira en eitt ár?
Þrautin sem um ræðir sést á mynd 1 hér fyrir neðan. 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.



Mynd 1 - Þrautin

Ein tilraun að lausn sést á mynd 2. Þar höfum við þó lent í sjálfheldu, því enn vantar að fara gegnum strikið sem er merkt með rauðu, og við komumst ekki til þess án þess að fara aftur gegnum eitthvað annað strik.



Mynd 2 - Tilraun að lausn

Lesendur eru hvattir til að spreyta sig á þrautinni áður en þeir lesa áfram.

Til þess að svara spurningunni er þægilegt að grípa til svokallaðrar netafræði. Það er grein innan stærðfræði sem hefur verið þróuð til að leysa þrautir sem þessar og önnur svipuð vandamál, þar sem tengingar og sambönd milli hluta skipta máli, frekar en fjarlægðir og stærðir. Til dæmis er netafræði beitt í öllum tækjum sem gefa upp bestu leiðina til að keyra á milli tveggja staða, því þá skiptir frekar máli að vegir liggi á milli staðanna en að upphafs- og lokapunktur séu nálægt hvor öðrum.

Til þess að geta talað um netafræði þurfum við nokkur hugtök hennar. Þau eru einföld og auðskiljanleg. Eins og nafnið gefur til kynna snýst netafræði um net. Sérhvert net samanstendur af hnútum, sem við getum teiknað sem punkta í plani, og leggjum, sem við teiknum sem strik á milli punktanna. Þannig er mynd 3 hér á eftir af einföldu neti, sem hefur hnútana a, b, c og d, og nokkra leggi á milli þeirra.



Mynd 3 - Dæmi um net

Athugið að við getum haft fleiri en einn legg milli tveggja hnúta. Til dæmis eru tveir leggir á milli hnútanna c og d á myndinni. Ef við hugsum um hnútana sem mismunandi staði á Íslandi og leggina sem vegi á milli, þá svarar þetta til þess að tveir mismunandi vegir liggi á milli staðanna.

Nú skulum við breyta þrautinn okkar í net. Við lítum á hvern lítinn kassa sem hnút, og bætum svo við einum hnúti sem táknar allt sem er fyrir utan kassann. Þessa hnúta merkjum við með bókstöfunum frá a upp í f



Mynd 4 - Hnútarnir í þrautinni

Næst tengjum við á milli hnútanna ef við getum komist frá einum kassa í annann. Á mynd 5 fyrir neðan hefur þetta verið gert fyrir hnútinn a. Við tengjum sitt hvorn legginn frá a í hnúta b og d, og tengjum svo tvo leggi frá a í hnút f, vegna þess að úr kassa a komumst við út úr stóra kassanum gegnum tvö mismunandi strik.



Mynd 5 - Leggir lagðir út frá hnúti a

Þetta endurtökum við fyrir hina hnútana, og fáum að lokum netið á mynd 6. Spurningin í þrautinni snýst nú um hvort við getum byrjað í einhverjum hnút, og fundið veg sem fer nákvæmlega einu sinni um hvern legg í netinu.



Mynd 6 - Þrautin gerð að neti

Verkefni af þessu tagi eru algeng í netafræði og vegir eins og sá sem er spurt um kallast Euler-vegir eftir svissneska stærðfræðingnum Leonard Euler (1707 - 1783). Hann lagði grunninn að netafræði til að leysa svipað vandamál og við erum að glíma við. Það var vandamálið um brýrnar í Königsberg, sem snerist um hvort hægt væri að ganga nákvæmlega einu sinni um brýrnar sjö sem tengja borgina Königsberg saman.

Euler leysti vandamálið á sama hátt og við erum að gera; hann breytti vandamálinu í net, og fann svo einfalda leið til að komast að því hvort vegir eins og við erum að leita að séu til fyrir hvaða net sem er. Leiðin hans er að úthluta hverjum hnúti tölu sem við köllum stig, en stig hnútar er einfaldlega fjöldi leggja sem tengjast í hann. Hjá okkur er til dæmis stig b jafnt 5, stig d er einnig jafnt 5, og stig f er jafnt 9.

Það sem Euler sannaði var að vegir eins og þeir sem við viljum finna eru til nákvæmlega þegar fjöldi hnúta með oddatölustig er 0 eða 2. Í stuttu máli er ástæðan fyrir því að ef til er hnútur með oddatölustig, þá þarf vegurinn okkar annað hvort að enda í honum, eða fara út úr honum og koma aldrei í hann aftur. Einhversstaðar þarf vegurinn að byrja eða enda, svo ljóst er að það þarf annan hnút með oddatölustig til móts við þann sem fyrir er. Þá sést líka ef að til er einn eða fleiri hnútar með oddatölustig í viðbót við þessa tvo, þá er vegurinn sem við leitum að ekki til.

Í netinu okkar eru fjórir hnútar með oddatölustig: b, d, e og f, svo að Euler-vegurinn sem við leitum að er ekki til. Þrautin hefur því enga lausn.

Í raun höfum við svarað erfiðari spurningu en beðið var um, því í netinu okkar höfum við hvergi tekið tillit til þess að línan sem óskað var eftir megi ekki skera sjálfa sig. Við höfum sýnt að ekki er til lína sem uppfyllir skilyrðin, og því er sér í lagi ekki til lína sem sker sjálfa sig aldrei og uppfyllir skilyrðin.

Heimildir, lesefni og myndir:

Upprunalega hljóðaði spurningin svona:

Vinnufélagar mínir og ég hafa glímt við gátu í yfir ár. Hún snýst um að geta teiknað óbrotna línu í gegnum hverja hlið á ferhyrningi, sem fyrst er skipt til helminga með láréttri línu, og síðan er efri helmingnum skipt í 3 jafna hluta með 2 lóðréttum línum en neðri skipt í tvo hluta með einni lóðréttri línu fyrir miðju. Markmiðið er að teikna óbrotna línu í gegnum hverja hlið á kassanum og bannað er að fara tvisvar í gegnum sömu hlið eða brjóta línuna. Þúsundir möguleika hafa verið prófaðir en enginn hefur getað leyst þrautina og hefur þeirri hugmynd verið kastað fram að þetta sé í raun ómögulegt á stærðfræðilegum grundvelli. Spurningin er einfaldlega: Er hægt að leysa þrautina? P.S. Ég sendi mynd af þrautinni og ýmsum tilraunum til ritstjórnar, vona að einhver geti sannað hvort þetta sé hægt eða ekki.
...