Solving the Königsberg Bridge Problem
This proof is accessible to ANYONE — no mathematics knowledge required! (perfect for if you are a bit bored and in isolation, like me right now!)
The Königsberg bridge problem shows the beauty of mathematics to transform the impossible to the obvious. It also gives an insight into the mind of the genius Leonhard Euler.
Stating the problem
Have a look at the map above.
It’s a diagram of the rivers and bridges of Königsberg. The areas A, B, C and D are bits of land, joined by the bridges, but otherwise cut off from each other by water.
A map of the city is below. Puteți să vă uitați la oricare dintre cele două diagrame – ambele surprind informațiile esențiale: ce pete de teren sunt conectate cu ce alte pete de teren și prin câte poduri.
În limbaj tehnic, reprezentăm acest lucru sub forma unui grafic. Petele de pământ sunt vârfurile, iar podurile sunt marginile. Dar acest lucru nu este important.
Problema este dacă este posibil să găsim un traseu care să treacă peste fiecare pod exact o dată. Asta înseamnă că, în plimbarea noastră prin oraș, vrem ca traseul nostru să treacă peste fiecare pod, dar nu poate trece peste el de două ori, sau de trei ori… Practic, dacă vă regăsiți pe același pod pe care ați fost anterior, traseul este invalid. Dacă vă terminați plimbarea și există un pod pe care nu l-ați traversat, atunci traseul dvs. a fost invalid.
Soluția
Considerați fiecare pată de pământ. Fiecare pod este conectat la două pete de pământ (așa funcționează podurile). Se întâmplă ca fiecare pată de pământ să aibă atașat un număr impar de poduri.
Acum, să ne gândim cum ar arăta o plimbare validă.
În timp ce vă plimbați, notați într-un carnețel de notițe de fiecare dată când vă aflați într-o anumită pată de pământ. De exemplu, dacă începeți în cel mai sudic capăt al orașului, notați acest lucru (faceți o fotografie, cumpărați un suvenir…) și dacă vă regăsiți din nou acolo, creșteți numărătoarea pentru sectorul sudic la doi.
Pentru fiecare pată de pământ există două cazuri
(1) acesta este un sector al orașului în care nici nu ne începem plimbarea, nici nu ne terminăm plimbarea acolo
(2) acesta este un sector al orașului în care fie ne începem plimbarea, fie ne terminăm plimbarea, fie amândouă.
Este clar că există cel mult 2 sectoare ale orașului de al doilea tip. Nu putem începe în două locuri în același timp și nici nu putem termina în două locuri în același timp.
Cum există patru secțiuni ale orașului, înseamnă că există cel puțin două secțiuni ale orașului, în plimbarea noastră, în care nu terminăm și nici nu începem. Să alegem unul dintre ele.
De fiecare dată când intrăm în acel sector, folosim un pod, iar de fiecare dată când îl părăsim, folosim un altul. Dar, fiecare sector are atașat de el un număr impar de poduri! Aceasta este o contradicție. Pentru a vedea de ce, reamintim că fiecare sector are fie 3 poduri, fie are 5 poduri atașate.
Dacă ne aflăm o singură dată în sector, putem utiliza doar două dintre podurile sale. Dacă ne aflăm în el de două ori, vom utiliza patru dintre podurile sale (sau vom rămâne fără poduri, dacă ar avea doar trei poduri). Dacă intrăm în el de trei ori, am avea nevoie de 6 poduri, pe care nu le putem avea. Așadar, cerința ca noi să intrăm și să ieșim atât dintr-un sector al orașului care nu este punctul nostru de plecare sau de sosire contrazice faptul că numărul de poduri de legătură este impar pentru fiecare sector.
.