matematikk.net

Som teamet tilsier lurer jeg på om denne oppgaven er uløselig:



Man skal streke igjennom alle veggene KUN en gang, og har heller ikke lov til å krysse streken man tegner opp. Tilsynelatende virker denne oppgaven uløselig, men jeg lurer på om den kan løses på en spesiell måte, for den har en del mulige utfall.

Dnne oppgaven husker jeg jeg fikk hos en venn, og har bevist uløselig. Her er en kopi av argumentet jeg sendte henne i mail:

Legg merke til at 2 ruter har 4 tilstøtende vegger, og 3 ruter har 5 tilstøtende vegger.
Tenk deg at du starter å tegne linjen UTENFOR en rute med 4 vegger. Endepunktet av linjen som går gjennom alle veggene må ligge UTENFOR denne firkanten - fordi du må passere gjennom tilstøtende vegger 4 ganger. Inn->ut->inn->ut. Slik er det for denne ruten, uansett hvilke andre vegger du velger å krysse i tillegg.

Tenk nå på en rute med 5 vegger. Starter du utenfor en slik en, må endestykket av linjen ende opp INNENFOR ruten. dette fordi du krysser de omliggende veggene fem ganger. inn-ut-inn-ut-inn. Slik er det for denne ruten, uansett hvilke andre vegger du velger å krysse også.

Det som er cluet er at det er 3 ruter med 5 tilstøtende vegger. Når du starter opp, må du nødvendigvis starte opp utenfor 2 av dem. Men for at det skal eksistere en løsning, må endepunktet av linjen ligge inni begge disse to rutene SAMTIDIG - noe som er umulig. Dermed er oppgaven uløselig.

Dette er en klassisk problemoppgave som finnes i flere kjente utgaver (Königsbergs bruer). http://en.wikipedia.org/wiki/Seven_Brid ... B6nigsberg

For å oppsummere litt:

Legg merke til at rommene og veggene kan erstattes med hhv noder og kanter i en graf. Som daofeishi skriver så vil løsbarhet være knyttet til antall noder med et odde antall kanter. For dersom en node ikke skal være verken start- eller sluttnode så må det være like mange kanter inn til noden som ut (i sum et partall antall kanter).

For at en slik graf skal være traverserbar (sammenhengende traversering der hver kant besøkes nøyaktig én gang) må følgende være oppfylt:

Start og slutt i samme node:
- Alle noder med et partall antall kanter

Start og slutt i to forskjellige noder:
- Nøyaktig to noder med et odde antall kanter

Videre kan det relativt lett vises at dersom et av kravene over er oppfylt så er grafen traverserbar (sammenhengende traversering der hver kant besøkes nøyaktig én gang).[/url]

Stemmer, jeg prøvde å ligge unna terminologien når jeg skrev denne forklaringen - teorien jeg brukte bak beviset for dette problemet er grafteori, som regnes for å være grunnlagt ved Eulers broproblem. En traverserbar graf kalles og gjerne en Eulersk graf og sies å ha en Eulersti. (Dersom du snur problemet rundt og ønsker å besøke hver node en og bare én gang ønsker du å finne en såkalt Hamiltonsk sti.) Som dirschler skriver finnes det enkle kriterier for å bestemme om en graf er Eulersk. Dette eksisterer dog ikke for det Hamiltonske problemet.

For å endre tegningen over til en graf, og dermed redusere den til et Eulersk problem, lar du området utenfor hele firkanten være en node, og alle rektangler på innsiden være noder. En kant tegnes mellom to noder dersom det befinner seg en vegg mellom områdene. Dersom grafen hadde vært traverserbar, ville kriteriet om at streken ikke skulle krysse seg selv gå ut på å undersøke grafens planaritet.