Uløselig oppgave?

Her kan brukere av forum utfordre hverandre med morsomme oppgaver og nøtter man ønsker å dele med andre. Dette er altså ikke et sted for desperate skrik om hjelp, de kan man poste i de andre forumene, men et sted for problemløsing på tvers av trinn og fag.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
kadetten
Fibonacci
Fibonacci
Innlegg: 1
Registrert: 06/07-2007 05:35

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

Bilde

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.
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

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.
dischler
Guru
Guru
Innlegg: 242
Registrert: 01/03-2004 10:11

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]
daofeishi
Tyrann
Tyrann
Innlegg: 1486
Registrert: 13/06-2006 02:00
Sted: Cambridge, Massachusetts, USA

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