Broene i Konigsberg, kan du løse det?

[gelali]

Hey, jeg kjedet meg litt og derfor publiserer jeg denne oppgaven som har blitt kanskje publisert her tidligere før. Uansett her er oppgaven:

Finn et utvei der du passerer alle bruene eksakt en gang og er tilbake i samme punktet/bruen som du startet fra.
Lykke til:D

[Realist1]

SPOILER: Det er vel bevist at dette ikke går. /SPOILER

[Gommle]

Hvis vi kaller broene for abcdefg (jeg går øverst fra venstre og ned til høyre), og toppen av broene for f.eks. [tex]a_1[/tex], (eller venstre for de horisontale), og bunnen av broene for [tex]a_2[/tex].

Da får vi:

[tex]a_1\, \rightarrow\, b_1, c_1[/tex]
[tex]a_2\, \rightarrow\, b_2, d_1, e_1, f_1[/tex]
[tex]b_1\, \rightarrow\, a_1, c_1[/tex]
[tex]b_2\, \rightarrow\, a_2, d_1, e_1, f_1[/tex]
[tex]c_1\, \rightarrow\, a_1, b_1[/tex]
[tex]c_2\, \rightarrow\, d_2, g_1[/tex]
[tex]d_1\, \rightarrow\, a_2, b_2, e_1, f_1[/tex]
[tex]d_2\, \rightarrow\, c_2, g_1[/tex]
[tex]e_1\, \rightarrow\, a_2, b_2, d_1, f_1[/tex]
[tex]e_2\, \rightarrow\, f_2, g_2[/tex]
[tex]f_1\, \rightarrow\, a_2, b_2, d_1, e_1[/tex]
[tex]f_2\, \rightarrow\, e_2, g_2[/tex]
[tex]g_1\, \rightarrow\, c_2, d_2[/tex]
[tex]g_2\, \rightarrow\, e_2, f_2[/tex]

Måten å løse det på blir:
1. Begynn et sted
2. Gå til en annen bro (ikke den andre siden av den du er på)
2. Gå til en bro vi ikke har besøkt, med mindre det er den siste broen.
3. Hvis denne siste broen er lik den andre siden av broen vi startet på, har vi greid det.

Nå gjenstår det (bare) å gjøre dette på alle mulige måter, for å vise at det finnes eller ikke finnes en måte.

Jeg forestiller meg at dette kan gjøres ved å lage et slags tre. (Multidimensjonalt array, for programmererne)

Jeg setter i gang med en løsning i Python nå. (eller ark)

[Realist1]

En enkel løsning:

Det er fire "landmasser". Dersom du bruker en bro for å komme dit, må du bruke en annen for å komme ut. Altså må det være et partall antall broer tilknyttet landmassen for å kunne gjøre seg ferdig med den landmassen suksessfullt. Eneste unntaket er landmassen man starter eller slutter på; de kan godt ha odde antall broer tilknyttet.

Alle fire landmassene har et odde antall broer tilknyttet seg (én har 5, mens de tre andre har 3). Dermed kan det umulig gå an.

[etse]

dette er samme figuren som tegningen, men som en graf. Siden alle hjørnene her har oddetall anntall veier, kan man ikke gå alle veiene uten å krysse minst en vei 2 ganger. Dette kommer av at vi har et teorem som sier at en slik sti kun eksisterer om grafen har mer enn 2 punkter/hjørner med oddetall anntall veier som leder ut/inn.

Edit: realisten var både før meg og forklarte bedre >.<

[Gommle]

Jeg tror jeg bør prøve å tenke litt enklere før jeg setter i gang med vanskelige løsninger

Jaja, det er hvertfall lærerikt.